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 illposed 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 PSPACEhard. Then we prove FPSPACEhardness 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 MordellLang 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 ndimensional space (the Euclidean volume is its diagonal form). For sparse polynomial systems it is used to give the socalled BKKbound 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. 

Folien 