CS 395T - Pseudorandomness and Combinatorial Constructions (Spring 2001)

Time/Location/Unique number. TTh 3:30-5:00, TAY 3.144, #51110.

Instructor. David Zuckerman (diz@cs.utexas.edu).

Course overview. Randomization is very useful in almost all areas of computer science, such as algorithms, cryptography, and distributed computing. These uses of randomness seem wonderful until one realizes that computers do not use truly random bits. Instead, most computers get their random bits by using pseudorandom generators. A pseudorandom generator is a deterministic algorithm that takes as input a short random seed and outputs a long string which is ``random'' enough for the purpose at hand.

In this course, we will develop provably good pseudorandom generators for a variety of tasks. Along the way, we will frequently require explicit combinatorial constructions. That is, we will want to efficiently and deterministically construct a combinatorial object whose existence is easily ensured by the probabilistic method. In fact, a pseudorandom generator is such an object.

Syllabus.

Lecture Notes.
Lecture 1: Introduction to Randomized Algorithms (Jan. 16)
Lecture 2: Randomized Algorithms for Equality and Primality (Jan. 18)
Lecture 3: Introduction to Pseudorandom Generators (Jan. 23)
Lecture 4: The Probabilistic Method (Jan. 25)
Lecture 5: Pairwise Independence (Jan. 30)
Lecture 6: Almost k-wise Independence (Feb. 1)
Lecture 7: Construction of Almost k-wise Independent Spaces (Feb. 6)
Lecture 8: Introduction to Coding Theory (Feb. 8)
Lecture 9: Codes, Epsilon-Biased Spaces, and Decoding (Feb. 13)
Lecture 10: List Decoding (Feb. 15)
Lecture 11: Expanders and Eigenvalues (Feb. 20)
Lecture 12: Random Walks on Expanders (Feb. 22)
Lecture 13: Diameter, Girth, and Expansion (Feb. 27)
Lecture 14: Zig-Zag Product and Expanders (March 1)
Lecture 15: The Leftover Hash Lemma and Its Uses (March 6)
Lecture 16: Randomized Space-Bounded Computation (March 8)
Lecture 17: Pseudorandom Generators for Space-Bounded Computation (March 20)
Lecture 18: Pseudorandom Generators for Space-Bounded Computation (continued) (March 22)
Lecture 19: Pseudorandom Generators from Hard Functions (March 27)
Lectures 20 and 21: Average Case Hardness and Hardcore Predicates (March 29 and April 3)
Lectures 21 and 22: Extractors and their Applications (April 3 and 5)
Lecture 23: Trevisan's Extractor (April 10)
Lecture 24: Loss-less Condensers (April 12)
Lecture 25: Applications of Extractors (April 17)

Problem Sets.
Problem Set #1
Problem Set #2
Problem Set #3
Problem Set #4
See the 2003 version of this course for more problem sets.

Useful References.
M. Luby and A. Wigderson, Pairwise Independence and Derandomization (Lectures 5, 11, 12, 15, 17, 18)
D. Zuckerman, Survey talk on extracting randomness (Lectures 15, 21, 22, and 25)
N. Alon, O. Goldreich, J. Hastad, and R. Peralta, Simple Constructions of Almost k-Wise Independent Random Variables (Lecture 7)
M. Sudan, Decoding of Reed-Solomon Codes Beyond the Error-Correction Bound (Lecture 10)
R. Impagliazzo and D. Zuckerman, How to Recycle Random Bits (Lectures 12 and 15)
D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs (book) (Lectures 12 and 16)
O. Reingold, S. Vadhan, and A. Wigderson, Entropy Waves, the Zig-Zag Product, and New Constant-Degree Expanders and Extractors (Lecture 14)
N. Nisan, RL is contained in SC (Lectures 17 and 18)
N. Nisan and A. Wigderson, Hardness vs. Randomness (Lecture 19)
O. Goldreich, Three XOR-Lemmas -- an Exposition (Lecture 21)
L. Trevisan, Extractors and Pseudorandom Generators (Lecture 23)
A. Ta-Shma, C. Umans, and D. Zuckerman, Unbalanced Expanders and Improved Extractors and Dispersers (Lecture 24)
N. Nisan and D. Zuckerman, Randomness is Linear in Space (Lecture 25)
A. Ta-Shma and D. Zuckerman, Extractor Codes (Lecture 25)

Projects (unedited by me).
Jean-Philippe Martin's presentation of Pseudorandomness for Network Algorithms
Vladimir Trifonov's presentation of the Gabber-Galil expander construction.
Joel Tropp's presentation of On the Second Eigenvalue and Linear Expansion of Regular Graphs
KJ Balakrishnan's presentation and Peiyush Jain's presentation of Ramsey graph constructions.