Workshop on Complexity

Foundations of Computational Mathematics.

Minneapolis, 5-14 August 2002

General information

Worshop date and time: August 12-14, 2002

13:50 to 15:30 and 16:00 to 18:30

Location: University of Minnesota, Minneapolis Campus

Institute for Mathematics and Its Applications: Main Office, 400 Lind Hall, Phone (612) 624-6006.

Workshop registration and lecture rooms at 3-176/3-180, Electrical Eng. and Computer Science Building (Please double-check the exact location on late july).

Local Information and maps

Organizers Pascal Koiran, ENS Lyon.

Gregorio Malajovich, UFRJ.

Related links FoCM'2002 main page

FoCM main page

Abstracts BOOK OF ABSTRACTS (Preliminary)
Schedule Workshop schedule (updated July 22)

Full schedule (FoCM homepage).

Workshop description and scope

This workshop will focus on the complexity of equation solving (linear algebra problems, non-linear equations, path-following algorithms, etc...), and related models of computation (boolean, algebraic, real machines, decision trees, circuits, Valiant's model...).

Unlike the previous FoCM conference, Computational Algebraic Geometry will be covered by another workshop (click here).

Talks will be 25 or 50 minutes long. We will give priority to participants that are not speaking in another workshop.

We still may have a few spots open, so feel free to contact the organizers,

List of participants.

List of speakers

Speaker Title and Abstract
Eric Allender (Semi-plenary) Complexity Classes and Linear Algebra
Eugene Allgower The Efficiency of Exclusion Algorithms
Alexander Barvinok Estimating Maxima by Moments for Functions on Orbits
Saugata Basu Betti Numbers, Spectral Sequences and Algorithms.
Peter Buergisser (Semi-plenary) Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
Felipe Cucker Counting Classes over the real and complex numbers
Jean-Pierre Dedieu Newton Method on Riemannian Manifolds: Covariant Alpha-Theory
Ioannis Emiris Improved algorithms for determinants and resultants
Myong-Hi Kim Implicit Gamma Theorems.
T.Y. Li Calculating Mixed Volume by Finding Mixed Cells
Martin Lotz On the algebraic complexity of colored Tutte polynomials
Gregorio Malajovich Numerics in K\"ahler manifolds.
Pepe Montana The distribution of Condition Numbers of Rational Data of Bounded Bit length
Klaus Meer Towards a complexity theory for analogue systems
Victor Pan Can We Optimize Toeplitz/Hankel Computations ?
Victor Pan Univariate Polynomial Root-Finding with a Lower Computational Precision and Higher Convergence Rates
J. Maurice Rojas (Semi-plenary) Complexity and Rationality
Pradyut Shah Lower Bound Techniques for Parallel Algorithms
Christophe Troestler Scalar- v.s. Vector-recursion for BSS-recursive functions
Gilles Villard On computing the determinant and the inverse of integer matrices

Related sites.

FoCM Main Homepage
Foundations of Computational Mathematics - the Journal