Improved Pseudorandom Generators for AC0 Circuits

Xin Lyu

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2024-212

December 13, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-212.pdf

We show a new PRG construction fooling depth-d, size-m AC0 circuits within error eps, which has seed length O(log^{d-1}(m) log(m/\eps) loglog(m)). Our PRG improves on previous work [TX13,ST19,Key21] from various aspects. It has optimal dependence on 1/eps 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,Key21], we prove a full derandomization of the powerful multi-switching lemma [Hastad14]. 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.

Advisors: Jelani Nelson and Avishay Tal

BibTeX citation:

@mastersthesis{Lyu:EECS-2024-212,
    Author= {Lyu, Xin},
    Title= {Improved Pseudorandom Generators for AC0 Circuits},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-212.html},
    Number= {UCB/EECS-2024-212},
    Abstract= {We show a new PRG construction fooling depth-d, size-m AC0 circuits within error eps, which has seed length O(log^{d-1}(m) log(m/\eps) loglog(m)). Our PRG improves on previous work [TX13,ST19,Key21] from various aspects. It has optimal dependence on 1/eps 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,Key21], we prove a full derandomization of the powerful multi-switching lemma [Hastad14]. 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.},
}

EndNote citation:

%0 Thesis
%A Lyu, Xin 
%T Improved Pseudorandom Generators for AC0 Circuits
%I EECS Department, University of California, Berkeley
%D 2024
%8 December 13
%@ UCB/EECS-2024-212
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-212.html
%F Lyu:EECS-2024-212