TY - GEN
T1 - Elusive functions and lower bounds for arithmetic circuits
AU - Raz, Ran
PY - 2008
Y1 - 2008
N2 - A basic fact in linear algebra, is that the image of the curve f(x) = (x1, x2, x3, . . . , xm), say over ℂ, is not contained in any m - 1 dimensional affine subspace of ℂm. In other words, the image of f is not contained in the image of any polynomial-mapping1 Γ : ℂm-1 → ℂm of degree 1 (that is, an affine mapping). Can one give an explicit example for a polynomial curve f : ℂ → ℂm, such that, the image of f is not contained in the image of any polynomial-mapping Γ : ℂm-1 → ℂ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 2), of degree up to 2m o(1), implies super-polynomial lower bounds for computing the permanent over ℂ. More generally, we say that a polynomial-mapping f : double strok F signn → double strok F signm is (s,r)-elusive, if for every polynomial-mapping Γ : double strok F signs → double strok F signm of degree r, Image(f) ⊄ Image(Γ). 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 : double strok F signn → double strok F signn2, of degree O(r), that is (s, r)-elusive for s = n1+Ω(1/r). We use this to construct for any r, an explicit example for 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 ≥ 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 n1+Ω(1). Previously, only lower bounds of the type Ω(n . Λr(n)), where Λr(n) are extremely slowly growing functions (e.g., Λ5(n) = log* n, and Λ7(n) = log* log* n), were known for constant-depth arithmetic circuits for polynomials of constant degree.
AB - A basic fact in linear algebra, is that the image of the curve f(x) = (x1, x2, x3, . . . , xm), say over ℂ, is not contained in any m - 1 dimensional affine subspace of ℂm. In other words, the image of f is not contained in the image of any polynomial-mapping1 Γ : ℂm-1 → ℂm of degree 1 (that is, an affine mapping). Can one give an explicit example for a polynomial curve f : ℂ → ℂm, such that, the image of f is not contained in the image of any polynomial-mapping Γ : ℂm-1 → ℂ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 2), of degree up to 2m o(1), implies super-polynomial lower bounds for computing the permanent over ℂ. More generally, we say that a polynomial-mapping f : double strok F signn → double strok F signm is (s,r)-elusive, if for every polynomial-mapping Γ : double strok F signs → double strok F signm of degree r, Image(f) ⊄ Image(Γ). 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 : double strok F signn → double strok F signn2, of degree O(r), that is (s, r)-elusive for s = n1+Ω(1/r). We use this to construct for any r, an explicit example for 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 ≥ 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 n1+Ω(1). Previously, only lower bounds of the type Ω(n . Λr(n)), where Λr(n) are extremely slowly growing functions (e.g., Λ5(n) = log* n, and Λ7(n) = log* log* n), were known for constant-depth arithmetic circuits for polynomials of constant degree.
KW - Theory
UR - http://www.scopus.com/inward/record.url?scp=57049112766&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57049112766&partnerID=8YFLogxK
U2 - 10.1145/1374376.1374479
DO - 10.1145/1374376.1374479
M3 - Conference contribution
AN - SCOPUS:57049112766
SN - 9781605580470
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 711
EP - 720
BT - STOC'08
PB - Association for Computing Machinery
T2 - 40th Annual ACM Symposium on Theory of Computing, STOC 2008
Y2 - 17 May 2008 through 20 May 2008
ER -