Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR23-019 | 14th April 2023 02:01

Theory of Unconditional Pseudorandom Generators

RSS-Feed




Revision #2
Authors: Pooya Hatami, William Hoza
Accepted on: 14th April 2023 02:01
Downloads: 1324
Keywords: 


Abstract:

This is a survey of unconditional *pseudorandom generators* (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that "fools" the model, meaning that every function computable in the model behaves approximately the same when we plug in pseudorandom bits from the PRG as it does when we plug in truly random bits. In this survey, we discuss four major paradigms for designing PRGs:

- We present several PRGs based on $k$-wise uniform generators, small-bias generators, and simple combinations thereof, including proofs of Viola's theorem on fooling low-degree polynomials (Comput. Complexity 2009) and Braverman's theorem on fooling $\mathbf{AC}^0$ circuits (J. ACM 2010).

- We present several PRGs based on "recycling" random bits to take advantage of communication bottlenecks, such as the Impagliazzo-Nisan-Wigderson generator (STOC 1994).

- We present connections between PRGs and computational hardness, including the Nisan-Wigderson framework for converting a hard Boolean function into a PRG (J. Comput. Syst. Sci. 1994).

- We present PRG frameworks based on random restrictions, including the "polarizing random walks" framework (Chattopadhyay, Hatami, Hosseini, and Lovett, Theory Comput. 2019).

We explain how to use these paradigms to construct PRGs that work *unconditionally*, with no unproven mathematical assumptions. The PRG constructions use ingredients such as finite field arithmetic, expander graphs, and randomness extractors. The analyses use techniques such as Fourier analysis, sandwiching approximators, and simplification-under-restrictions lemmas.



Changes to previous version:

Minor corrections.


Revision #1 to TR23-019 | 14th March 2023 20:05

Theory of Unconditional Pseudorandom Generators





Revision #1
Authors: Pooya Hatami, William Hoza
Accepted on: 14th March 2023 20:05
Downloads: 251
Keywords: 


Abstract:

This is a survey of unconditional *pseudorandom generators* (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that "fools" the model, meaning that every function computable in the model behaves approximately the same when we plug in pseudorandom bits from the PRG as it does when we plug in truly random bits. In this survey, we discuss four major paradigms for designing PRGs:

- We present several PRGs based on $k$-wise uniform generators, small-bias generators, and simple combinations thereof, including proofs of Viola's theorem on fooling low-degree polynomials (Comput. Complexity 2009) and Braverman's theorem on fooling $\mathbf{AC}^0$ circuits (J. ACM 2010).

- We present several PRGs based on "recycling" random bits to take advantage of communication bottlenecks, such as the Impagliazzo-Nisan-Wigderson generator (STOC 1994).

- We present connections between PRGs and computational hardness, including the Nisan-Wigderson framework for converting a hard Boolean function into a PRG (J. Comput. Syst. Sci. 1994).

- We present PRG frameworks based on random restrictions, including the "polarizing random walks" framework (Chattopadhyay, Hatami, Hosseini, and Lovett, Theory Comput. 2019).

We explain how to use these paradigms to construct PRGs that work *unconditionally*, with no unproven mathematical assumptions. The PRG constructions use ingredients such as finite field arithmetic, expander graphs, and randomness extractors. The analyses use techniques such as Fourier analysis, sandwiching approximators, and simplification-under-restrictions lemmas.



Changes to previous version:

Minor changes including a corrected reference in Section 2.4.


Paper:

TR23-019 | 2nd March 2023 00:04

Theory of Unconditional Pseudorandom Generators





TR23-019
Authors: Pooya Hatami, William Hoza
Publication: 3rd March 2023 01:09
Downloads: 1031
Keywords: 


Abstract:

This is a survey of unconditional *pseudorandom generators* (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that "fools" the model, meaning that every function computable in the model behaves approximately the same when we plug in pseudorandom bits from the PRG as it does when we plug in truly random bits. In this survey, we discuss four major paradigms for designing PRGs:

- We present several PRGs based on $k$-wise uniform generators, small-bias generators, and simple combinations thereof, including proofs of Viola's theorem on fooling low-degree polynomials (Comput. Complexity 2009) and Braverman's theorem on fooling $\mathbf{AC}^0$ circuits (J. ACM 2010).

- We present several PRGs based on "recycling" random bits to take advantage of communication bottlenecks, such as the Impagliazzo-Nisan-Wigderson generator (STOC 1994).

- We present connections between PRGs and computational hardness, including the Nisan-Wigderson framework for converting a hard Boolean function into a PRG (J. Comput. Syst. Sci. 1994).

- We present PRG frameworks based on random restrictions, including the "polarizing random walks" framework (Chattopadhyay, Hatami, Hosseini, and Lovett, Theory Comput. 2019).

We explain how to use these paradigms to construct PRGs that work *unconditionally*, with no unproven mathematical assumptions. The PRG constructions use ingredients such as finite field arithmetic, expander graphs, and randomness extractors. The analyses use techniques such as Fourier analysis, sandwiching approximators, and simplification-under-restrictions lemmas.



ISSN 1433-8092 | Imprint