Pseudorandomness (2023-II)

(Tuesdays and Thursdays 1130 — 1300) @ A 201 and Zoom

This course will deal with various kinds of explicit objects that are “random-looking”, its utility in various aspects of theoretical computer science, and their constructions. We will primarily be following the Vadhan’s manuscript titled “Pseudorandomness” [Vad12], with some recent developments.

Prerequisites

Although no prerequisites are formally required, it would be very helpful for students to have taken a basic course on probability and computational complexity. This would help the students put the course in perspective.

Crediting / auditing the course

Students from TIFR would be enrolling for this course using the usual channels (STCS CRS). The course will also be available in a hybrid mode over Zoom.

If you are interested in the zoom link, please contact me about it

Problem sets

Problem Set 1: [PDF] (Uploaded on: 2023-08-29, Deadline: 2023-09-10)
Problem Set 2: [PDF] (Uploaded on: 2023-09-28, Deadline: 2023-10-15)
Problem Set 3: [PDF] (Uploaded on: 2023-12-02, Deadline: 2023-12-10)

Summary / plan of lectures

Lecture 1 (Tuesday, 2023-08-22): Introduction to the course, administrivia, general notion of pseudorandomness and primary aims
Lecture 2 (Thursday, 2023-08-24): Basic derandomisation techniques – enumeration, method of conditional expectation, limited independence
Lecture 3 (Tuesday, 2023-08-29): Construction of k-wise independent hash families, applications to samplers, samplers using pairwise independence, averaging samplers as graphs
Lecture 4 (Thursday, 2023-08-31): Vertex expansion, spectral expansion, connection between them, expander mixing lemma
Lecture 5 (Tuesday, 2023-09-05): Spectral expansion implies vertex expansion, linear algebra of random walks, proof of the expander mixing lemma
Lecture 6 (Thursday, 2023-09-07): Analysing mixing time of random walks, understanding graphs with no spectral gap, a randomised logspace algorithm for undirected s-t connectivity
Lecture 7 (Tuesday, 2023-09-12): Matrix decomposition of expanders into “complete graph” + “error”, hitting property of random walks on expanders, efficient error reduction in randomised algorithms
Lecture 8 (Thursday, 2023-09-14): Examples of expander graphs, building expanders via graph operations, the zig-zag product

(No lecture on 2023-09-19 (Ganesh Chaturti))

Lecture 9 (Thursday, 2023-09-21): Analysis of the zig-zag product, construction of strongly-explicit expander families
Lecture 10 (Tuesday, 2023-09-26): Low space algorithms, revisiting undirected s-t connectivity, Reingold’s log-space algorithm for undirected s-t connectivity
Lecture 11 (Thursday, 2023-09-28): Definition of graph Laplacians and sparsifiers, Spielman-Srivastava’s construction of spectral sparsifiers
Lecture 12 (Tuesday, 2023-10-03): Introduction to codes and list-decoding, achievable bounds for random codes, Johnson radius
Lecture 13 (Thursday, 2023-10-05): Hadamard, Reed-Solomon and Reed-Muller codes, Sudan’s algorithm for list-decoding Reed-Solomon codes
Lecture 14 (Tuesday, 2023-10-10): Revisiting Sudan’s algorithm for efficiently list-decoding RS codes, list recovery, modifications to polynomial codes to achieve list-decodability up to capacity
Lecture 15 (Thursday, 2023-10-12): Derivatives and multiplicities, distance of multiplicity codes, the Guruswami-Wang algorithm for list-decoding multiplicity codes
Lecture 16 (Tuesday, 2023-10-17): List size bounds for multiplicity codes, Kalev-TaShma’s construction of unbalanced lossless vertex expanders from multiplicity codes
Lecture 17 (Tuesday, 2023-10-31): Computational indistinguishability, definition of PRGs, existence, introduction to small-biased spaces
Lecture 18 (Thursday, 2023-11-09): Revisiting small-bias spaces with basic Fourier Analysis, Vazirani XOR Lemma, almost k-wise independence and k-universal set constructions
Lecture 19 (Tuesday, 2023-11-14): Next-bit-unpredictability, using hard functions for PRGs, combinatorial designs, towards the Nisan-Wigderson theorem
Lecture 20 (Thursday, 2023-11-16): Proof of the Nisan-Wigderson theorem, towards PRGs from worst-case hardness (Impagliazzo-Wigderson theorem), local decodability
Lecture 21 (Tuesday, 2023-11-21): Local decoding of Reed-Muller codes, code concatenation, worst-case hardness to some average case hardness
Lecture 22 (Tuesday, 2023-11-28): (tentative) Local list-decoding, local list-decoding of Reed-Muller codes, completing the Sudan-Trevisan-Vadhan’s proof of the Impagliazzo-Wigderson theorem
Lecture 23 (Thursday, 2023-11-30): (tentative) List-decoding Hadamard codes (Goldreich-Levin theorem), and applications.

References

[Vad12] : “Pseudorandomness” by Salil Vadhan.
[Vad16] : Salil Vadhan’s course title “Pseudorandomness” at Harvard University.
[Tre05] : Luca Trevisan’s course titled “Pseudorandomness and Combinatorial Constructions” at UC Berkeley.
[Spi15] : Daniel Spielman’s course titled “Spectral Graph Theory” at Yale University.
[Woo18] : Mary Wootters’ course titled “Algebraic Error Correcting Codes” at Stanford University