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