Pseudorandomness (2018-II)

(Mon 1130 — 1300) & (Wed 1400 — 1530) @ A 201

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.

Problem sets

  • Problem Set 1: [PDF] (Deadline: August 31st 2018)
  • Problem Set 2: [PDF] (Deadline: September 29th 2018)
  • Reed-Solomon decoding [html] (Deadline: Dec 1st 2018)
  • Problem Set 3: [PDF] (Deadline: November 24th 2018)

Source files: [ZIP]

Brief summary of lectures

Lecture 1 (Monday, 2018-08-13)
Introduction to the course, definition of objects, basic complexity classes, basic probability inequalities.
Lecture 2 (Friday, 2018-08-17)
Basic techniques: enumeration, method of conditional expectations, bounded independence
  • [Vad12]: Section 3.4, and parts of Section 3.5
Lecture 3 (Monday, 2018-08-20)
Sampling using pairwise independence, and randomness-efficient error reduction, introduction to random walks on graphs
  • [Vad12]: Section 3.5, Section 2.4
Lecture 4 (Monday, 2018-08-27)
Random walks via linear algebra, hitting time and spectral expansion, introduction to the Laplacian, U-st-conn is in RL
  • [Vad12]: Section 2.4, parts of Chapter 4
  • [Spi15]: Parts of Lecture 2 and 10
Lecture 5 (Wednesday, 2018-08-29)
Expanders, spectral expansion implies vertex and edge expansion, expander mixing lemma
Lecture 6 (Friday, 2018-08-31)
Cheeger inequalities, using expanders for sampling problems.
Lecture 7 (Wednesday, 2018-09-05)
Explicit constructions of constant degree expanders (squaring, tensoring and zig-zag products of graphs)
Lecture 8 (Monday, 2018-09-10)
Derandomized squaring, U-st-conn is in L
Lecture 9 (Wednesday 2018-09-12)
Spectral sparsifiers for general graphs.
Lecture 10 (Monday 2018-09-17)
Introduction to codes, list decoding, proof of existence, Johnson bound
Lecture 11 (Wednesday 2018-09-19)
Reed-Solomon codes - Berlekamp-Welsch’s unique decoder, and Sudan’s list decoder
Lecture 12 (Wednesday 2018-09-26)
(Lecturer: Prahladh Harsha)
Improved list-decoding of Reed-Solomon codes by Guruswami and Sudan
  • [Guruswami-Sudan]: “Improved decoding of Reed-Solomon and algebraic-geometric codes.” (FOCS 1998)
Lecture 13 (Monday 2018-10-01)
Limits of list decoding Reed-Solomon codes (BenSasson-Kopparty-Radhakrishnan), introduction to folded Reed-Solomon codes
  • [Vad12]: Sections 5.2.3 and 5.2.4
Lecture 14 (Wednesday 2018-10-03)
List decoding Folded Reed-Solomon codes
Lecture 15 (Monday 2018-10-08)
Graph theoretic view of samplers and list decodable codes, near-optimal unbalanced vertex expanders from codes
Lecture 16 (Wednesday 2018-10-10)
Introduction to extractors, weak sources, non-existence of deterministic extractors, existence of seeded extractors
Lecture 17 (Monday 2018-10-15)
Strong extractors, and connections to hash functions, expanders and samplers via list-size bounds
Lecture 18 (Thursday 2018-10-18)
(tentative) Block sources and extracting randomness from them, towards extractors for general sources
Lecture 19 (Monday 2018-10-22)
Explicit construction of extractors for general sources with O(log n)-seed length
Lecture 20 (Monday 2018-11-05)
Introduction pseudorandom generators. epsilon-biased spaces and applications to almost k-wise independence
  • [Vad12]: Initial parts of Chapter 7
Lecture 21 (Monday 2018-11-12)
Average case hardness of functions, hybrid argument, PRGs from average case hard functions via Nisan-Wigderson designs
Lecture 22 (Wednesday 2018-11-14)
Revisiting PRGs from average case hardness and using it for Trevisan’s extractor
Lecture 23 (Monday 2018-11-19)
Nisan’s PRG for RL
Lecture 24 (Wednesday 2018-11-21)
BPL is in SC, and hitting-set generator of Hoza-Zuckerman for RL
Lecture 25 (Monday 2018-11-26)
Finishing the Hoza-Zuckerman HSG, introducing the method of gradually increasing independence
Lecture 26 (Wednesday 2018-11-28)
Gradually increasing independence for balls and bins, and PRGs for combinatorial rectangles