Pritish Kamath has kindly agreed to survey the exciting flurry of algebraic complexity theory results in STOC, which, to many of us, is in a permanent state of mystery. But Pritish did some valiant depth-reduction on the state of affairs in the area, and I hope you’ll appreciate his determined effort.
Pritish Kamath on the latest and greatest in algebraic circuit lower bounds
The most natural and intuitive way to compute a polynomial is via an arithmetic circuit. In this model the inputs are variables and the computation is performed using the operations and (where we allow the gates to take arbitrary linear combinations of its inputs). The output of the circuit is a formal polynomial over the base field (as opposed to functions) computed by boolean circuits).
The size of an arithmetic circuit is defined as the number of and gates in the circuit, and is typically measured with respect to the number of variables. Proving super-polynomial lower bounds on the size of arithmetic circuits computing any explicit polynomial is one of the most important open problems in the area of algebraic complexity theory. The best known lower bound as of today is a modest due to Baur-Strassen [BS83] from 30 years ago!
Since proving lower bounds for general arithmetic circuits is such a daunting task, it is natural to focus on proving lower bounds for restricted models. One such restriction is of constant-depth circuits. Although this seems like a severe restriction, a surprising result due to Agrawal-Vinay [AV08], subsequently strengthened by Koiran [Koi12] and Tavenas [Tav13] showed that if a polynomial is computed by poly-sized circuits, then they are in fact computed by not-so-large-sized depth-4 circuits. In particular, they showed the following theorem,
hom- denotes homogeneous depth-4 circuits with fan-in of bottom product gates bounded by . The contrapositive of the above depth-reduction result says that proving a lower bound on the size of hom--circuits computing , suffices to prove that cannot be computed by -sized arithmetic circuits!
Results from STOC 2014, before and after…
Proving lower bounds for hom--circuits seems like a conceptually much simpler task than proving lower bounds for general circuits. Using a new technique of the shifted partial derivatives, Gupta et al [GKKS13] showed that hom--circuits computing the determinant () requires size , which is only a factor away (in the exponent), from the depth-reduction result!
Thus, after the above result was established, there were two possible approaches for proving super-polynomial lower bounds for general circuits,
- Improve the lower bound on hom--circuits
- Improve the depth-reduction result from general circuits to hom--circuits
Post-[GKKS13], there was a lot of excitement and a flurry of activity followed, proving stronger lower bounds (in fact the improved depth reduction of Tavenas [Tav13] came after [GKKS13]). The magnitude of this activity is well illustrated by the fact that there were a sequence of four papers in STOC 2014, each showing significant improvements over the previous ones, all produced in a span of just 6 months or so!
[KSS14] A super-polynomial lower bound for regular arithmetic formulas
In this paper, Kayal-Saha-Saptharishi prove a lower bound of on size of hom--circuits computing an explicit polynomial (neatly constructed using Nisan-Wigderson designs), denoted by . After this result, we are only a factor away (in the exponent) from our goal!
[FLMS14] Lower bounds for depth 4 formulas computing iterated matrix multiplication
In this paper, Fournier-Limaye-Malod-Srinivasan prove a lower bound of on size of hom--circuits computing the iterated matrix product of generic matrices, denoted by . This result improved upon [KSS14] in the sense that is in , whereas was only in . This shows that the depth-reduction of [Tav13] is in fact tight, and hence rules out approach (b) stated above!
[KS14a] The Limits of Depth Reduction for Arithmetic Formulas: It’s all about the top fan-in
Taking it one more step further than [FLMS14], Kumar-Saraf prove a lower bound for an explicit polynomial that can be computed by -sized formulas, thus showing that the depth-reduction of Tavenas is in fact tight even for formulas (formulas are weaker models than circuits, in that, the fan-out of any gate in a formula is at most one; thus, formulas are representable by trees, whereas circuits are represented by directed acyclic graphs).
Another question that had been tantalizingly open for a long time was to prove super-polynomial lower bounds on the size of general hom--circuits (that is, homogenous depth-4 circuits without the bottom fan-in restriction). Towards this direction, Kumar-Saraf considered the problem of proving lower bounds on size of hom--circuits with bounded top fan-in, and in this paper, they also prove a super-polynomial lower bound on size of such circuits where the top fan-in is .
[KLSS14] Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
And finally, Kayal-Limaye-Saha-Srinivasan prove a super-polynomial lower bound of on the size of general hom--circuits computing . Interestingly, Kumar-Saraf in a different paper [KS13] had independently proved a weaker lower bound of on the same circuit model computing a Nisan-Wigderson type polynomial (similar to the one in [KSS14]).
Now that super-polynomial lower bounds for hom--circuits had been shown, it remained open to prove exponential lower bound (such as ) on such circuits. Since the STOC deadline in November 2013, more improvements have come out!
Completing this picture, Kumar-Saraf [KS14b] have proved a similar lower bound of on the size of hom--circuits computing , which shows that the depth-reduction of [Tav13] is tight even if the reduction was to general -circuits (without bottom fan-in condition).
Perhaps we will see these papers in FOCS 2014. ;)
Bird’s eye view of the techniques
To prove lower bounds on any class of circuits, a natural idea (pun intended!) used in most lower bound techniques has been to introduce a measure such that is large for a certain polynomial , but is small for any small-sized , and hence no small-sized circuit in can compute .
The main technique used in all the papers above are certain variants of the measure of shifted-partial derivatives technique introduced in [Kay12] and [GKKS13], inspired by the measure of partial derivatives introduced by Nisan-Wigderson [NW95]. The measure is defined as follows,
Essentially, this measure looks at the dimension of the sub-space spanned by the polynomials obtained by multiplying monomials of degree at most to all -th order partials derivatives of (where we think of polynomials as a vector of coefficients).
The other new ideas used in the papers described has been the idea of random restrictions (somewhat seen in the context of Håstad’s switching lemma), and of looking at novel variants of shifted partial derivatives by means of projections onto a smaller space of polynomials. In the interest of length of this post, we won’t go into those details here.