Algorithmic Method for Proving Circuit Lower Bounds

Proving circuit lower bounds is one of the most challenging questions in complexity theory. It is deeply connected to many fundamental questions such as \(\mathsf{P}\) vs. \(\mathsf{NP}\) and derandomization. However, after much progress in the 1980s, there has been a hiatus in new circuit lower bounds for decades. In particular, we did not have any non-trivial super-polynomial lower bounds against the frontier circuit class \(\mathsf{ACC^0}\) (which is the class of constant-depth circuits consisting of unbounded fan-in \(\mathsf{AND}\), \(\mathsf{OR}\) and \(\mathsf{MOD}[m]\) gates for a constant \(m\)).

A decade ago, Williams [Wil’11] proved that \(\mathsf{NEXP} \not\subset \mathsf{ACC}^0\) by introducing the algorithmic method [Wil’10], which connects algorithm design to circuit lower bounds. The most notable part of this approach is it avoids all previous barriers for proving circuit lower bounds and puts together nearly every gem in complexity theory, ranging from time hierarchy theorem to \(\mathsf{IP} = \mathsf{PSPACE}\). Building on [Wil’11], a recent breakthrough [MW’18] by Murray and Williams significantly improved the state-of-the-art lower bounds for \(\mathsf{ACC}^0\) by showing \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}] \not\subset \mathsf{ACC}^0\).

Some of my papers ([Chen’19], [Chen-Ren’20], [Chen-Lyu-Williams’20], [Chen-Lyu’21], [Alman-Chen’19], [Chen-Williams’19]) are devoted to obtaining stronger circuit lower bounds using the algorithmic method. They are summarized below.

1. Average-Case Circuit Lower Bounds from Algorithmic Method

• Most previous work using the algorithmic method can only achieve worst-case lower bounds, although average-case lower bounds (w.r.t. uniform distribution) have more applications, including constructions of pseudorandom generators. In [R.Chen-Oliveira-Santhanam’18], R.Chen, Oliveira, and Santhanam took the first step in that direction and proved that \(\mathsf{NEXP}\) cannot be \(1/2 + 1/\mathrm{polylog}(n)\)-approximated by poly-size \(\mathsf{ACC}^0\).

• In [Chen’19], I proved that \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}]\) cannot be \(1/2 + 1/\mathrm{polylog}(n)\)-approximated by poly-size \(\mathsf{ACC}^0\), improving on both of [R.Chen-Oliveira-Santhanam’18] and [Murray-Williams’18].

• The immediate question left open in [Chen’19] is whether the inapproximability ratio of \(1/2 + 1/\mathrm{polylog}(n)\) can be further improved to \(1/2 + 1/n^{k}\) for every \(k\). In [Chen-Ren’20], building crucially on [Chen-Williams’19] and [Chen’19], Hanlin Ren and I did just that by proving that \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}]\) cannot be \(1/2 + 1/n^k\)-approximated by poly-size \(\mathsf{ACC}^0\), for every constant \(k\).
  This is the first strong average-case lower bounds (\(1/2+n^{-k}\) for every \(k\)) against even the \(\mathsf{AC}^0[\oplus]\) circuits (or even \(\log n\)-degree \(\mathbb{F}_2\)-polynomials). Prior to our work, it was even unknown that whether \(\mathsf{E}^{\mathsf{NP}}\) can be \((1/2+1/\sqrt{n})\)-approximated by poly-size \(\mathsf{AC}^0[\oplus]\) circuits (or \(\log n\)-degree \(\mathbb{F}_2\)-polynomials).
  In a concurrent work, [Viola’20] proved that \(\mathsf{E}^{\mathsf{NP}}\) cannot be \((1/2+n^{-1+\Omega(1)})\)-approximated by \(2^{n^{o(1)}}\)-size \(\mathsf{AC^0}[\oplus]\) circuits.

• The lower bound in [Chen-Ren’20] is only super polynomial, and an open question was whether one can show strong average-case lower bounds against sub-exponential-size \(\mathsf{ACC}^0\) circuits. In [Chen-Lyu-Williams’20], Xin Lyu, Ryan Williams, and I proved that \(\mathsf{E}^{\mathsf{NP}}\) cannot be \(1/2+1/2^{n^{o(1)}}\)-approximated by \(2^{n^{o(1)}}\)-size \(\mathsf{ACC}^0\) circuits. Note that this is incomparable with [Chen-Ren’20], as we are now considering the complexity class \(\mathsf{E}^{\mathsf{NP}}\), which is much bigger than \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}]\).
  In [Chen-Lyu-Williams’20], we also proved that \(\mathsf{E}^{\mathsf{NP}}\) cannot be \(\left(1/2 + 1/2^{n^{o(1)}}\right)\)-approximated by \(n^{1/2-\varepsilon}\)-degree \(\mathbb{F}_2\)-polynomials, for every \(\varepsilon > 0\).

