Revised: May 15, 2010
Published: September 11, 2010
Abstract: [Plain Text Version]
It is a basic fact of linear algebra that the image of the curve
$f(x)=(x^1,x^2,x^3,\ldots,x^m)$, say over $\C$,
is not contained in any $(m-1)$-dimensional affine subspace of
$\C^m$.
In other words, the image of $f$ is not contained in the image
of any polynomial mapping
$\Gamma:\C^{m-1} \rightarrow \C^m$ of degree 1
(that is, an affine mapping).
Can one give an explicit example of a polynomial
curve $f:\C \rightarrow \C^m$ such
that the image of $f$ is not contained in the image
of any polynomial mapping
$\Gamma:\C^{m-1} \rightarrow \C^m$ of degree
In this paper, we show that problems of this type are closely related to proving lower bounds for the size of general arithmetic circuits. For example, any explicit $f$ as above (with the right notion of explicitness), of degree up to $2^{m^{o(1)}}$, implies super-polynomial lower bounds for computing the permanent over$~\C$.
More generally, we say that a polynomial mapping $f:\F^{n} \rightarrow \F^m$ is $(s,r)$-elusive, if for every polynomial mapping $\Gamma:\F^{s} \rightarrow \F^m$ of degree $r$, $\Image(f) \not \subset \Image(\Gamma)$. We show that for many settings of the parameters $n,m,s,r$, explicit constructions of elusive polynomial mappings imply strong (up to exponential) lower bounds for general arithmetic circuits.
Finally, for every $r < \log n$, we give an explicit example of a polynomial mapping $f:\F^{n} \rightarrow \F^{n^2}$, of degree $O(r)$, that is $(s,r)$-elusive for $s = n^{1+\Omega(1/r)}$. We use this to construct for any $r$, an explicit example of an $n$-variate polynomial of total-degree $O(r)$, with coefficients in $\{0,1\}$, such that any depth-$r$ arithmetic circuit for this polynomial (over any field) is of size $\geq n^{1+\Omega(1/r)}$.
In particular, for any constant $r$, this gives a constant degree polynomial such that any depth $r$ arithmetic circuit for this polynomial is of size $\geq n^{1+\Omega(1)}$. Previously, only lower bounds of the type $\Omega(n \cdot \lambda_r (n))$, where the $\lambda_r$ are extremely slowly growing functions, were known for constant-depth arithmetic circuits for polynomials of constant degree (actually, for linear functions).
Licensed under a Creative Commons Attribution License (CC-BY)