Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.
An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be e...
| Published in: | Communications of the ACM Vol. 67; no. 2; pp. 101 - 109 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Published: |
Association for Computing Machinery
Feb2024
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=175048204&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 175048204 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Feb2024 vid: 67 iid: 2 pid: 68 pub: Association for Computing Machinery artinfo: ui: 175048204 10.1145/3611094 ppf: 101 ppct: 8 formats: tig: atl: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. aug: au: Limaye, Nutan Srinivasan, Srikanth Tavenas, Sébastien affil: ITU Copenhagen, Denmark Aarhus University, Denmark Université Savoie Mont Blanc, CNRS, LAMA, France su: Algebra Polynomials Circuit complexity Algorithms Directed acyclic graphs Logic circuits sug: subj: Algebra Polynomials Circuit complexity Algorithms Directed acyclic graphs Logic circuits ab: An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over any field other than F), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0. We also observe that our super-polynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small-depth circuits using the known connection between algebraic hardness and randomness. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2024 holdings: @attributes: islocal: N |
|---|