CSS.413.1 Pseudorandomness
Semester:
-
2021 Autumn/Monsoon (Aug - Dec)
- Course introduction
- What the course is about
- The power of randomness
- Basic probability inequalities
- Basic derandomization techniques
- Method of conditional expectation
- Limited independence
- Sampling using limited independence
- Constructing k-wise independent distributions
- Intro to random walks
- Epsilon-biased spaces and AGHP construction
- Expansion
- Linear algebra and random walks, spectral expansion, edge-expansion, vertex-expansion, EML
- Cheeger's inequality
- Applications to randomness-efficient sampling
- Hitting Set Lemma (KPS, AKS) and Chernoff Bound
- Explicit construction of expanders (squaring, tensoring, zig-zag)
- Pseudorandom generators
- intro to PRGs, application to almost k-wise indep.
- average case hardness, hybrid argument, Nisan-Wigderson generators Shaltiel-Umans
- optional topics: Hoza-Zuckerman hitting-sets for small-success RL, polarising random walks,
- PRGs for Space
- Nisan’s Generator
- INZ Generator
- Saks-Zhou derandomization of BPL
- Reingold's theorem (SL = L)
- Spectral sparsifiers
- Extractors
- Introduction to extractors, seeded-extractors
- Strong extractors, connection to hash functions, expanders
- Leftover Hash Lemma
- Block sources and extracting randomness from them
- Extractors for general sources with O(log n) seed
- Revisiting Nisan's PRG for Trevisan's extractor
- Condensers / Mergers: GUV construction, unbalanced expanders
- Pseudorandomness Elsewhere
- Roth's theorem
- Green-Tao's result on APs within primes
- Pseudorandomness and Blackholes
- High-dimensional Expanders
