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 their paper on the ``chasm at depth four'', Agrawal and Vinay have shown that low degree multivariate polynomials which have nontrivial arithmetic circuits also have nontrivial arithmetic circuits of depth four. In this second version of our paper we state (and to some extent use) a new result on reduction to depth four for arithmetic circuits.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00477023
Contributor : Pascal Koiran <>
Submitted on : Saturday, May 29, 2010 - 12:04:56 AM
Last modification on : Friday, September 10, 2021 - 2:34:03 PM
Long-term archiving on: : Thursday, September 30, 2010 - 4:46:16 PM

Files

v2prunel.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

28

Files downloads

17