Oberseminar Komplexität und Algorithmen

Sommersemester 2006

Prof. Dr. Peter Bürgisser

Termin: Montag, 11:15 - 12:45 Uhr im D1.338

Beginn: Montag, den 8. 5. 2006

Wichtig: Wir bitten Interessenten, sich in die Mailingliste seminarca einzutragen.


Mo, 8. 5. 2006 Smoothed analysis of conic condition numbers
und Peter Bürgisser
Mo, 15. 5. 2006

Smoothed analysis of complexity bounds and condition numbers has been done, so far, on a case by case basis. In this paper we consider a reasonably large class of condition numbers for problems over the complex numbers and we obtain smoothed analysis estimates for elements in this class depending only on geometric invariants of the corresponding sets of ill-posed inputs. These estimates are for a version of smoothed analysis proposed in this paper which, to the best of our knowledge, appears to be new. Several applications to linear and polynomial equation solving show that estimates obtained in this way are easy to derive and quite accurate.

Mo, 22. 5. 2006 On the complexity of computing Betti numbers of complex algebraic varieties
und Peter Scheiblechner
Mo, 29. 5. 2006

We extend the lower bounds on the complexity of computing Betti numbers proved by Bürgisser and Cucker to complex algebraic varieties. More precisely, we first prove that the problem of deciding connectedness of a complex affine or projective variety given as the zero set of integer polynomials is PSPACE-hard. Then we prove FPSPACE-hardness for the more general problem of computing Betti numbers of fixed order of a complex projective variety.

Mo, 12. 6. 2006 Computing with roots of unity in the BSS model
und Emmanuel Jeandel
Mo, 19. 6. 2006

We are interested in the following problem: Is the group generated by some matrices X_1 .. X_k finite? This problem is known to be polynomial in the classical model of computation (coefficients are rationals given in binary representation). In the Turing model with complex or real numbers, the problem becomes undecidable. However, if we add an oracle which decides if a matrix is of finite order, it becomes decidable.

We discuss here the Turing model with this oracle. The main result is that we really need an oracle for matrices of all sizes: There is no algorithm which given an oracle which decides if a n by n matrix is of finite order can solve the same problem for n+1 by n+1 matrices. The proof uses a deep result from Diophantine Geometry, namely the Mordell-Lang conjecture (McQuillan theorem) and a slight part of the talk will be devoted to this theorem.

Mo, 3. 7. 2006 Mixed Volume of Lattice Polytopes
Dennis Amelunxen

The mixed volume of convex sets is a multivariable generalization of the normal Euclidean volume in n-dimensional space (the Euclidean volume is its diagonal form). For sparse polynomial systems it is used to give the so-called BKK-bound for the number of isolated zeros. This bound is (in this context) considerably sharper than the Bézout bound so that it improves for example homotopy methods for polynomial systems.

In this talk the notion of the Mixed Volume shall be presented and analyzed for lattice polytopes.