We give PRG for depth-$d$, size-$m$ $\mathrm{AC}^0$ circuits with seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m))$. Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on $\frac{1}{\varepsilon}$ 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 [DETT10, Tal17].

There are two technical ingredients behind our new result; both of them might be of independent interest. First, we develop a “partitioning-based” approach to construct PRGs based on restriction lemmas for AC0. Previous works [TX13, ST19, Kel21] usually built PRGs on the Ajtai-Wigderson framework [AW89]. Compared with them, our new approach avoids the extra “$\log(n)$” factor that usually arises from the Ajtai-Wigderson framework, allowing us to get the almost-tight seed length. Our partitioning-based approach is quite general, and we believe it can help design PRGs for classes beyond constant-depth circuits.

Second, improving and extending [TX13, ST19, Kel21], we prove a full derandomization of the powerful multi-switching lemma [Hås14]. We show that one can use a short random seed to sample a restriction, such that a family of DNFs simultaneously simplifies under the restriction with high probability. This answers an open question in [Kel21]. Previous derandomizations were either partial (that is, they pseudorandomly choose variables to restrict, and then fix those variables to truly-random bits) or had sub-optimal seed length. In our application, having a fully-derandomized switching lemma is crucial, and the randomness-efficiency of our derandomization allows us to get an almost-tight seed length.