Prof. Dr. Peter Bürgisser
Beginn: Montag, den 8. 5. 2006Wichtig: Wir bitten Interessenten, sich in die Mailingliste seminarca einzutragen.
|Mo, 8. 5. 2006||Smoothed analysis of conic condition numbers|
|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|
|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|
|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|
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.