Pseudorandomness (2018-II)
(Mon 1130 — 1300) & (Wed 1400 — 1530) @ A 201
(.ical)
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.
Brief summary of lectures
- Lecture 1 (Monday, 2018-08-13)
- Introduction to the course, definition of objects, basic complexity classes, basic probability inequalities.
-
- [Vad12]: Chapter 1, Section 2.2
- 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
-
- [Vad12]: Section 4.1
- Lecture 6 (Friday, 2018-08-31)
- Cheeger inequalities, using expanders for sampling problems.
-
- [Vad12]: Section 4.2 and 4.3
- Lecture 7 (Wednesday, 2018-09-05)
- Explicit constructions of constant degree expanders (squaring, tensoring and zig-zag products of graphs)
-
- [Vad12]: Section 4.3
- Lecture 8 (Monday, 2018-09-10)
- Derandomized squaring, U-st-conn is in L
-
- [Vad12]: Section 4.4
-
- [Rozenmann-Vadhan]: “Derandomized Squaring of Graphs”, RANDOM 2005
- Lecture 9 (Wednesday 2018-09-12)
- Spectral sparsifiers for general graphs.
-
- [Spielman-Srivastava] - “Graph Sparsification by Effective Resistances”, SICOMP
-
- “Graph Sparsification I: Sparsification via Effective Resistances” (Video) by Nikhil Srivastava at Simon’s Institute
- Lecture 10 (Monday 2018-09-17)
- Introduction to codes, list decoding, proof of existence, Johnson bound
-
- [Vad12]: Section 5.1
- Lecture 11 (Wednesday 2018-09-19)
- Reed-Solomon codes - Berlekamp-Welsch’s unique decoder, and Sudan’s list decoder
-
- [Vad12]: Section 5.2.1, 5.2.2
-
- [Woo18]: Lecture 10 and Lecture 11
- 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)
-
- Chapter 13 of Essential Coding Theory by Guruswami, Sudan and Rudra
- Lecture 13 (Monday 2018-10-01)
- Limits of list decoding Reed-Solomon codes (BenSasson-Kopparty-Radhakrishnan), introduction to folded Reed-Solomon codes
-
- [BenSasson-Kopparty-Radhakrishnan]: “Subspace polynomials and List Decoding of Reed-Solomon Codes”, FOCS 2006
-
- [Woo18]: Lecture 14
-
- [Vad12]: Sections 5.2.3 and 5.2.4
- Lecture 14 (Wednesday 2018-10-03)
- List decoding Folded Reed-Solomon codes
-
- Chapter 14 of Essential Coding Theory by Guruswami, Sudan and Rudra
-
- [Woo18]: Lecture 14
- Lecture 15 (Monday 2018-10-08)
- Graph theoretic view of samplers and list decodable codes, near-optimal unbalanced vertex expanders from codes
-
- [Vad12]: Section 5.3, 5.4
-
- [Guruswami-Umans-Vadhan]: “Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes”
- Lecture 16 (Wednesday 2018-10-10)
- Introduction to extractors, weak sources, non-existence of deterministic extractors, existence of seeded extractors
-
- [Vad12]: Section 6.1
- Lecture 17 (Monday 2018-10-15)
- Strong extractors, and connections to hash functions, expanders and samplers via list-size bounds
-
- [Vad12]: Section 6.2
- Lecture 18 (Thursday 2018-10-18)
- (tentative) Block sources and extracting randomness from them, towards extractors for general sources
-
- [Vad12]: Section 6.3
- Lecture 19 (Monday 2018-10-22)
- Explicit construction of extractors for general sources with O(log n)-seed length
-
- [Vad12]: Section 6.3
- 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 7 of Swastik Kopparty’s course Topics in Complexity Theory and Pseudorandomness.
- Lecture 21 (Monday 2018-11-12)
- Average case hardness of functions, hybrid argument, PRGs from average case hard functions via Nisan-Wigderson designs
-
- [Vad12]: Section 7.3 and 7.4
- Lecture 22 (Wednesday 2018-11-14)
- Revisiting PRGs from average case hardness and using it for Trevisan’s extractor
-
- [Vad12]: Section 7.7
- Lecture 23 (Monday 2018-11-19)
- Nisan’s PRG for RL
-
- Lecture 9,10 from Amnon Ta-Shma’s course Space-Bounded Computation
- Lecture 24 (Wednesday 2018-11-21)
- BPL is in SC, and hitting-set generator of Hoza-Zuckerman for RL
-
- Parts of lectures 9,10 and 11 from Amnon Ta-Shma’s course Space-Bounded Computation
- Lecture 25 (Monday 2018-11-26)
- Finishing the Hoza-Zuckerman HSG, introducing the method of gradually increasing independence
-
- Lecture 11 from Amnon Ta-Shma’s course Space-Bounded Computation
-
- Tutorial (video) by Parikshit Gopalan at WACT 2016
- Lecture 26 (Wednesday 2018-11-28)
- Gradually increasing independence for balls and bins, and PRGs for combinatorial rectangles
-
- “Balls and bins: Smaller Hash Families and Faster Evaluation” by Celis, Reingold, Segev, Wieder (SIAM Journal Of Computing)
-
- Tutorial (video) by Parikshit Gopalan at WACT 2016
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