CS395T: Pseudorandomness (Fall 2017)

Logistics: TTh 11-12:30
GDC 4.516
Unique Number: 51910
Course web page: http://www.cs.utexas.edu/~diz/395T
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Phone: 471-9729
Office Hours: M 3:30-4:30, W 2:30-3:30
TA: Akshay Kamath
Email: kamath@cs.utexas.edu
Office: GDC 1.302
Office Hours: F 10:30-11:30
Course Overview: Randomization is extremely useful in almost all areas of computer science, such as algorithms, cryptography, and distributed computing. Can we derandomize algorithms, i.e., convert randomized algorithms into deterministic algorithms? Can we save random bits for tasks that do require randomness? How can we get randomness, when the easily accessible sources of randomness have little entropy? What does it mean for a fixed object, such as a graph, to be "random-like"?

In this course, we will study these and related questions. Our explorations will lead us to several important, related pseudorandom objects: pseudorandom generators, expander graphs, randomness extractors, and error-correcting codes. A tentative list of topics follows.

Basics: Randomized algorithms, basic coding theory, k-wise independence, small-bias spaces.

Expander Graphs: Chernoff bound for random walks, explicit constructions, SL=L.

Randomness Extractors: Seeded vs. seedless extractors, relation to expanders, constructions.

Polynomial Method and List Decoding: List decoders for RS codes and Parvaresh-Vardy codes, uses for extractors, Kakeya sets and mergers, capset problem.

Unconditional PRGs: Fourier analysis, PRG for polynomials, AC0, and Space-Bounded Computation.

PRGs and Hardness: cryptographic setting, derandomization setting, extractors from black-box PRGs, PRGs from shrinkage.

Two-Source Extractors and Ramsey Graphs: Recent constructions using nonmalleable extractors and resilient functions.

Useful References: The main text for this class will be Salil Vadhan's Pseudorandomness survey/monograph.
My 2001 class with lecture notes.
Simons Institute Pseudorandomness Boot Camp videos.

Similar classes:
Salil Vadhan: Pseudorandomness
Amnon Ta-Shma: Expanders, Pseudorandomness and Derandomization (contains lecture notes)
Luca Trevisan: Pseudorandomness and combinatorial constructions (contains lecture notes)
Chris Umans: Pseudorandomness and combinatorial constructions
Valentine Kabanets: Pseudorandomness (contains lecture notes)

Guruswami, Rudra, and Sudan's book, Essential Coding Theory
Hoory, Linial, and 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 book, Analysis of Boolean Functions
Sanjeev Arora's lecture notes on Fourier analysis

Nisan and Zuckerman, Randomness is Linear in Space
Impagliazzo, Nisan, and Wigderson, Pseudorandomness for Network Algorithms
Braverman, Rao, Raz, and Yehudayoff, Pseudorandom Generators for Regular Branching Programs
Emanuele Viola, The Sum of d Small-Bias Generators Fools Polynomials of Degree d
Mark Braverman, Polylogarithmic Independence Fools AC0 Circuits
Alon, Goldreich, and Mansour, Almost k-wise independence versus k-wise independence
Luca Trevisan, Extractors and Pseudorandom Generators

Prerequisites: Mathematical and computational maturity, plus familiarity with the following topics:
  • Discrete Probability, including moments and deviation bounds of Markov, Chebyshev, and Chernoff;
  • Algebra, including vector spaces, eigenvectors/eigenvalues, and finite fields;
  • Complexity Theory, including P, NP, NP-completeness, and reductions;
  • Other: basic combinatorics and graph theory; exposure to some randomized algorithms.
Grading: 90%: Homework
10%: Participation
Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.

Submission policy: Homeworks are due at the beginning of class. No late homeworks will be accepted.
Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.
Laptops/Phones: The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you sit in the first row and only use them for class-related purposes. Other exceptions may be made in unusual circumstances. All phones must be silenced.
Students with
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.

Last modified: November 15, 2017.