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

The schedule:
Monday: 9:30 – 11:30 am and 1:30 – 3:30 pm
Tuesday: 9 – 11:30 am, 1:30-3:30 pm and 4-6 pm.
Wednesday: 9-11:30 am and 1:30-3:30 pm.
Thursday: 9 am – 12:30 pm
Friday: 9 am – 12:30 pm and afternoon exam: 2 pm – 4 pm

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