Pseudorandomness (2025-II)
(Tuesdays and Thursdays 0930 — 1100) @ A 238
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.
Problem sets
Summary / plan of lectures
- Lecture 1 (Tuesday, 2025-08-26)
- Introduction to the course, administrivia, general notion of pseudorandomness and primary aims, method of conditional expectation applied to derandomise 2-approximation of MaxCut
- Lecture 2 (Thursday, 2025-08-28)
- k-wise independent hash families, construction of k-wise independent hash families and application to derandomising 2-approximation of MaxCut and 7/8-approximation of Max3SAT.
- Lecture 3 (Thursday, 2025-09-04)
- Samplers, and using pairwise independence to construct samplers
- Lecture 4 (Tuesday, 2025-09-09)
- Introduction to graph expanders, definition of vertex expanders and proof of existence of vertex expanders, definition of spectral expanders
- Lecture 5 (Thursday, 2025-09-11)
- Spectral theorem, connecting spectral expanders with eigenvalues, linear algebra of random walks matrices, expander mixing lemma
- Lecture 6 (Tuesday, 2025-09-16)
- Relating graph mixing times with spectral gap, undirected s-t connectivity in randomised logspace, expanders = complete graph + noise
- Lecture 7 (Thursday, 2025-09-18)
- Proof of the hitting property of expanders and Expander Chernoff bound
- Lecture 8 (Tuesday, 2025-09-23)
- Construction of explicit expanders (I): some examples of expanders, and graph operations such as powering and tensoring, definition of the zig-zag product
- Lecture 10 (Thursday, 2025-09-25)
- Construction of explicit expanders (II): Analysing the zig-zag product of graphs and using graph operations to build strongly explicit expander graph families
- Lecture 11 (Tuesday, 2025-10-07)
- Reingold’s low-space algorithm for undirected connectivity
- Lecture 12 (Thursday, 2025-10-09)
- Graph sparsification (Spielman-Srivastava)
- Lecture 13, 14 (Tuesday, 2025-10-14 (double-class))
- Introduction to coding theory and list-decoding, Singleton bounds and generalised Singleton bounds, Johnson radius, Reed-Solomon codes, Sudan’s algorithm for list-decoding Reed-Solomon codes up to Johnson radius
- Lecture 15 (Thursday, 2025-10-23)
- Folded-Reed-Solomon codes and the Guruswami-Wang algorithm for list-decoding FRS codes
- Lecture 16 (Tuesday, 2025-11-04)
- Recap of the Guruswami-Wang list-decoding algorithm, list size bounds for Folded-Reed-Solomon codes: pruning algorithm of Kopparty-Saraf-RonZewi-Wootters and Tamo’s bound
- Lecture 17 (Thursday, 2025-11-06)
- Ashvinkumar-Habib-Srivastava’s algorithm for list-decoding FRS codes in time poly(n, 1/eps) (also yielding a list size of 1/eps^2), Chen-Zhang’s list-size bound of O(1/eps)
- Lecture 18 (Tuesday, 2025-11-11)
- Code concatenation, decoding concatenated codes, expander-based codes by ABNNR (distance amplifications) and AEL (local-to-global codes), recent results on AEL codes achieving list-decoding capacity (and in near-linear time!)
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
Previous offerings of this course
Recorded lectures from previous offerings