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