Time: Tue-Thu 09:30-11:00
Location: Zoom and Live Youtube Streaming
Instructors: and
Homepage:
http://www.tifr.res.in/~prahladh/teaching/2021-22/pseudorandom
In view of the suspension of all in-class lectures due to the COVID-19 precautionary measure, all classess will be held in the distance model via Zoom.
The online lectures will be both transcribed and recorded. The online transcripts are available below as pdfs while the videos will be available on the STCS TIFR Youtube Channel.
| 24 Aug | 1. The Power of Randomness Administrivia; introduction; power of randomness (equality, Ramsey theory, primality, generating primes, undirected path, approximating MAXCUT) [ Notes (ph) ] |
| 26 Aug | 2. Polynomial Identity Testing Finite fields, polynomial identity testing, Schwartz-Zippel Lemma, perfect matching in bipartite graphs [ Notes (ph) ], Ref: Sudan's primer on Finite Fields. |
| 31 Aug | 3. Do we need randomness? Can we eliminate/reduce randomness? Enumeration; Method of Conditional Expectations; Limited Independence (pairwise independence) [ Notes (ph) ] |
| 02 Sep | 4. Primer on Probabilistic Classes Pairwise independent family of hash functions; Randomized Complexity Classes; Error Reduction; Basic probability inequalities. [ Notes (ph) ], Ref: [Vad (Sec 2.2)] |
| 07 Sep | 5. Epsilon-biased distributions Error Reduction (Chernoff vs Chebyshev), Samplers (independent, pair-wise independent), epsilon-biased distribution, AGHP construction [ Notes (ph) ], Ref: [Vad (Sec 3.5.4), AGHP] |
| 09 Sep | 6. Expander Graphs I: Introduction Promise problem, complete problem for prBPP, samplers, introduction to expansion, vertex expansion [ Notes (ph) ], Ref: [Vad (Sec 2.3.2, 3.5.4, 4.1)] |
| 14 Sep | 7. Expander Graphs II: Random graphs and KPS generator Vertex expansion, random graphs are expanders, explicit vs super-explicit constructions, Karp-Pippenger-Sipser generator [ Notes (ph) ], Ref: [Vad (Sec 4.1, 4.3 (Intro))] |
| 16 Sep | 8. Expander Graphs III: Spectral Expansion Random-walk matrix, spectral expansion, expander mixing lemma, spectral expansion implies vertex expansion [ Notes (ph) ], Ref: [Vad (Sec 4.1), HS (Lecture 20-23), BL] |
| 21 Sep | 9. Expander Graphs IV: Random Walks spectral vs vertex expansion, Ramanujan graphs, random walk on graphs and expanders [ Notes (ph) ], Ref: [Vad (Sec 4.1.2, 2.4), HS (Lecture 20-23)] |
| 23 Sep | 10. Expander Graphs V: Hitting Set Lemma Hitting set lemma and Chernoff bound for random walk on expanders, explicit algebraic constructions of expanders [ Notes (ph) ], Ref: [Vad (Sec 4.2, 4.3 (till end of 4.3.1)), HS (Lecture 20-23)] |
| 28 Sep | 11. Expander Graphs VI: Zig-Zag Expanders Explicit constructions of expander graphs; Graph operations: squaring, tensoring, zig-zag prodcut; zig-zag expander construction [ Notes (rp) ], Ref: [Vad (Sec 4.3)] [IPython notebook] |
| 30 Sep | 12. Expander Graphs VII: Undirected Connectivity in logspace Review of zig-zag expander construction, Reingold's logspace algorithm for undirected connectivity [ Notes (rp) ], Ref: [Vad (Sec 4.3, 4.4)] |
| 05 Oct | 13. Expander Graphs VIII: Spectral sparsifiers Laplacian of a graph, Spielman-Srivastava spectral sparsfication [ Notes (rp) ], Ref: [SS, Sri] |
| 07 Oct | 14. Pseudorandom Generators I: Introduction Intro to PRGs, PRGs for derandomizing BPP?, next bit unpredicatability [ Notes (rp) ] |
| 18 Oct | 15. Pseudorandom Generators II: Nisan's PRG PRGs for small space, Nisan's PRG, PRGs for low communication via the INW generator. [ Notes (rp) ], Ref: [DH (Lec 4)] |
| 21 Oct | 16. Pseudorandom Generators III: BPL ⊆ L3/2 Deterministic simulation using Nisan's PRG: pseudorandom squaring; truncation and random perturbation, Saks-Zhou Theorem: BPL ⊆ L3/2. [ Notes (ph) ], Ref: [SZ, Sak] |
| 26 Oct | 17. Pseudorandom Generators IV: PRGs from average-case hardness Average-case hardness, combinatorial designs, Nisan-Wigderson theorem: PRGs from average-case hard functions. [ Notes (rp) ], Ref: [NW, Vad (Sec 7.4)] |
| 28 Oct | 18. Pseudorandom Generators V: PRGs from worst-case hardness An exposition of Impagliazzo-Wigderson PRGs: weakly hard functions, Yao's XOR Lemma, Goldreich-Levin theorem, locally decodable codes, worst-case to average-case hardness. [ Notes (rp) ], Ref: [IW, Vad (Sec 7.5)] |
| 02 Nov | 19. Extractors I: Introduction Weak random sources, closeness of distributions, deterministic extractors, towards seeded extractors [ Notes (rp) ], Ref: [Vad (Sec 6.1)] |
| 09 Nov | 20. Extractors II: Block sources and extractors for them Hash functions and expanders as extractors, block sources, zigzag-like extractors for block sources, roadmap towards extractors for general sources [ Notes (rp) ], Ref: [Vad (Sec 6.2, 6.3.1)] |
| 11 Nov | 21. Extractors III: Extractors for general sources Condensers, Residual Entropy Lemma, reducing general sources to block sources, the Guruswami-Umans-Vadhan extractor [ Notes (rp) ], Ref: [Vad (Sec 6.3)] |
| 16 Nov | 22. Extractors IV: Trevisan's extractor List-decoding viewpoint of pseudorandom objects, blackbox PRG constructions, Trevisan's extractor. [ Notes (rp) ], Ref: [Vad (Sec 5.3, 6.2.3, parts of 7.7.1 and 7.7.2)] |
| 18 Nov | 23. Extractors V: Two-source extractors (an exposition) Ramsey graphs, two source extractors, an exposition of ideas in explicit constructions [Notes (rp)], Ref: [Dor, Zuc, Li] |
| 23 Nov | 24. Finding APs inside dense subsets of integers Szemerédi regularity lemma, triangle removal lemma, Roth's theorem, towards sparse regularity theorems and the Green-Tao theorem [Notes (rp)], Ref: [CFZ] |
| 30 Nov | 25. Finding 3APs inside dense subsets of pseudorandom
sets of integers Roth's Theorem, Relative Roth's Theorem, Dense model theorem and counting lemma. [Notes (ph)], Ref: [CFZ] |
| 2 Dec | 26. Dense Model Theorem Dense model theorem: dense subsets of pseudorandom sets have a dense model [Notes (ph)], Ref: [CFZ, RTTV ] |
| 7 Dec | 27. High Dimensional Expanders - I Intro to high-dimensional expanders, random walks (up-down, down-up), link expanders, sampling spanning trees [Notes (ph)] |
| 9 Dec | 28. High Dimensional Expanders - II Sampling spanning trees of graphs, up-down and down-up walks, matroidal graphs [Notes (ph), Exposition of ALOV19 ], Ref: [ALOV] |
| [AGHP] | Noga Alon, Oded Goldreich, Johan Hastad and Rene Peralta, Simple Constructions of Almost k-wise Independent Random Variables. Random Struct. Alg., 3:289-304, 1992. [ .pdf | doi ] |
| [ALOV] | Nima Anari and Kuikui Liu and Shayan Oveis-Gharan and Cynthia Vinzant, Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proc. 51st ACM Symp. on Theory of Computing (STOC), pages 1–12. 2019 [ doi | arXiv ] |
| [BL] | Yonathan Bilu and Nati Linial, Lifts, Discrepancy and Nearly Optimal Spectral Gap. Combinatorica 26, 495-519, 2006. [ .pdf | doi ] |
| [CFZ] | David Conlon, Jacob Fox, Yufei Zhao The Green-Tao Theorem: An Exposition. EMS Surveys in Mathematical Sciences, 1 (2). pp. 249-282 [ .html | doi | Video by Yufei Zhao (hosted on YouTube) ] |
| [DH] | Cynthia Dwork and Prahladh Harsha CS369E: Expanders in Computer Science, 2005. A course offered at Stanford (Spring 2005). [ .html ] |
| [Dor] | Dean Doron. A Reduction from Efficient Non-Malleable Extractors to Low-Error Two-Source Extractors. Video lecture at the Simons Institute [ Video (hosted on YouTube)] |
| [HS] | Prahladh Harsha and Piyush Srivastava CSS.202.1 Toolkit for Theoretical Computer Science, 2021. A course offered at TIFR (Winter-Summer 2020-21). [ .html ] |
| [IW] | Russell Impagliazzo and Avi Wigderson P = BPP if E requires Exponential Circuits: Derandomizing the XOR Lemma. Proc. 29th Annual ACM Symposium on the Theory of Computing (STOC), 220-229, 1997. [ .pdf | doi ] |
| [LW] | Michael Luby, Avi Wigderson. Pairwise Independence and Derandomization.. Found. Trends Theor. Comput. Sci., 1(4):237-301, 2005. [ .pdf | doi ] |
| [Li] | Xin Li. New Independent Source Extractors with Exponential Improvement. Video lecture at the Institute of Advanced Study [ Video (hosted on YouTube)] |
| [NW] | Noam Nisan, Avi Wigderson. Hardness vs Randomness.. J. Comput. Syst. Sci., 49(2):149-167, 1994. [ .pdf | doi ] |
| [RTTV] | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan New Proofs of the Green–Tao–Ziegler Dense Model Theorem: An Exposition. 2008 [ arXiv ] |
| [Sak] | Michael E. Saks. Randomization and Derandomization in Space_Bounded Computation, Computational Complexity Conference: 128-149, 1996. [ doi ] |
| [Sri] | Nikhil Srivastava. Lectures Series on Graph Sparsfication.. Algorithmic Spectral Graph Theory Boot Camp, 26-27 Aug, 2014. [ Video I | Video II | Video III (hosted on YouTube) ] |
| [SS] | Daniel A. Spielman and Nikhil Srivastava. Graph Sparsification by Effective Resistances. SIAM J. Comput., 40(6), 1913–1926, 2011. [ arXiv | doi ] |
| [SZ] | Michael E. Saks, Shiyu Zhou. BPHSpace(S) ⊆ DSPACE(S3/2). J. Comput. Syst. Sci. 58(2): 376-403, 1999. [ .pdf | doi ] |
| [Vad] | Salil Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. [ .html | doi ] |
| [Zuc] | David Zuckerman. Explicit Two-Source Extractors and Resilient Functions - Chattopadhyay and Zuckerman. Video lecture at the Simons Institute [ Video (hosted on YouTube)] |
This page has been accessed at least
times since 19 August, 2021.
| Prahladh Harsha |