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

  • Problem set 1: [PDF] (Due date: 2025-09-28)
  • Problem set 2: [PDF] (Due date: 2025-10-19)

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

Previous offerings of this course

Recorded lectures from previous offerings