Improved Pseudorandom Generators for 𝖠𝖢^0 Circuits
share
We show a new PRG construction fooling depth-d, size-m 𝖠𝖢^0 circuits within error ε, which has seed length O(log^d-1(m)log(m/ε)loglog(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 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 (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 𝖠𝖢^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).
READ FULL TEXT
