Improved Pseudorandom Generators for ${\mathsf{AC}}^0$ Circuits

Abstract

We show a new PRG construction fooling depth-$d$, size-$m$ ${\mathsf{AC}}^0$ circuits within error $\epsilon$, which has seed length $O({\log }^{d-1}(m)\log (m/\epsilon )\log \log (m))$. Our PRG improves on previous work (Trevisan and Xue 2013, Servedio and Tan 2019, Kelley 2021) from various aspects. It has optimal dependence on $\frac{1}{\epsilon }$ and is only one ``$\log \log (m)$'' away from the lower bound barrier. For the case of $d=2$, the seed length tightly matches the best-known PRG for CNFs (De et al. 2010, Tal 2017). There are two technical ingredients behind our new result; both of them might be of independent interest. First, we use a partitioning-based approach to construct PRGs based on restriction lemmas for ${\mathsf{AC}}^0$, which follows and extends the seminal work of (Ajtai and Wigderson 1989). Second, improving and extending prior works (Trevisan and Xue 2013, Servedio and Tan 2019, Kelley 2021), we prove a full derandomization of the powerful multi-switching lemma for a family of DNFs (Håstad 2014).

The conference version appeared in CCC2022