Algorithmic Method for Proving Circuit Lower Bounds
The algorithmic approach, which connects algorithm design to circuit lower bounds, lies behind the recent breakthrough result that \(\mathsf{NEXP} \not\subset \mathsf{ACC}^0\) [Wil’14]. The most notable part of this approach is it seems to avoid all previous barriers for circuit lower bounds, and puts together nearly every gem in complexity theory, ranging from time hierarchy theorem to \(\mathsf{IP} = \mathsf{PSPACE}\). A recent breakthrough [Murray-Williams’18] significantly improved the state-of-the-art lower bounds from the paradigm by showing \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}] \not\subset \mathsf{ACC}^0\).
Some of my papers are devoted to obtaining better circuit lower bounds using the algorithmic method. They are summarized below.
1. 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 draw connection from PCP of Proximity (PCPP), and show a tighter connetion between circuit-analysis algorithms and circuit lower bounds: In order 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 following subsequent work.
2. Average-Case Circuit Lower Bounds from Algorithmic Method
Most previous work using algorithmic method can only achieve worst-case lower bounds. While average-case lower bounds (w.r.t. uniform distribution) have more applications espeically for building PRGs. R.Chen-Oliveira-Santhanam’18 took the first step in that direction and proved that \(\mathsf{NEXP}\) cannot be \(1/2 + 1/\mathrm{polylog}(n)\)-approximated by \(\mathsf{ACC}^0\).
In [Chen’19], we proved that \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}]\) cannot be \(1/2 + 1/\mathrm{polylog}(n)\)-approximated by \(\mathsf{ACC}^0\), improving on both of [R.Chen-Oliveira-Santhanam’18] and [Murray-Williams’18].
In [Chen-Ren’20], building crucially on [Chen-Williams’19] and [Chen’19], we proved that \(\mathsf{NTIME}[n^{\mathrm{polylog}(n)}]\) cannot be \(1/2 + 1/\mathrm{poly}(n)\)-approximated by \(\mathsf{ACC}^0\).
3. Construction of Rigid Matrices using Algorithmic Method
4. Almost-Everywhere Circuit Lower Bounds via Algorithmic Method
All previous lower bounds proved via the algorithmic method are infinitely-often. That is, for a certain hard function \(f\), they only guarantee that \(f\) is hard for 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. For example, 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.