Needless to say, this result is very remote from my areas of expertise, but still it sounds fantastic enough to call attention to. I have verified with an expert that my impression is correct.
An Algebraic Circuit for a polynomial $P\in F[x_1,\ldots,x_N]$ is a computational model for constructing the polynomial $P$ using only additions and multiplications. It is a \emph{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), 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)\cdot 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 $IMM_{n,d}$ (which computes a fixed entry of the product of $d$ $n\times n$ matrices). More precisely, we prove that any set-multilinear circuit of depth $\Delta$ computing $IMM_{n,d}$ must have size at least $n^{d^{\exp(-O(\Delta))}}.$ This result holds over any field.
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 for $d$ that is a slow-growing function of $n$.
Finally, we observe that our superpolynomial 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.
Available from ECCC TR21-081