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.

6 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
  5. The problem could still in algebraic NC^1 right?

    ReplyDelete
  6. IMM is in algebraic SAC1. It would be very surprising if it is in algebraic NC1. It would in particular show that anything computable by an algebraic branching program can also be computed by an algebraic formula.

    (Typed on my phone.)

    ReplyDelete