Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

In a recent breakthrough, C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901 proved that NQP = NTIMEn^{polylog (n) } cannot be computed by polynomial-size ACC⁰ circuits (constant-depth circuits consisting of AND/OR/MODₘ gates for a fixed constant m, a frontier class in circuit complexity). This was recently strengthened by L. Chen, FOCS 2019, IEEE, Piscataway, NJ, 2019, pp. 1281--1304 to that NQP cannot be (1/2+1/polylog (n) ) -approximated by polynomial-size ACC⁰ circuits. In this work we will prove that NQP cannot be (1/2+1/n^ (1) ) -approximated by polynomial-size ACC⁰ circuits. As a straightforward application, we obtain an infinitely often nondeterministic pseudorandom generator for polysize ACC⁰ circuits with sub-polynomial seed length. More generally, we establish a connection showing that, for a typical circuit class C, nontrivial deterministic algorithms estimating the acceptance probability of C circuits imply strong (1/2 + 1/n^ (1) ) average-case lower bounds against C circuits. We also apply this connection to prove new lower bounds against several subclasses of TC⁰ circuits (constant-depth circuits consisting entirely of majority gates), and show that nontrivial derandomization of MAJ MAJ would imply worst-case lower bounds for TC⁰₃ (MAJ MAJ MAJ), suggesting that TC⁰₃ lower bounds are probably within reach. Our two new important technical ingredients are (1) techniques from cryptography in NC⁰ B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput. , 36 (2006), pp. 845--888, and (2) probabilistic checkable proofs of proximity with NC¹-computable proofs.