Strong average-case lower bounds from non-trivial derandomization

L Chen, H Ren - Proceedings of the 52nd Annual ACM SIGACT …, 2020 - dl.acm.org
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020dl.acm.org
We prove that for all constants a, NQP= NTIME [n polylog (n)] cannot be (1/2+ 2− log an)-
approximated by 2log an-size ACC 0∘ THR circuits (ACC 0 circuits with a bottom layer of
THR gates). Previously, it was even open whether E NP can be (1/2+ 1/√ n)-approximated
by AC 0 [⊕] circuits. As a straightforward application, we obtain an infinitely often (NE∩
coNE)/1-computable pseudorandom generator for poly-size ACC 0 circuits with seed length
2logє n, for all є> 0. More generally, we establish a connection showing that, for a typical …
We prove that for all constants a, NQP = NTIME[n polylog(n)] cannot be (1/2 + 2−log a n )-approximated by 2log a n -size ACC 0THR circuits ( ACC 0 circuits with a bottom layer of THR gates). Previously, it was even open whether E NP can be (1/2+1/√n)-approximated by AC 0[⊕] circuits. As a straightforward application, we obtain an infinitely often ( NEcoNE)/1-computable pseudorandom generator for poly-size ACC 0 circuits with seed length 2logє n , for all є > 0.
More generally, we establish a connection showing that, for a typical circuit class C, non-trivial nondeterministic algorithms estimating the acceptance probability of a given S-size C circuit with an additive error 1/S (we call it a CAPP algorithm) imply strong (1/2 + 1/n ω(1)) average-case lower bounds for nondeterministic time classes against C circuits. Note that the existence of such (deterministic) algorithms is much weaker than the widely believed conjecture PromiseBPP = PromiseP.
We also apply our results to several sub-classes of TC 0 circuits. First, we show that for all k, NP cannot be (1/2 + n k )-approximated by n k -size SumTHR circuits (exact ℝ-linear combination of threshold gates), improving the corresponding worst-case result in [Williams, CCC 2018]. Second, we establish strong average-case lower bounds and build ( NEcoNE)/1-computable PRGs for SumPTF circuits, for various regimes of degrees. Third, we show that non-trivial CAPP algorithms for MAJMAJ indeed already imply worst-case lower bounds for TC 3 0 ( MAJMAJMAJ). Since exponential lower bounds for MAJMAJ are already known, this suggests TC 3 0 lower bounds are probably within reach.
Our new results build on a line of recent works, including [Murray and Williams, STOC 2018], [Chen and Williams, CCC 2019], and [Chen, FOCS 2019]. In particular, it strengthens the corresponding (1/2 + 1/polylog(n))-inapproximability average-case lower bounds in [Chen, FOCS 2019].
The two important technical ingredients are techniques from Cryptography in NC 0 [Applebaum et al., SICOMP 2006], and Probabilistic Checkable Proofs of Proximity with NC 1-computable proofs.
ACM Digital Library