Speaker: Pascal Koiran
Ecole Normale Superieure de Lyon
Title: Shallow circuits with high-powered inputs.
Abstract: 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 year 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 highlight three open problems which can be viewed as refinements of the tau-conjecture of Shub and Smale on integer roots of univariate polynomials.
In particular, I will propose a real version of the tau conjecture. A positive answer to any of these three problems would imply a superpolynomial lower bound on the arithmetic complexity of the permanent polynomial.