Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

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).