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 Project |