CS 294-202 Pseudorandomness
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.
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.
Salil Vadhan - Pseudorandomness
Error Correcting Codes
Expander Graphs - Cheeger's Inequality, Zig-Zag Product, SL=L
Pseudorandom Generators - NW Construction
Connections between all the above
Derandomization of Small-Space Computation
Introduction + derandomizing an approximation algorithm Max-Cut
Error reduction + Intro to PRGs Lecture note
Construction of small biased distributions [AGHP] + Brief introduction to discrete Fourier analysis Lecture note
Error correcting codes, Code concatenation, Connections between small biased distributions and error correcting codes Lecture note
Expander Graphs - Combinatorial Definition, Existence using the Probabilistic Method Lecture note
Spectral Expansion Lecture note
Expander Mixing Lemma Lecture note
Random Walks on Expanders Lecture note
Zig-Zag Product Lecture note
SL=L Lecture note
Randomness Extractors: Definition, Existence of Seeded-Extractors, Leftover Hash Lemma Lecture note
Seeded-Extractors: Graph Theoretic View, Samplers Lecture note
Pseudorandom Generators: Next-Bit Unpredictability Lecture note
Pseudorandom Generators: the Nisan-Wigderson Construction Lecture note
Two-Source Extractor Lecture note
Simple Construction of Almost k-wise Independent Random Variables - Alon, Goldreich, Håstad, Peralta
Expander Graphs and Their Applications -- Hoory, Linial, Wigderson