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 kwise independent distributions and smallbias sets. Subsequently, we will proceed to construct remarkably powerful pseudorandom generators that draw upon these foundational constructs for various computational models such as lowdegree polynomials, lowdepth circuits, and space bounded algorithms. We will then transition to the exploration of randomness extractors, with specific emphasis on seeded extractors and twosource extractors.
Technicalities
When and where
Lectures are on Thursdays 10:1013:00 at Orenstein 110, and recitations by Itay Cohen on Thursdays 14:1015:00 at Holcblat 7. I will replace Itay in the first few weeks.
Grade
Half of the grade will be based on 34 homework assignments. The other half will be derived from a onehour presentation each student will deliver at the semester's end, discussing a paper from a predetermined list that is related to the course material (see list below). Homework submission and presentations 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 spacebounded 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.
Notes
I am in the process of writing notes for the course. You can find them here though keep in mind this is a draft and that I'll keep changing the notes. Other resources are as follows (organized by lectures):

For lectures 3 & 5 I am making use of these slides for the expander construction part and these for Reingold's theorem, SL = L.

For lecture 4 we use this note by Babai.

Lecture 56 mainly followed the slides on expander constructions and SL=L. The smallbias set powering construction presented in based on this paper. The Hermitian based construction is based on this paper.

Lecture 7 mainly follows chapter 2.12.3 in HatamiHoza's survey.

For lecture 8 (with the video failure) we followed the notes as well as this paper by Naor on Ramsey graph construction.

For the SaksZhou algorithm presented in lecture 9, I followed section 4 of this paper (see also Dean's talk at IAS).

Here is a link to the paper I've mentioned in the last lecture about tree evaluation in nearly logarithmic space.
YouTube channel
The lecture recordings are available on the course YouTube channel.
Problem sets
Syllabus (tentative)
A bird's eye view of pseudorandomness (1.5 weeks)
Bounded independence (1.5 week)
Construction of kwise independent distributions
Tail bounds
PRGs for decision trees
PRGs for combinatorial rectangles
Small bias sets (1.5 weeks)
Probabilisitic method and Alon's lower bound
The powering construction (paper)
The BenAroya and TaShma Hermitian curve based construction (paper)
Construction of almost kwise independent distributions
Viola's PRG for low degree polynomials (paper)
Randomness extractors (1 week)
DvirWigderson Kakeya based mergers (paper)
Space bounded derandomization (1.5 week)
Nisan's PRG
SaksZhou
Introduction to expander graphs (2 week)
Reingold's theorem SL = L (paper)
List of papers for presentation (needs to be updated)

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

Nonmalleable extractors with short seeds and applications to privacy amplification

Near optimal pseudorandom generators for constant depth read once formulas

Explicit binary tree codes with polylogarithmic size alphabet

Improved PRGs for combinatorial rectangles (requires login for the university)

Approximating iterated multiplication of stochastic matrices in small space

Nearoptimal derandomization of mediumwidth branching programs (builds on the paper above).

Locally testable codes with constant rate, distance, and locality