Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

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 NEXP is contained in i.o.-NP; that is, it is open whether nondeterministic exponential time computation can be simulated on infinitely many input lengths by an NP algorithm. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. [Murray and Williams, STOC 2018] proved that nondeterminstic quasi-polynomial time is not contained in ACCˆ0, while it remained an open problem to show that EˆNP (2ˆO(n) time with an NP oracle) is not contained in i.o.-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.

First, we show there is a function f in EˆNP such that, for all sufficiently large input lengths n, f cannot be (1/2+exp(-nˆe))-approximated by exp(nˆe)-size ACCˆ0 circuits on inputs of length n (for all small e), improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020]. Second, we construct rigid matrices in PˆNP for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al. 2020].

Third, we show there is a positive c such that EˆNP has constant-error probabilistic degree at least cn/(logˆ2 n) for all large enough n, improving an infinitely-often separation by [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, 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 PCP of proximity ideas 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 ACCˆ0 circuits with seed length polylog(n), which resolves an open question in [Chen and Ren, STOC 2020].