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.

4 comments:

  1. Nice, there is a non-paywall version at https://hal.science/hal-03367796/document

    ReplyDelete
  2. huh, why isnt this on ArXiv?

    ReplyDelete
  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.) https://eccc.weizmann.ac.il/report/2021/081/

    Thomas Thierauf has written a short note about it as well, if that seems more accessible. https://image.informatik.htw-aalen.de/~thierauf/Papers/Const_Depth-LST%202021.pdf

    It has also been explained really well in Ramprasad Saptharishi's survey, which is available here https://github.com/dasarpmar/lowerbounds-survey.

    I hope this helps! :)

    ReplyDelete
  4. Any connection to boolean complexity of iterated MM?

    ReplyDelete