A Wronskian approach to the real tau-conjecture


Pascal Koiran, Ecole Normale Supérieure de Lyon. 28 mars 2013 14:00 labo
Abstract:

According to Shub and Smale's tau-conjecture, the number of integer roots of a univariate polynomial should be polynomially bounded in the size of the smallest (constant free) straight-line program computing it. This statement becomes provably false if one counts real roots instead of integer roots. I have proposed a real version of the tau-conjecture where the attention is restricted to straight-line programs of a special form: the sums of products of sparse polynomials. This conjecture implies that the permanent polynomial cannot be computed by polynomial-size arithmetic circuits. The complexity of the permanent in the arithmetic circuit model is a long standing open problem, which can be thought of as an algebraic version of P versus NP. In this talk I will present the real tau-conjecture and its consequence for the permanent. If time allows, I will introduce a new tool in this context: the Wronksian determinant. This leads to some modest progress on the real tau-conjecture, and to new bounds on the number of solutions of sparse systems of polynomial equations. The latter bounds seem to be of independent interest from the point of view of real algebraic geometry.