Name
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. |
Year | Venue | Keywords |
|---|---|---|
2010 | Clinical Orthopaedics and Related Research | computational complexity,upper bound,sum of products,lower bound |
Field | DocType | Volume |
Polynomial identity testing,Discrete mathematics,Combinatorics,Polynomial arithmetic,Polynomial,Upper and lower bounds,Descartes' rule of signs,Arithmetic circuit complexity,Univariate,Mathematics,Computing the permanent | Journal | abs/1004.4 |
Citations | PageRank | References |
19 | 1.48 | 15 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Koiran | 1 | 919 | 113.85 |