Revised: May 15, 2010

Published: September 11, 2010

**Keywords:**algebraic complexity, arithmetic circuits, lower bounds, explicit polynomials, permanent

**Categories:**complexity theory, algebraic complexity, lower bounds, circuit complexity, arithmetic circuits, separation of complexity classes, polynomials - multivariate, polynomial mapping, explicit construction, permanent

**ACM Classification:**F.2.2, F.1.3, F.1.2, G.2.0

**AMS Classification:**68Q15, 68Q17, 94C05

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