**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