
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).