[CvGmt News] School on Randomized Algorithms at the CRM in Pisa

[Luigi Ambrosio]

To whom may be interested,

I am sending the announcement of a school on Randomized Algorithms that 
will take place at the Centro De Giorgi from
February 3 to February 8 of 2008, organized by Alessandro Panconesi (La 
Sapienza University) and me.

Below is a short description of this activity, see also 
http://www.dsi.uniroma1.it/~ale/BiCi/Sns08/ 
Registration can be made at:

_http://www.crm.sns.it/cgi-bin/pagina.pl?Id=101&Tipo=evento&TipoEvento=schools&Sezione=Registration&Periodo=future_

Luigi Ambrosio

*****

BiCi - SNS School on Randomized Algorithms

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.

1. 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

2. 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