The school consists of two main modules, each running for 2x45 minutes a day, for 5 days:

  • Sampling, Counting, Mixing and Balancing.
    Instructor: Eli Upfal, Brown University

    We will cover some recent developments in the applications of probabilistic techniques to the design and analysis of algorithms. In particular we will discuss methods for approximate counting of combinatorial structures using rapidly mixing Markov chains, and combinatorial balancing techniques based on the power of multiple choice paradigm.

    Reference: M.Mitzenmacher - E.Upfal, Probability and Computing. Cambridge U Press

  • Talagrand's Isoperimetric Inequality, Transportation Cost and Applications to the Analysis of Randomized Algorithms.
    Instructor: Devdatt Dubhashi, Chalmers University

    In the first part of this series of lectures, we will give a gentle introduction to Talagrand's inequality and illustrate it with applications, in particular, for the analysis of randomized algorithms, taking examples from recent literature. In the second part, we will discuss the transportation cost method to prove isoperimetric inequalties, including that of Talagrand discussed in the first part.

    Reference: D.Dubhashi - A.Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms.