## 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 ℂ, 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-mapping^{1} Γ : ℂ^{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 2^{m} ^{o(1)}, implies super-polynomial lower bounds for computing the permanent over ℂ. More generally, we say that a polynomial-mapping f : double strok F sign^{n} → double strok F sign^{m} is (s,r)-elusive, if for every polynomial-mapping Γ : double strok F sign^{s} → double strok F sign^{m} 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 sign^{n} → double strok F sign^{n2}, of degree O(r), that is (s, r)-elusive for s = n^{1+Ω(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 n^{1+Ω(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 language | English (US) |
---|---|

Title of host publication | STOC'08 |

Subtitle of host publication | Proceedings of the 2008 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 711-720 |

Number of pages | 10 |

ISBN (Print) | 9781605580470 |

DOIs | |

State | Published - 2008 |

Externally published | Yes |

Event | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada Duration: May 17 2008 → May 20 2008 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 |
---|---|

Country/Territory | Canada |

City | Victoria, BC |

Period | 5/17/08 → 5/20/08 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Theory