pdf icon
Volume 6 (2010) Article 7 pp. 135-177
Elusive Functions and Lower Bounds for Arithmetic Circuits
by Ran Raz
Received: June 3, 2008
Revised: May 15, 2010
Published: September 11, 2010
Download article from ToC site:
[PDF (502K)] [PS (1927K)] [Source ZIP]
Keywords: algebraic complexity, arithmetic circuits, lower bounds, explicit polynomials, permanent
ACM Classification: F.2.2, F.1.3, F.1.2, G.2.0
AMS Classification: 68Q15, 68Q17, 94C05

Abstract: [Plain Text Version]

$\newcommand{\C}{\mathbb{C}}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\Image}{{\mathrm{Image}}}$

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 $2$ ?

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