[CvGmt News] School on Randomized Algorithms at the CRM in Pisa
Luigi Ambrosio
l.ambrosio at sns.it
Mon Dec 17 17:09:27 CET 2007
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
More information about the News
mailing list