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.
Nice, there is a non-paywall version at https://hal.science/hal-03367796/document
ReplyDeletehuh, why isnt this on ArXiv?
ReplyDeleteThank you for mentioning our work! :)
ReplyDeleteFor 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! :)
Any connection to boolean complexity of iterated MM?
ReplyDeleteThe problem could still in algebraic NC^1 right?
ReplyDeleteIMM 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.
ReplyDelete(Typed on my phone.)