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 nontrivial superpolynomial lower bounds against the frontier circuit class \(\mathsf{ACC^0}\) (which is the class of constantdepth circuits consisting of unbounded fanin \(\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 stateoftheart 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], [ChenRen’20], [ChenLyuWilliams’20], [ChenLyu’21], [AlmanChen’19], [ChenWilliams’19]) are devoted to obtaining stronger circuit lower bounds using the algorithmic method. They are summarized below.
1. AverageCase Circuit Lower Bounds from Algorithmic Method
Most previous work using the algorithmic method can only achieve worstcase lower bounds, although averagecase lower bounds (w.r.t. uniform distribution) have more applications, including constructions of pseudorandom generators. In [R.ChenOliveiraSanthanam’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 polysize \(\mathsf{ACC}^0\).
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 [ChenRen’20], building crucially on [ChenWilliams’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 polysize \(\mathsf{ACC}^0\), for every constant \(k\).
This is the first strong averagecase 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 polysize \(\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 [ChenRen’20] is only super polynomial, and an open question was whether one can show strong averagecase lower bounds against subexponentialsize \(\mathsf{ACC}^0\) circuits. In [ChenLyuWilliams’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 [ChenRen’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 [ChenLyuWilliams’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 [ChenLyu’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
In [AlmanChen’19], Josh Alman and I gave a semiexplicit construction of rigid matrices in a particular regime of parameters, for which no nontrivial 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 nonstandard computational model (lowrank matrices are very different from usual circuits).
In a followup work [BhangaleHarshaParadiseTal’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 [ChenLyuWilliams’20], we managed to improve the above construction from infiniteoften to almosteverywhere. That is, building on [BhangaleHarshaParadiseTal’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 [ChenLyu’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 rigidityrank tradeoff.
A concurrent work by [HuangViola’21] also improved the hamming distance parameter, with a worse rigidityrank tradeoff than us.
3. AlmostEverywhere Circuit Lower Bounds via Algorithmic Method
All previous lower bounds proved via the algorithmic method are infinitelyoften. 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 FortnowSanthanam’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 [ChenLyuWilliams’20], we proved \(\mathsf{E}^{\mathsf{NP}} \not\subset i.o.\textrm{}\mathsf{ACC}^0\), which is the first almosteverywhere separation proved via the algorithmic method. Our framework can also be used to extend several other known infiniteoften lower bounds to almosteverywhere 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 CircuitAnalysis Algorithms and Circuit Lower Bounds
In previous work on the circuitanalysisalgorithmstocircuitlowerbounds 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 [ChenWilliams’19], we drew a connection from PCP of Proximity (PCPP), and showed a tighter connection between circuitanalysis algorithms and circuit lower bounds: To prove lower bounds for \(\mathcal{C}\) circuits, it suffices to start from a nontrivial 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.
