Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-001 | 5th January 2008 00:00

Elusive Functions and Lower Bounds for Arithmetic Circuits

RSS-Feed




TR08-001
Authors: Ran Raz
Publication: 6th January 2008 21:33
Downloads: 3237
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