Dear all,

please note the change of location for the second talk next week:

Dear all,

next week Peter Bürgisser from Paderborn is visiting us. He will give two talks on applied mathematics and complexity theory. Please see below for the announcements.

All the best,

Matthias.

Matthias Christandl Institute for Theoretical Physics ETH Zurich http://www.itp.phys.ethz.ch/people/christandl/index

---

Speaker: Peter Bürgisser (University of Paderborn)

Time and Location: Tuesday, 14th of September, 11am, HG F 33.1 (ETH Zentrum)

Title: Smoothed analysis of condition numbers

Abstract: We present some recent results on the probabilistic behaviour of interior point methods for the convex conic feasibility problem and for homotopy methods solving complex polynomial equations. As suggested by Spielman and Teng, the goal is to prove that for all inputs (even ill-posed ones), and all slight random perturbations of that input, it is unlikely that the running time will be large. These results are obtained through a probabilistic analysis of the condition of the corresponding computational problems.

---

Speaker: Peter Bürgisser (University of Paderborn)

Time and Location: Thursday, 16th of September, 11am, HPK D 24.2 (ETH Hönggerberg)

Title: The state of the art in geometric complexity theory

Abstract: Geometric complexity theory is an approach towards the fundamental lower bound problems in complexity theory based on algebraic geometry and representation theory. Originally, it has been proposed for the permanent versus determinant problem. Recently, the overall framework has been applied and further developed for the tensor rank problem (complexity of matrix multiplication). While no good lower bounds have been obtained so far with these methods, we have now a much clearer understanding of the mathematical difficulties to be overcome for advancing.

Matthias Christandl Institute for Theoretical Physics ETH Zurich http://www.itp.phys.ethz.ch/people/christandl/index