School on Randomized Algorithms

Partially supported by BiCi

4 February 2008 - 8 February 2008

Aims

This school is partially supported by BiCi.

Probabilistic algorithms and methods have become a cornerstone of the Theory of Algorithms. This school will present important and exciting recent developments in an organized and gentle manner.

A limited number of fellowships is available. Please refer to "Registration"

Sampling, Counting, Mixing and Balancing 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 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. Manuscript: www.dsi.uniroma1.it/~ale/papers.html