Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

An Algebraic Circuit for a polynomial P P Frx 1 , . . . , x N s 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 pdq ¨polypN q, 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 IMM n,d (which computes a fixed entry of the product of d n ˆn matrices). More precisely, we prove that any set-multilinear circuit of depth ∆ computing IMM n,d must have size at least n d expp´Op∆qq . This result holds over any field, as long as d " oplog nq.

We then show how to convert any constant-depth algebraic circuit of size s to a constantdepth 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 Ωplog sq.) This implies our constantdepth circuit lower bounds.

We can also use these lower bounds to prove a Depth Hierarchy theorem for constantdepth circuits. We show that for every depth Γ, there is an explicit polynomial which can be computed by a depth Γ circuit of size s, but requires circuits of size s ωp1q if the depth is Γ ´1.

Finally, we observe that our superpolynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial