Theory of Computing
-------------------
Title     : Elusive Functions and Lower Bounds for Arithmetic Circuits
Authors   : Ran Raz
Volume    : 6
Number    : 7
Pages     : 135-177
URL       : https://theoryofcomputing.org/articles/v006a007

Abstract
--------

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} --> C^m  of degree 1
(that is, an affine mapping).   Can one give an explicit example 
of a polynomial curve  f: C --> C^m  such that the image of  f  
is not contained in the image of any polynomial mapping
Gamma: C^{m-1} --> 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} --> F^m 
is   (s,r)-elusive, if for every polynomial mapping Gamma: F^{s} --> 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  > n^{1+\Omega(1)}.   Previously, only 
lower bounds of the type  \Omega(n 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).