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

**Textbook:**

Salil Vadhan - Pseudorandomness

**Problem Sets:**

Homework 1 - Due Monday, Sep 20.

Homework 2 - Due Wednesday, Oct 6.

Homework 3 - Due Thursday, Oct 21.

Homework 4 - Due Thursday, Nov 18.

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

Introduction + derandomizing an approximation algorithm Max-Cut Lecture note

k-wise independence Lecture note

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

Trevisan's Extractor Lecture note

Two-Source Extractor Lecture note

**Derandomizing Small-Space Computation:**

Nisan's PRG Lecture note

Nisan-Zuckerman's PRG Lecture note

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

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

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

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

Fractional PRGs and Polarizing Random Walks Lecture note

**Student Final Projects****:**

Survey of Interlacing Families for Bipartite Ramanujan Graphs by

Pseudorandom Walks: 2006 and Now by Nathaniel Young and Vint Lee

Fractional Pseudorandom Generators from Any Fourier Level by Ishaq Aden-Ali and Nathan Ju

Fooling Polytopes by Isaac Merritt, Justin Yokota, and Yuwen Zhang

Constructions of near-Ramanujan Graphs by Andrew Lin and Ansh Nagda

PRGs for Polynomial Threshold Functions by Thiago Bergamaschi and Yinuo Zhang

Expander Random Walks: A Fourier-Analytic Approach by Devon Ding and Xin Lyu

PRGs for Monotone Read-Once Branching Programs by Zoë Bell and Malvika Raj

Computational Extractors & Applications by Jialin Li and Dhanya Jayagopal

**Additional Reading****:**

Simple Construction of Almost k-wise Independent Random Variables by Alon, Goldreich, Håstad, Peralta

Expander Graphs and Their Applications by Hoory, Linial, Wigderson