CSS.413.1: Pseudorandomness - Monsoon Semester (2021-22)


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


Dilbert Random
	Number Generator
Videos Problem Sets IPython Notebooks Lectures References

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.


Online Videos of Lectures


Problem Sets

  1. PS1 [ (out: 10 Sep, due: 23 Sep) ]
  2. PS2 [ (out: 2 Oct, due: 18 Oct) ]

Interactive python notebooks (hosted on Google Colab)


Lectures

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) ]

Tentative schedule (for future lectures)


References

[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 ]

Previous avatars of this course: 2018

This page has been accessed at least Counter times since 19 August, 2021.


Prahladh Harsha