P. Koiran's lecture at the
Fall school (Sept.'11)

Shallow circuits with high-powered inputs.

A polynomial identity testing algorithm must determine whether an input polynomial (given for instance by an arithmetic circuit) is identically equal to 0. Following Kabanets and Implagliazzo (2004), it has become increasingly clear in recent years that efficient deterministic algorithms for polynomial identity testing would imply strong lower bounds (the connection between arithmetic circuit lower bounds and derandomization of polynomial identity testing was foreshadowed in a 30 years old paper by Heintz and Schnorr). This approach to lower bounds was advocated in particular by Agrawal (2005).

In my talk I will present some further results on univariate polynomial identity testing. I will propose a real version of the tau-conjecture of Shub and Smale on integer roots of univariate polynomials. The real tau conjecture implies a superpolynomial lower bound on the arithmetic complexity of the permanent polynomial. This result was presented at ICS 2011. In this talk I may also discuss some work in progress towards unconditional lower bounds.

Slides.