ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 309320, 9787302245179
Tsinghua University Press 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 blackbox identity testing algorithm for (highdegree) 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 (lowdegree) 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 ShubSmale ¿ 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:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.