CS 294-202 Pseudorandomness

Course Description:

Randomized algorithms give a broad and rich algorithmic toolkit (e.g., sampling, Monte Carlo methods). Randomness is an essential resource in distributed computing, cryptography, and interactive proofs. In this course, we would explore the role of randomness in computation: Can we derandomize algorithms without changing their time or space complexity? Can we "purify" randomness from a weak source of randomness?

Pseudo-randomness is the property of "appearing random" while having little or no randomness. Pseudo-randomness plays a significant role in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. In this course, we will see all these beautiful applications. In the second part of the course, we would focus on the question of derandomization of small-space computation, also known as the "RL versus L" question. It asks whether all problems that can be decided in randomized logarithmic space (RL) can also be decided in deterministic logarithmic space (L). We would cover recent approaches towards showing that RL = L.

Undergraduate students who wish to take this class should fill out the following Google Form.

General Information:

Time and Place: Tuesday, Thursday 3:30-5:00 PM, Soda 405

Office Hours: Monday 3:00-4:00 PM (via Zoom).

Instructor: Avishay Tal, atal "at" berkeley.edu

TA: Kewen Wu, shlw_kevin [at] hotmail [dot] com

Grading: Homeworks - 40% (4 assignments), Final Project & Presentation - 50%, Scribes - 10%.

Prereqs: CS170 or equivalent is required.

Gradescope Piazza

Textbook:

Problem Sets:

Topics:

  • k-wise Independence

  • ε-Biased Distributions

  • Error Correcting Codes

  • Expander Graphs - Cheeger's Inequality, Zig-Zag Product, SL=L

  • Pseudorandom Generators - NW Construction

  • Randomness Extractors

  • Connections between all the above

  • Derandomization of Small-Space Computation

Lectures:

  1. Introduction + derandomizing an approximation algorithm Max-Cut Lecture note

  2. k-wise independence Lecture note

  3. Error reduction + Intro to PRGs Lecture note

  4. Construction of small biased distributions [AGHP] + Brief introduction to discrete Fourier analysis Lecture note

  5. Error correcting codes, Code concatenation, Connections between small biased distributions and error correcting codes Lecture note

  6. Expander Graphs - Combinatorial Definition, Existence using the Probabilistic Method Lecture note

  7. Spectral Expansion Lecture note

  8. Expander Mixing Lemma Lecture note

  9. Random Walks on Expanders Lecture note

  10. Zig-Zag Product Lecture note

  11. SL=L Lecture note

  12. Randomness Extractors: Definition, Existence of Seeded-Extractors, Leftover Hash Lemma Lecture note

  13. Seeded-Extractors: Graph Theoretic View, Samplers Lecture note

  14. Pseudorandom Generators: Next-Bit Unpredictability Lecture note

  15. Pseudorandom Generators: the Nisan-Wigderson Construction Lecture note

  16. Trevisan's Extractor Lecture note

  17. Two-Source Extractor Lecture note

Derandomizing Small-Space Computation:

  1. Nisan's PRG Lecture note

  2. Nisan-Zuckerman's PRG Lecture note

  3. Saks-Zhou: BPL in L^{3/2} Lecture note

  4. Ajtai-Wigderson Framework: Random-Restriction Based PRGs Lecture note

  5. Forbes-Kelley: Fooling Read-Once Branching Programs in any Order Lecture note

  6. Cheng-Hoza: Hitting Sets Give Two-Sided Derandomization of Small Space Lecture note

  7. Fractional PRGs and Polarizing Random Walks Lecture note

Student Final Projects:

Additional Reading: