HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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. 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 our lower bound it would be sufficient to derandomize identity testing for polynomials of a very specific norm: sums of products of sparse polynomials with sparse coefficients. This observation leads to new versions of the Shub-Smale tau-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 good enough 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 this third version of our paper we show that 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 suffice to obtain a lower bound on the size of depth 4 circuits computing the permanent.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

Contributor : Pascal Koiran Connect in order to contact the contributor
Submitted on : Thursday, July 29, 2010 - 10:52:01 PM
Last modification on : Tuesday, May 3, 2022 - 3:14:03 PM
Long-term archiving on: : Thursday, November 4, 2010 - 10:40:39 AM


Files produced by the author(s)


  • HAL Id : ensl-00477023, version 4
  • ARXIV : 1004.4960



Pascal Koiran. Shallow Circuits with High-Powered Inputs. 2010. ⟨ensl-00477023v4⟩



Record views


Files downloads