Synopsis:
Decision Problems
* Space-bounded interactive protocols
* Reachability and threshold problems for Markov chains
* Connections with number theory
Stochastic Processes
* Markov-chain Monte Carlo techniques, Coupling
* Martingales, Optional Stopping Theorem, Azuma’s inequality and
applications, Lyapunov functions
* Equivalence of Markov chains, Markov decision processes
* Distance between Markov chains
* Analysis of infinite-state Markov chains
Data Structures and Algorithms
* Luby’s algorithm
* Count-min filters
* Random rounding, packet routing
Learning Theory
* Rademacher complexity, VC dimension
* Johnson-Lindenstraus Lemma