__
TR08-001 | 5th January 2008 00:00
__

#### Elusive Functions and Lower Bounds for Arithmetic Circuits

TR08-001
Authors:

Ran Raz
Publication: 6th January 2008 21:33

Downloads: 3261

Keywords:

**Abstract:**
A basic fact in linear algebra is that the image of the curve

$f(x)=(x^1,x^2,x^3,...,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

$G:C^{m-1} ---> C^m$ of degree 1(that is, an affine mapping).

Can one give an explicit example for a polynomial curve

$f:C ---> C^m$, such that, the image of $f$ is not contained in

the image of any polynomial-mapping $G:C^{m-1} ---> C^m$ of degree 2 ?

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 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 ---> F^m$ is

$(s,r)$-elusive, if for every polynomial-mapping $G:F^s ---> F^m$ of degree $r$, $Image(f)$ is not contained in Image(G)$.

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

for a polynomial-mapping $f:F^n ---> 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

for an $n$-variate polynomial of total-degree $O(r)$, such that,

any depth $r$ arithmetic circuit for this polynomial (over any field)

is of size $> 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 $> n^{1+\Omega(1)}$.

Previously, only lower bounds of the type

$\Omega(n \cdot \lambda_r (n))$, where $\lambda_r (n)$ are extremely

slowly growing functions (e.g., $\lambda_5(n) = \log^{*}n$, and

$\lambda_7(n) = \log^* \log^{*}n$), were known for constant-depth arithmetic circuits for polynomials of constant degree.