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?
ReplyDelete