CS395T: Pseudorandomness (Fall 2009)

Syllabus: Syllabus
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: TAY 3.134
Phone: 471-9729
Office Hours: W 2-3pm
Course Topics:

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).

Main References: Salil Vadhan's pseudorandomness survey: Part 1 and Part 2
Earlier versions of this class: 2003 and 2001 with lecture notes.
Similar Classes: Salil Vadhan: Pseudorandomness
Luca Trevisan: Pseudorandomness and combinatorial constructions (contains lecture notes)
Chris Umans: Pseudorandomness and combinatorial constructions
Valentine Kabanets: Pseudorandomness (contains lecture notes)
Surveys: Madhu Sudan's 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
Original Papers: Emanuele Viola, 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
Assignments: Problem Set #1
Problem Set #2
Problem Set #3

Last modified: November 14, 2009.