CSS.413.1 Pseudorandomness

Instructor: 

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