Thursday, June 13, 2024

Favorite Theorems: Algebraic Circuits

May Edition

Most of my favorite theorems tell us something new about the world of complexity. But let's not forget the greatest technical challenges in our area: proving separations that are "obviously" true. Here's the most exciting such result from the past decade.  

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas

In this model, the inputs are variables and constants, and the goal is to create a specific formal polynomial using the gate operations of plus and times. Limaye, Srinivasan and Tavenas find an explicit polynomial such that any polynomial-size constant-depth algebraic circuit will compute it. 

How explicit? Here it is: Take d nxn matrices, multiply them together and output the top left element of the product. The \(N=dn^2\) variables are the entries of the matrices. The top left element is a polynomial of the inputs that can be computed by a simple polynomial-size circuit that just computes the iterated multiplication, just not in constant depth. The paper shows that for an unbounded d that is \(o(\log n)\), there is no constant-depth polynomial-size algebraic circuit.

The authors first prove a lower bound for set multilinear circuits and then extend to more general algebraic circuits.


  1. Nice, there is a non-paywall version at

  2. huh, why isnt this on ArXiv?

  3. Thank you for mentioning our work! :)

    For the anonymous commenter: Here is a link to the ECCC version. (ECCC is the Arxiv equivalent for Complexity Theory.)

    Thomas Thierauf has written a short note about it as well, if that seems more accessible.

    It has also been explained really well in Ramprasad Saptharishi's survey, which is available here

    I hope this helps! :)

  4. Any connection to boolean complexity of iterated MM?