Algebraic circuit lower bounds bonanza – STOC 2014 Recaps (Part 3)

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 x_1, x_2, \cdots, x_n and the computation is performed using the operations + and \times (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 \mathbb{F} (as opposed to functions) computed by boolean circuits).

The size of an arithmetic circuit is defined as the number of + and \times 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 \Omega(n \log n) due to Baur-Strassen [BS83] from 30 years ago!

Depth-reduction results

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,

Theorem.[AV08, Koi12, Tav13]
Let p_n(\mathbf{x}) \in \mathbb{F}[\mathbf{x}] be a polynomial over n-variables, of degree d = n^{O(1)}. If there is a \mathrm{poly}(n) sized arithmetic circuit computing p_n(\mathbf{x}), then there is a hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-circuit of size 2^{O(\sqrt{d} \log n)} computing p_n.

hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}] denotes homogeneous depth-4 circuits with fan-in of bottom product gates bounded by \sqrt{d}. The contrapositive of the above depth-reduction result says that proving a 2^{\omega(\sqrt{d} \log n)} lower bound on the size of hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-circuits computing p_n(\mathbf{x}), suffices to prove that p_n(\mathbf{x}) cannot be computed by n^{O(1)}-sized arithmetic circuits!

Results from STOC 2014, before and after…

Proving lower bounds for hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-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-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-circuits computing the d \times d determinant (\mathrm{Det}_d) requires size 2^{\Omega(\sqrt{d})}, which is only a \omega(\log n) 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,

  1. Improve the lower bound on hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-circuits
  2. Improve the depth-reduction result from general circuits to hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-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 2^{\Omega(\sqrt{d} \log n)} on size of hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-circuits computing an explicit polynomial (neatly constructed using Nisan-Wigderson designs), denoted by \mathrm{NW}_{n,d}. After this result, we are only a \omega(1) 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 2^{\Omega(\sqrt{d} \log n)} on size of hom-\Sigma\Pi\Sigma\Pi[\sqrt{d}]-circuits computing the iterated matrix product of d generic n \times n matrices, denoted by \mathrm{IMM}_{n,d}. This result improved upon [KSS14] in the sense that \mathrm{IMM}_{n,d} is in \mathrm{VP}, whereas \mathrm{NW}_{n,d} was only in \mathrm{VNP}. 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 2^{\Omega(\sqrt{d} \log n)} lower bound for an explicit polynomial that can be computed by \mathrm{poly}(n)-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-\Sigma\Pi\Sigma\Pi-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-\Sigma\Pi\Sigma\Pi-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 o(\log n).

[KLSS14] Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

And finally, Kayal-Limaye-Saha-Srinivasan prove a super-polynomial lower bound of n^{\Omega(\log n)} on the size of general hom-\Sigma\Pi\Sigma\Pi-circuits computing \mathrm{IMM}_{n,d}. Interestingly, Kumar-Saraf in a different paper [KS13] had independently proved a weaker lower bound of n^{\Omega(\log \log n)} on the same circuit model computing a Nisan-Wigderson type polynomial (similar to the one in [KSS14]).

Subsequent results

Now that super-polynomial lower bounds for hom-\Sigma\Pi\Sigma\Pi-circuits had been shown, it remained open to prove exponential lower bound (such as 2^{\Omega(\sqrt{d} \log n)}) on such circuits. Since the STOC deadline in November 2013, more improvements have come out!

Kayal-Limaye-Saha-Srinivasan [KLSS14] have proved a lower bound of 2^{\Omega(\sqrt{d} \log n)} on the size of hom-\Sigma\Pi\Sigma\Pi-circuits computing an explicit Nisan-Wigderson type polynomial (similar to the ones in [KSS14] and [KS13]).

Completing this picture, Kumar-Saraf [KS14b] have proved a similar lower bound of 2^{\Omega(\sqrt{d} \log n)} on the size of hom-\Sigma\Pi\Sigma\Pi-circuits computing \mathrm{IMM}_{n,d}, which shows that the depth-reduction of [Tav13] is tight even if the reduction was to general \Sigma\Pi\Sigma\Pi-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 \mathcal{C} of circuits, a natural idea (pun intended!) used in most lower bound techniques has been to introduce a measure \Gamma : \mathbb{F}[\mathbf{x}] \rightarrow \mathbb{Z}_+ such that \Gamma(p) is large for a certain polynomial p, but \Gamma(C) is small for any small-sized C \in \mathcal{C}, and hence no small-sized circuit in \mathcal{C} can compute p.

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,

\Gamma_{k, \ell}(f) = \mathrm{dim}(\mathbf{x}^{\le \ell} \partial^{=k} f)

Essentially, this measure looks at the dimension of the sub-space spanned by the polynomials obtained by multiplying monomials of degree at most \ell to all k-th order partials derivatives of f (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.


One thought on “Algebraic circuit lower bounds bonanza – STOC 2014 Recaps (Part 3)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s