Elusive functions and lower bounds for arithmetic circuits

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages711-720
Number of pages10
ISBN (Print)9781605580470
DOIs
StatePublished - 2008
Externally publishedYes
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CountryCanada
CityVictoria, BC
Period5/17/085/20/08

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Theory

Fingerprint Dive into the research topics of 'Elusive functions and lower bounds for arithmetic circuits'. Together they form a unique fingerprint.

  • Cite this

    Raz, R. (2008). Elusive functions and lower bounds for arithmetic circuits. In STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing (pp. 711-720). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/1374376.1374479