Pseudorandomness (2018II)
(Mon 1130 — 1300) & (Wed 1400 — 1530) @ A 201
(.ical)
This course will deal with various kinds of explicit objects that are “randomlooking”, 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)
 ReedSolomon decoding [html] (Deadline: Dec 1st 2018)
 Problem Set 3: [PDF] (Deadline: November 24th 2018)
Source files: [ZIP]
Brief summary of lectures
 Lecture 1 (Monday, 20180813)
 Introduction to the course, definition of objects, basic complexity classes, basic probability inequalities.

 [Vad12]: Chapter 1, Section 2.2
 Lecture 2 (Friday, 20180817)
 Basic techniques: enumeration, method of conditional expectations, bounded independence

 [Vad12]: Section 3.4, and parts of Section 3.5
 Lecture 3 (Monday, 20180820)
 Sampling using pairwise independence, and randomnessefficient error reduction, introduction to random walks on graphs

 [Vad12]: Section 3.5, Section 2.4
 Lecture 4 (Monday, 20180827)
 Random walks via linear algebra, hitting time and spectral expansion, introduction to the Laplacian, Ustconn is in RL

 [Vad12]: Section 2.4, parts of Chapter 4

 [Spi15]: Parts of Lecture 2 and 10
 Lecture 5 (Wednesday, 20180829)
 Expanders, spectral expansion implies vertex and edge expansion, expander mixing lemma

 [Vad12]: Section 4.1
 Lecture 6 (Friday, 20180831)
 Cheeger inequalities, using expanders for sampling problems.

 [Vad12]: Section 4.2 and 4.3
 Lecture 7 (Wednesday, 20180905)
 Explicit constructions of constant degree expanders (squaring, tensoring and zigzag products of graphs)

 [Vad12]: Section 4.3
 Lecture 8 (Monday, 20180910)
 Derandomized squaring, Ustconn is in L

 [Vad12]: Section 4.4

 [RozenmannVadhan]: “Derandomized Squaring of Graphs”, RANDOM 2005
 Lecture 9 (Wednesday 20180912)
 Spectral sparsifiers for general graphs.

 [SpielmanSrivastava]  “Graph Sparsification by Effective Resistances”, SICOMP

 “Graph Sparsification I: Sparsification via Effective Resistances” (Video) by Nikhil Srivastava at Simon’s Institute
 Lecture 10 (Monday 20180917)
 Introduction to codes, list decoding, proof of existence, Johnson bound

 [Vad12]: Section 5.1
 Lecture 11 (Wednesday 20180919)
 ReedSolomon codes  BerlekampWelsch’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 20180926)
 (Lecturer: Prahladh Harsha)
 Improved listdecoding of ReedSolomon codes by Guruswami and Sudan

 [GuruswamiSudan]: “Improved decoding of ReedSolomon and algebraicgeometric codes.” (FOCS 1998)

 Chapter 13 of Essential Coding Theory by Guruswami, Sudan and Rudra
 Lecture 13 (Monday 20181001)
 Limits of list decoding ReedSolomon codes (BenSassonKoppartyRadhakrishnan), introduction to folded ReedSolomon codes

 [BenSassonKoppartyRadhakrishnan]: “Subspace polynomials and List Decoding of ReedSolomon Codes”, FOCS 2006

 [Woo18]: Lecture 14

 [Vad12]: Sections 5.2.3 and 5.2.4
 Lecture 14 (Wednesday 20181003)
 List decoding Folded ReedSolomon codes

 Chapter 14 of Essential Coding Theory by Guruswami, Sudan and Rudra

 [Woo18]: Lecture 14
 Lecture 15 (Monday 20181008)
 Graph theoretic view of samplers and list decodable codes, nearoptimal unbalanced vertex expanders from codes

 [Vad12]: Section 5.3, 5.4

 [GuruswamiUmansVadhan]: “Unbalanced expanders and randomness extractors from ParvareshVardy codes”
 Lecture 16 (Wednesday 20181010)
 Introduction to extractors, weak sources, nonexistence of deterministic extractors, existence of seeded extractors

 [Vad12]: Section 6.1
 Lecture 17 (Monday 20181015)
 Strong extractors, and connections to hash functions, expanders and samplers via listsize bounds

 [Vad12]: Section 6.2
 Lecture 18 (Thursday 20181018)
 (tentative) Block sources and extracting randomness from them, towards extractors for general sources

 [Vad12]: Section 6.3
 Lecture 19 (Monday 20181022)
 Explicit construction of extractors for general sources with O(log n)seed length

 [Vad12]: Section 6.3
 Lecture 20 (Monday 20181105)
 Introduction pseudorandom generators. epsilonbiased spaces and applications to almost kwise independence

 [Vad12]: Initial parts of Chapter 7

 Lecture 7 of Swastik Kopparty’s course Topics in Complexity Theory and Pseudorandomness.
 Lecture 21 (Monday 20181112)
 Average case hardness of functions, hybrid argument, PRGs from average case hard functions via NisanWigderson designs

 [Vad12]: Section 7.3 and 7.4
 Lecture 22 (Wednesday 20181114)
 Revisiting PRGs from average case hardness and using it for Trevisan’s extractor

 [Vad12]: Section 7.7
 Lecture 23 (Monday 20181119)
 Nisan’s PRG for RL

 Lecture 9,10 from Amnon TaShma’s course SpaceBounded Computation
 Lecture 24 (Wednesday 20181121)
 BPL is in SC, and hittingset generator of HozaZuckerman for RL

 Parts of lectures 9,10 and 11 from Amnon TaShma’s course SpaceBounded Computation
 Lecture 25 (Monday 20181126)
 Finishing the HozaZuckerman HSG, introducing the method of gradually increasing independence

 Lecture 11 from Amnon TaShma’s course SpaceBounded Computation

 Tutorial (video) by Parikshit Gopalan at WACT 2016
 Lecture 26 (Wednesday 20181128)
 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