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.


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.


Previous offerings of this course

Recorded lectures from previous offerings