We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of 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/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, we obtain an infinitely often (NE cap coNE)_{/1}-computable pseudorandom generator for poly-size ACC^0 circuits with seed length 2^{log^{eps} n}, for all eps > 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^omega(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 Sum of THR circuits (exact R-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 (NE cap coNE)_{/1}-computable PRGs for Sum of PTF circuits, for various regimes of degrees. Third, we show that non-trivial CAPP algorithms for MAJ of MAJ indeed already imply worst-case lower bounds for TC^0_3 (MAJ of MAJ of MAJ). Since exponential lower bounds for MAJ of MAJ are already known, this suggests TC^0_3 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.

Fixed a subtle error about PRGs. Some minor revisions.

We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of 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/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, we obtain an infinitely often (NE cap coNE)_{/1}-computable pseudorandom generator for poly-size ACC^0 circuits with seed length 2^{log^{eps} n}, for all eps > 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^omega(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 Sum of THR circuits (exact R-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 (NE cap coNE)_{/1}-computable PRGs for Sum of PTF circuits, for various regimes of degrees. Third, we show that non-trivial CAPP algorithms for MAJ of MAJ indeed already imply worst-case lower bounds for TC^0_3 (MAJ of MAJ of MAJ). Since exponential lower bounds for MAJ of MAJ are already known, this suggests TC^0_3 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.