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)
- (tentative) Graph sparsification
- Lecture 13 (Tuesday, 2025-10-14)
- (tentative) TBA
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