Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

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

ISSN 1433-8092 | Imprint