Pseudorandomness
Fall 2023/24
About the course
Randomness plays a crucial role in computer science, along with its applications in fields like cryptography and coding theory. Understanding the extent to which randomness aids computation consists of deep and fundamental questions in complexity theory. Within this context, pseudorandomness is all about comprehending the attributes of randomness that effectively cater to our structural and computational requisites.
In this course, our attention will be directed towards two primary focal points within pseudorandomness: pseudorandom generators and randomness extractors. We will delve into the study of both classical and contemporary methods for constructing these objects. The techniques will be versatile: combinatorial, probabilistic, algebraic, and (Fourier-)analytic.
In the initial segment of the course, our focus will be on constructing k-wise independent distributions and small-bias sets. Subsequently, we will proceed to construct remarkably powerful pseudorandom generators that draw upon these foundational constructs for various computational models such as low-degree polynomials, low-depth circuits, and space bounded algorithms. We will then transition to the exploration of randomness extractors, with specific emphasis on seeded extractors and two-source extractors.
Technicalities
When and where
Lectures are on Thursdays 10:10-13:00 at Exact Sciences 315 and recitations by Itay Cohen on Thursdays 14:10-15:00 at Holcblat 7.
Grade
Half of the grade will be based on 4-5 homework assignments. The other half will be derived from a one-hour presentation each student will deliver at the semester's end, discussing a paper from a pre-determined list that is related to the course material (see list below). Homework submission will be in pairs if the the number of participants will be high enough.
Literature
We won't strictly follow a particular source; however, much of what we'll study can be found in the sources listed below. All of these are accessible for free online.
-
Pseudorandomness by Vadhan
-
Theory of unconditional pseudorandom generators by Hatami and Hoza
-
Recent progress on derandomizing space-bounded computation by Hoza
We will also partially follow many of the original papers. In the tentative syllabus below these are linked next to the relevant topic.
Syllabus (tentative)
Bounded independence
Construction of k-wise independent distributions
Tail bounds
PRGs for decision trees
Derandomizing balls into bins
Small bias sets
Probabilisitic method and Alon's lower bound
The powering construction (paper)
The Ben-Aroya and Ta-Shma Hermitian curve based construction (paper)
A brief introduction to Fourier analysis
PRGs for decision trees and width-2 branching programs
Construction of almost k-wise independent distributions
Viola's PRG for low degree polynomials (paper)
Random restrictions based PRGs
PRGs from polarized random walks (paper)
PRGs for any order permutation read once branching programs
The Forbes-Kelly PRG for any order read once branching programs (paper)
Space bounded derandomization
Nisan's PRG
BPL in SC (paper)
A quick introduction to expander graphs
The Impagliazzo-Nisan-Wigderson PRG
Error reduction for weighted PRGs (paper or this one)
Derandomizing medium width branching programs (paper and this one)
Seeded extractors
Dvir-Wigderson Kakeya based mergers (paper)
Guruswami-Umans-Vadhan condensers (paper)
Construction of seeded extractors
Multi-source extractors
Raz's two-source extractor (paper )
Bourgain's two-source extractor (exposition by Rao)
Barak-Impagliazzio-Wigderson extractors via additive number theory (paper)
List of papers for presentation
-
Concentration for limited independence via inequalities for the elementary symmetric polynomials
-
Extensions to the method of multiplicities with applications to Kakeya sets and mergers
-
Pseudorandom generators from the second Fourier level and applications to AC0 and parity gates
-
Improved pseudorandomness for unordered branching programs through local monotonicity
-
Non-malleable extractors with short seeds and applications to privacy amplification
-
Near optimal pseudorandom generators for constant depth read once formulas