Description
We show a new PRG construction fooling depth-d, size-m AC0 circuits within error ε, which has seed length O(log{d-1}(m) log(m/ε) loglog(m)). Our PRG improves on previous work [TX13 ,ST19, Kel21] from various aspects. It has optimal dependence on 1/ε and is only one "loglog(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 use 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, the partitioning approach avoids the extra "log(n)" factor that usually arises from the Ajtai-Wigderson framework, allowing us to get the almost-tight seed length. The partitioning 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.