Dates : 7-11 December
Teachers: Joel Ouaknine, Ben Worrell et Stefan Kiefel (Oxford).
Local contact: Pascal Koiran
Title: Probabilistic Techniques and Models in Computer Science
Synopsis (more information here):
— 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