ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 309-320, 978-7-302-24517-9
Tsinghua University Press

Shallow Circuits with High-Powered Inputs Authors : Pascal Koiran [Download PDF]

Abstract:
A polynomial identity testing algorithm must determine whether an input polynomial (given for instance by an arithmetic circuit) is identically equal to 0. In this paper, we show that a deterministic black-box identity testing algorithm for (high-degree) univariate polynomials would imply a lower bound on the arithmetic complexity of the permanent. The lower bounds that are known to follow from derandomization of (low-degree) multivariate identity testing are weaker.
To obtain a lower bound for the permanent it would be su±cient to derandomize identity testing for polynomials of a very speci¯c norm: sums of products of sparse polynomials with sparse coe±cients. This observation leads to new versions of the Shub-Smale ¿ -conjecture on integer roots of univariate polynomials. In particular, we show that a lower bound for the permanent would follow if one could give a polynomial upper bound on the number of real roots of sums of products of sparse polynomials (Descartes' rule of signs gives such a bound for sparse polynomials and products thereof). In fact the same lower bound would follow even if one could only prove a slightly superpolynomial upper bound on the number of real roots. This is a consequence of a new result on reduction to depth 4 for arithmetic circuits which we establish in a companion paper. We also show that an even weaker bound on the number of real roots would su±ce to obtain a lower bound on the size of depth 4 circuits computing the permanent.
These results suggest the intriguing possibility that tools from real analysis might be brought to bear on a longstanding open problem: what is the arithmetic complexity of the permanent polynomial?

Preview: