**Instructor**: Eshan Chattopadhyay

**Class schedule:** Tuesdays and Thursdays, 10:10-11:25am

**Location:** Bard Hall 140

**Office hours**: 10:30-11:30am on Mondays, Location: Gates 319

As we shall see in this course,

** Tentative list of topics**

- Basic topics: k-wise independence, basic coding theory, epsilon-bias spaces, hash functions
- Expander graphs: random walks, zig-zag product, SL=L
- Pseudorandom generators for derandomization: Nisan-Wigderson construction, Impagliazzo-Wigderson worst-case to average case reduction.
- Some unconditional derandomization: small depth-circuits, low degree polynomials, space-bounded computation
- Randomness Extractors: seeded and seedless extraction, connections to expanders, explicit constructions
- List-decoding: basics, explicit constructions of seeded extractors from list-decodable codes
- Non-malleable extractors: basics, introduction to privacy amplification, constructions
- Alternating extraction: basics, the flip-flop primitive, correlation breakers
- Extractors for independents sources, Ramsey graphs: constructions based on additive combinatorics, and newer ideas

- Lecture 1: Introductory lecture.
- Lecture 2: Pairwise independence, Pseudorandom generator definition. pdf
- Lecture 3: k-wise independence, small-biased distribution. pdf
- Lecture 4: Small-biased distribution, introduction to Fourier analysis on Abelian groups. pdf
- Lecture 5: Almost k-wise independence, Vazirani's XOR lemma pdf
- Lectures 6,7: The cap-set problem. Fourier analytic approach and new advances based on the polynomial method. (guest lectures by Bobby Kleinberg). pdf
- Lecture 8: Coding theory connections, introduction to polynomial codes. pdf
- Lecture 9: Unique decoding and list-decoding of Reed-Solomon codes, the Johnson bound.
- Lecture 10: Expander graphs, various notions of expansion pdf
- Lecture 11: Expanders continued, random walks on expanders, introduction to Extractors pdf
- Lecture 12: Seeded extractors, Leftover hash lemma pdf
- Lecture 13: More on seeded extractors, Samplers from extractors, a-expanding graphs pdf
- Lecture 14: a-expanding graphs from seeded extractors, Lossless condensers pdf
- Lecture 15, 16: Seeded extractors, lossless condensers, and optimal vertex expanders from list-decodable codes pdf pdf
- Lecture 17: Derandomizing space-bounded computation 1: basics pdf
- Lecture 18: Derandomizing space-bounded computation 2: Nisan type PRG, Nisan-Zuckerman PRG pdf
- Lecture 19: Parameters of Nisan-Zuckerman PRG, 2-source extractors: explicit construction based on the inner product function and Paley graphs pdf
- Lecture 20: Hardness vs Randomness paradigm 1: warm-up for Nisan-Wigderson PRG pdf
- Lecture 21: Hardness vs Randomness paradiigm 2: Nisan-Wigderson PRG pdf
- Lecture 22: Seeded extractors from Nisan-Wigderson style argument: Trevisan's Extractor. Explicit affine extractors based on the inner product function.
- Lecture 23: Explicit spectral expanders via the Zig-Zag product pdf
- Lecture 24: Constant-degree lossless vertex expanders pdf

An excellent reference for this course is the following book.

- Salil Vadhan. Pseudorandomness

- David Zuckerman: Pseudorandomness
- David Zuckerman: Pseudorandomness and Combinatorial Constructions
- Luca Trevisan: Pseudorandomness and Combinatorial Constructions
- Salil Vadhan: Pseudorandomness
- Chris Umans: Pseudorandomness and combinatorial constructions
- Amnon Ta-Shma: Expanders, Pseudorandomness and Derandomization
- Valentine Kabanets: Pseudorandomness

- Some notes on Algebra by Madhu Sudan.
- A very brief review of Linear Algebra by Luca Trevisan.
- The book Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan is an excellent source for the prerequisite probability theory background for this course. Some notes on probability by Luca Trevisan.
- Expander graphs by Shlomo Hoory, Nati Linial, and Avi Wigderson.
- An introdury survey to Boolean Fourier Analysis by Ryan O'Donnell. For an in-depth study of the subject, a link to the book Analysis of Boolean functions by Ryan.
- Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan
- Modern Cryptography, Probabilistic Proofs, and Pseudorandomness by Oded Goldreich
- A survey on derandomization by Peter Bro Miltersen.
- A survey on random walks on graphs by Lászlò Lovász.

- Some introductory lectures on pseudorandomness as part of a Pseudorandomness Bootcamp workshop at the Simons Institute.
- A talk by Avi Wigderson on Randomness and Pseudorandomness.
- Avi Wigderson's talk on randomness extractors.

- Cayley expanders and the zig-zag product. Tjaden Hess, Linus Setiabrata, Cosmo Viola. pdf
- Pseudorandom generators from the Fourier spectrum. Jason Gaitonde. pdf
- Concentration of measure in the matrix-valued dependent setting. Juan C. Martinez Mori, Ayush Sekhari. pdf
- Easy witness and hard circuit lower bounds. Shawn Ong. pdf
- Towards derandomizing RL via graph connectivity. Jyun-Jie Liao and Wei-Kai Lin. pdf