Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Nutan Limaye; Srikanth Srinivasan; Sébastien Tavenas

doi:10.1109/FOCS52979.2021.00083

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Nutan Limaye
, Srikanth Srinivasan
, Sébastien Tavenas

Algorithms

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

An Algebraic Circuit for a polynomial P ∈F[x1,…,xN] 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 fields other than F2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first super polynomial lower bounds against general algebraic circuits of all constant depths over all fields of characteristic 0 (or large).

Original language	English
Title of host publication	2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Publisher	IEEE
Publication date	4 Mar 2022
ISBN (Electronic)	978-1-6654-2055-6
DOIs	https://doi.org/10.1109/FOCS52979.2021.00083
Publication status	Published - 4 Mar 2022
Event	Symposium on Foundations of Computer Science - VIRTUAL, VIRTUAL Duration: 7 Feb 2022 → 10 Feb 2022 https://ieee-focs.org/FOCS-2021-Papers/content/start.html

Symposium

Symposium	Symposium on Foundations of Computer Science
Location	VIRTUAL
City	VIRTUAL
Period	07/02/2022 → 10/02/2022
Internet address	https://ieee-focs.org/FOCS-2021-Papers/content/start.html

Keywords

Algebraic circuits
Polynomial circuit complexity
Depth-3 and depth-4 circuits
Lower bounds in algebraic computation
Fields of characteristic zero

Access to Document

10.1109/FOCS52979.2021.00083

intro-inhomogeneousOther version, 554 KB

Cite this

@inproceedings{3635f358f315459fa97bb73a884b6145,

title = "Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits",

abstract = "An Algebraic Circuit for a polynomial P ∈F[x1,…,xN] 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 fields other than F2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first super polynomial lower bounds against general algebraic circuits of all constant depths over all fields of characteristic 0 (or large). ",

keywords = "Algebraic circuits, Polynomial circuit complexity, Depth-3 and depth-4 circuits, Lower bounds in algebraic computation, Fields of characteristic zero",

author = "Nutan Limaye and Srikanth Srinivasan and S{\'e}bastien Tavenas",

year = "2022",

month = mar,

day = "4",

doi = "10.1109/FOCS52979.2021.00083",

language = "English",

booktitle = "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)",

publisher = "IEEE",

address = "United States",

note = "Symposium on Foundations of Computer Science, FOCS ; Conference date: 07-02-2022 Through 10-02-2022",

url = "https://ieee-focs.org/FOCS-2021-Papers/content/start.html",

}

TY - GEN

T1 - Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

AU - Limaye, Nutan

AU - Srinivasan, Srikanth

AU - Tavenas, Sébastien

PY - 2022/3/4

Y1 - 2022/3/4

N2 - An Algebraic Circuit for a polynomial P ∈F[x1,…,xN] 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 fields other than F2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first super polynomial lower bounds against general algebraic circuits of all constant depths over all fields of characteristic 0 (or large).

AB - An Algebraic Circuit for a polynomial P ∈F[x1,…,xN] 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 fields other than F2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first super polynomial lower bounds against general algebraic circuits of all constant depths over all fields of characteristic 0 (or large).

KW - Algebraic circuits

KW - Polynomial circuit complexity

KW - Depth-3 and depth-4 circuits

KW - Lower bounds in algebraic computation

KW - Fields of characteristic zero

U2 - 10.1109/FOCS52979.2021.00083

DO - 10.1109/FOCS52979.2021.00083

M3 - Article in proceedings

BT - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - Symposium on Foundations of Computer Science

Y2 - 7 February 2022 through 10 February 2022

ER -

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Abstract

Symposium

Keywords

Access to Document

Fingerprint

Cite this