Office: TAY 3.134
Office Hours: W 2-3pm
Basics: Introduction, basic coding theory, k-wise independence (1-2 weeks).
Fourier Analysis: small-bias sets, almost k-wise independence, linearity test, PRG for polynomials (1-2 weeks).
Expander Graphs: connection with small-bias sets, Chernoff bound for random walks, explicit constructions, SL=L (2 weeks).
Randomness Extractors: Leftover Hash Lemma, relation to expanders, constructions (2 weeks).
PRGs for Space-Bounded Computation: PRGs from extractors and expanders (1 week).
Polynomial Method and List Decoding: List decoders for RS codes and Parvaresh-Vardy codes, uses for extractors, Kakeya sets and mergers (2 weeks).
Additive Number Theory: Sum-product theorem and incidence theorem, 1-bit condenser, 2-source extractor (1 week).
PRGs and Hardness: cryptographic setting and hardcore bits, derandomization setting, extractors from black-box PRGs (2 weeks).
Earlier versions of this class: 2003 and 2001 with lecture notes.
Luca Trevisan: Pseudorandomness and combinatorial constructions (contains lecture notes)
Chris Umans: Pseudorandomness and combinatorial constructions
Valentine Kabanets: Pseudorandomness (contains lecture notes)
lecture notes on coding theory|
S. Hoory, N. Linial, and A. Wigderson's survey, Expander Graphs and their Applications
Oded Goldreich's book, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness
Peter Bro Miltersen's book chapter, Derandomizing Complexity Classes
My talk on Codes in Theoretical Computer Science
Ryan O'Donnell's survey of Fourier analysis, Some Topics in Analysis of Boolean Functions
Sanjeev Arora's lecture notes on Fourier analysis
The sum of d small-bias generators fools polynomials of degree d
N. Alon, O. Schwartz, and A. Shapira, An Elementary Construction of Constant-Degree Expanders
Omer Reingold, Undirected Connectivity in Log-Space
R. Impagliazzo and D. Zuckerman, How to Recycle Random Bits
D. Zuckerman, Randomness-Optimal Oblivious Sampling
D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
N. Nisan and D. Zuckerman, Randomness is Linear in Space
R. Impagliazzo, N. Nisan, A. Wigderson, Pseudorandomness for Network Algorithms
Problem Set #1
Problem Set #2
Problem Set #3