In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely many input lengths by $\mathrm{NP}$ algorithms. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. In particular, although [Murray and Williams, STOC 2018] proved $\mathrm{NTIME}[2^{\mathrm{polylog}(n)}] \not\subset \mathrm{ACC}^0$, it has remained an open problem to show that $\mathrm{E}^{\mathrm{NP}}$ ($2^{O(n)}$ time with an $\mathrm{NP}$ oracle) is not contained in $\mathrm{i.o.-}\mathrm{ACC}^0$.
In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds.
- We show there is a function $f \in \mathrm{E}^{\mathrm{NP}}$ such that for all sufficiently large input lengths $n$ and $\varepsilon \leq o(1)$, $f$ cannot be $(1/2+2^{-n^{\varepsilon}})$-approximated by $2^{n^\varepsilon}$-size $\mathrm{ACC}^0$ circuits on inputs of length $n$, improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020].
- We construct rigid matrices in $\mathrm{P}^{\mathrm{NP}}$ for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al., FOCS 2020].
- We show there are functions in $\mathrm{E}^{\mathrm{NP}}$ requiring constant-error probabilistic degree at least $\Omega(n/\log^2 n)$ for all large enough $n$, improving an infinitely-often separation of [Viola, ECCC 2020].
Our key to proving almost-everywhere worst-case lower bounds is a new ``constructive'' proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every ``weak'' nondeterminstic algorithm (with smaller running-time and short witness), a ``refuter algorithm'' exists that can construct ``bad'' inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with the PCP-of-proximity applications developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size $\mathrm{ACC}^0$ circuits with seed length $\mathrm{polylog}(n)$, which resolves an open question in [Chen and Ren, STOC 2020].