• In [Chen-Lyu’21], Xin Lyu and I improved the correlation bound above by showing that \(\mathsf{E}^{\mathsf{NP}}\) cannot be \(\left(1/2 + 1/2^{d}\right)\)-approximated by degree-\(d\) \(\mathbb{F}_2\)-polynomials, for \(d = \sqrt{n/\log n}\).
  We also observed that improving the parameter \(d\) mentioned above to even \(n^{1/2+\varepsilon}\) would imply breakthrough new circuit lower bounds (\(2^{n^{1/2+\varepsilon}}\)) against depth-\(3\) \(\mathsf{AC}^0\) circuits.

2. Construction of Rigid Matrices using Algorithmic Method

• A rigid matrix is a matrix with a high hamming distance from all low-rank matrices. It is a long-standing open question to give explicit constructions of rigid matrices with strong enough parameters. The question of constructing rigid matrices can also be interpreted as the question of proving average-case lower bounds against low-rank matrices.

• In [Alman-Chen’19], Josh Alman and I gave a semi-explicit construction of rigid matrices in a particular regime of parameters, for which no non-trivial constructions were known before.
  Formally, we constructed a \(\mathsf{P}^{\mathsf{NP}}\) machine \(M\) such that for infinite many integer \(n\), \(M(1^n)\) outputs an \(n \times n\) matrix which has \(\Omega(n^2)\) hamming distance to all matrices with rank at most \(2^{(\log n)^{1/4-\varepsilon}}\) over \(\mathbb{F}_2\), for some \(\varepsilon > 0\). This work is a surprising instantiation of the algorithmic method in a very non-standard computational model (low-rank matrices are very different from usual circuits).

• In a follow-up work [Bhangale-Harsha-Paradise-Tal’20], Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal significantly improved (and simplified) our construction. In particular, they improved the rank parameter from \(2^{(\log n)^{1/4-\varepsilon}}\) to \(2^{\log n / \Omega(\log \log n)}\), which is extremely close to a polynomial rank.

• In [Chen-Lyu-Williams’20], we managed to improve the above construction from infinite-often to almost-everywhere. That is, building on [Bhangale-Harsha-Paradise-Tal’20], we constructed a \(\mathsf{P}^{\mathsf{NP}}\) machine \(M\) such that for all large enough integer \(n\), \(M(1^n)\) outputs an \(n \times n\) matrix which has \(\Omega(n^2)\) hamming distance to all matrices with rank at most \(2^{\log n/\Omega(\log\log n)}\).

• In [Chen-Lyu’21], we further improve the hamming distance parameter above from just \(\Omega(n^2)\) to \((1/2 - o(1)) \cdot n^2\). We also obtained a rigidity-rank trade-off.
  A concurrent work by [Huang-Viola’21] also improved the hamming distance parameter, with a worse rigidity-rank trade-off than us.

3. Almost-Everywhere Circuit Lower Bounds via Algorithmic Method

• All previous lower bounds proved via the algorithmic method are infinitely-often. That is, for a specific hard function \(f\), they only guarantee that \(f\) is hard on infinitely many input lengths. Ideally, one would want \(f\) to be hard on all sufficiently large input lengths. There are attempts to addresses this issue, in Fortnow-Santhanam’11, an intermediate notion called significant separation was introduced, and it is showed that \(\mathsf{NEXP} \not\subset \mathsf{ACC}^0\) can be made to a significant separation.

• In [Chen-Lyu-Williams’20], we proved \(\mathsf{E}^{\mathsf{NP}} \not\subset i.o.\textrm{-}\mathsf{ACC}^0\), which is the first almost-everywhere separation proved via the algorithmic method. Our framework can also be used to extend several other known infinite-often lower bounds to almost-everywhere lower bounds. Besides the construction of rigid matrices mentioned above, we also proved that there is a function \(f \in \mathsf{E}^{\mathsf{NP}}\) which cannot be \(1/2+1/2^{n^{o(1)}}\)-approximated by \(2^{n^{o(1)}}\)-size \(\mathsf{ACC}^0\) circuits, on all sufficiently large input lengths.

4. Tighter Connections between Circuit-Analysis Algorithms and Circuit Lower Bounds

• In previous work on the circuit-analysis-algorithms-to-circuit-lower-bounds connection, to prove a lower bound for \(\mathcal{C}\) circuits, one usually has to design algorithms for \(\widetilde{\mathcal{C}}\) circuits, where \(\widetilde{\mathcal{C}}\) is a circuit class larger than \(\mathcal{C}\).

• In [Chen-Williams’19], we drew a connection from PCP of Proximity (PCPP), and showed a tighter connection between circuit-analysis algorithms and circuit lower bounds: To prove lower bounds for \(\mathcal{C}\) circuits, it suffices to start from a non-trivial derandomization of an XOR (AND or OR also suffice) of two \(\mathcal{C}\) circuits. The PCPP based techniques in this paper turned out to be very useful in subsequent work.