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