Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

被引:16
作者
Limaye, Nutan [1 ]
Srinivasan, Srikanth [2 ]
Tavenas, Sebastien [3 ]
机构
[1] ITU Copenhagen, Copenhagen, Denmark
[2] Aarhus Univ, Aarhus, Denmark
[3] Univ Savoie Mt Blanc, Univ Grenoble Alpes, LAMA, CNRS, Chambery, France
来源
2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021) | 2022年
关键词
Computational complexity; Algebraic complexity theory; Lower bounds; Small depth circuits; HARDNESS-RANDOMNESS TRADEOFFS; ARITHMETIC CIRCUITS; COMPLEXITY; FORMULAS; POWER; SIZE;
D O I
10.1109/FOCS52979.2021.00083
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
An Algebraic Circuit for a polynomial P is an element of F[x(1), ..., x(N)] 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 F-2), 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 general algebraic circuits of all constant depths over all fields of characteristic 0 (or large). We also prove the first lower bounds against homogeneous algebraic circuits of constant depth over any field. Our approach is surprisingly simple. We first prove superpolynomial lower bounds for constant-depth Set-Multilinear circuits. While strong lower bounds were already known against such circuits, most previous lower bounds were of the form f(d) . poly(N), where d denotes the degree of the polynomial. In analogy with Parameterized complexity, we call this an FPT lower bound. We extend a well-known technique of Nisan and Wigderson (FOCS 1995) to prove non-FPT lower bounds against constant-depth set-multilinear circuits computing the Iterated Matrix Multiplication polynomial IMMn,d (which computes a fixed entry of the product of d n x n matrices). More precisely, we prove that any set-multilinear circuit of depth Delta computing IMMn,d must have size at least n(dexp(-O(Delta))). This result holds over any field, as long as d = o(log n). We then show how to convert any constant-depth algebraic circuit of size s to a constant-depth set-multilinear circuit with a blow-up in size that is exponential in d but only polynomial in s over fields of characteristic 0. (For depths greater than 3, previous results of this form increased the depth of the resulting circuit to Omega(log s).) This implies our constant-depth circuit lower bounds. Finally, we observe that our superpolynomial lower bound for constant-depth circuits implies the first deterministic subexponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small depth circuits using the known connection between algebraic hardness and randomness.
引用
收藏
页码:804 / 814
页数:11
相关论文
共 68 条
[1]   SIGMA-11-FORMULAE ON FINITE STRUCTURES [J].
AJTAI, M .
ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) :1-48
[2]  
[Anonymous], 1986, 18 ANN ACM S THEORY, DOI DOI 10.1145/12130.12132
[3]  
[Anonymous], 1987, Computational Limitations of Small-depth Circuits
[4]  
Arvind V, 2019, BULL EUR ASSOC THEOR, P55
[5]  
Beame P, 2010, ACM S THEORY COMPUT, P87
[6]   Algebraic independence and blackbox identity testing [J].
Beecken, M. ;
Mittmann, J. ;
Saxena, N. .
INFORMATION AND COMPUTATION, 2013, 222 :2-19
[7]   A Depth-Five Lower Bound for Iterated Matrix Multiplication [J].
Bera, Suman K. ;
Chakrabarti, Amit .
30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 :183-197
[8]   Cook's versus Valiant's hypothesis [J].
Bürgisser, P .
THEORETICAL COMPUTER SCIENCE, 2000, 235 (01) :71-88
[9]  
Burgisser Peter, 1997, Grundlehren der Mathematischen Wissenschaften, V315
[10]  
Chattopadhyay Arkadev, 2020, ELEC, V27, P166