CS395T: Pseudorandomness (Spring 2003)

Syllabus: Syllabus.
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: TAY 3.134
Phone: 471-9729
Office Hours: TTh 5:00-6:00, or by appointment
Problem Sets: Problem Set #1
Problem Set #2
Useful Books and Lecture Notes: My 2001 lecture notes cover much of the course material.
Salil Vadhan's lecture notes for Pseudorandomness;
Oded Goldreich's book, Modern Cryptography, "Probabilistic Proofs and Pseudorandomness";
Peter Bro Miltersen's book chapter, "Derandomizing Complexity Classes";
Madhu Sudan's
Course Notes on Coding Theory;
Nati Linial and Avi Wigderson's course, Expanders and Their Applications;
David Aldous and Jim Fill's book, Reversible Markov Chains and Random Walks on Graphs.
Relevant Talks: Extractors for Weak Random Sources and their Applications
Codes in Theoretical Computer Science
Relevant Papers: D. Koller and N. Megiddo, Constructing small sample spaces satisfying given constraints
D.R. Karger and D. Koller, (De)randomized construction of small sample spaces in NC
N. Alon, O. Goldreich, J. Hastad, and R. Peralta, Simple Constructions of Almost k-Wise Independent Random Variables, Addendum.
R. Impagliazzo and D. Zuckerman, How to Recycle Random Bits
N. Nisan, Extracting Randomness: How and Why -- A Survey
R. Shaltiel, Recent Developments in Explicit Constructions of Extractors
My extractor papers
N. Nisan and A. Wigderson, Hardness vs. Randomness
O. Goldreich and L. Levin, Hard-core Predicates for any One-way Function (Goldreich's revision)
R. Impagliazzo and A. Wigderson, Randomness vs. Time: De-randomization under a uniform assumption
R. Impagliazzo, N. Nisan, and A. Wigderson, Pseudorandomness for network algorithms
Presentation Tips: You may use transparencies or the blackboard or some combination. Some helpful tips are available in Ian Parberry's Speaker's Guide. Please allow 10 minutes at the end for questions and comments on the presentation.
Presentation Schedule: PCP and Unapproximability, Ned Dimitrov and Xiaozhou (Steve) Li, March 24, 26, 31, and April 2
Ned's slides for the talk
A. Shamir, IP=PSPACE
L. Babai, L. Fortnow, and C. Lund, Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
Sanjeev Arora's lecture notes on Fourier Analysis
Sanjeev Arora's Ph.D. thesis

Algebraic Extractors and Pseudorandom Generators, Anindya Patthak, April 7 and 9
Papers by Shaltiel & Umans and by Umans.

Cryptographic Applications, Atri Rudra, April 14 and 16
S. Vadhan, On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model
C. Lu, Encryption against storage-bounded adversaries from on-line strong extractors
Atri's slides for the talk

Deterministic Extractors for Symbol-Fixing Sources and Exposure-Resilient Cryptography, Jesse Kamp, April 21 and 23

Last modified: April 17, 2003