Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
Lijie Chen, Hanlin Ren · SIAM Journal on Computing · 2022
In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901] proved that ${NQP} = {NTIME}[n^{{polylog}(n)}]$ cannot be computed by polynomial-size ${ACC}^0$ circuits (constant-depth circuits consisting of ${AND}$/${OR}$/${MOD}_m$ 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}^0$ circuits. In this work we will prove that ${NQP}$ cannot be $(1/2+1/n^{\omega(1)})$-approximated by polynomial-size ${ACC}^0$ circuits. As a straightforward application, we obtain an infinitely often nondeterministic pseudorandom generator for polysize ${ACC}^0$ circuits with sub-polynomial seed length. More generally, we establish a connection showing that, for a typical circuit class $\mathscr{C}$, nontrivial deterministic algorithms estimating the acceptance probability of $\mathscr{C}$ circuits imply strong ($1/2 + 1/n^{\omega(1)}$) average-case lower bounds against $\mathscr{C}$ circuits. We also apply this connection to prove new lower bounds against several subclasses of ${\sf TC}^0$ circuits (constant-depth circuits consisting entirely of majority gates), and show that nontrivial derandomization of ${MAJ} \circ {MAJ}$ would imply worst-case lower bounds for ${TC}^0_3$ (${MAJ} \circ{MAJ} \circ {MAJ}$), suggesting that ${TC}^0_3$ lower bounds are probably within reach. Our two new important technical ingredients are (1) techniques from cryptography in ${NC}^0$ [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845--888], and (2) probabilistic checkable proofs of proximity with ${NC}^1$-computable proofs.