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) ] |
2 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)] |
7 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] |
9 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: Introduction Intro to PRGs, PRGs for derandomizing BPP?, next bit unpredicatability [ Notes (rp) ] |
[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 ] |
[BL] | Yonathan Bilu and Nati Linial, Lifts, Discrepancy and Nearly Optimal Spectral Gap. Combinatorica 26, 495-519, 2006. [ .pdf | doi ] |
[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 ] |
[LW] | Michael Luby, Avi Wigderson. Pairwise Independence and Derandomization.. Found. Trends Theor. Comput. Sci., 1(4):237-301, 2005. [ .pdf | 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 ] |
[Vad] | Salil Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. [ .html | doi ] |
This page has been accessed at least times since 19 August, 2021.
Prahladh Harsha |