ER01: Probabilistic Techniques and Models in Computer Science

      (7-11 December), Lyon


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