Analysis of Combinatorial Algorithms and Concentration of Measure
- Dagstuhl Workshop: Analysis of Combinatorial Algorithms and Concentration of Measure
- August 29 -- September 3, 2004
- Organizers: Devdatt Dubhashi (Goeteborg), Anand Srivastav (Kiel)
Abstract
Concentration of Measure has witnessed some of the most important
recent advances in modern probability theory. These developments
include Talagrand's isoperimetric inequalities, Log-Sobolev
inequalities and Transportation cost inequalities, in addition to
renewed interest and development of martingale methods. Some of
these techniques have had a profound impact on the analysis of
randomized algorithms and some others have great potential to do so.
This seminar aims at gathering together yound researchers and some
leading
experts in the area, from Probability Theory, Combinatorics
and Computer Science
to achieve an integrated view of the
state-of-the-art of the theme, and to provide a ,,guided tour'' for
non-experts in computer science and algorithmic discrete mathematics who
are
applying probabilistic methods to the analysis of
randomized and approximation algorithms.
Participants
- Andreas Baltz (Kiel)
- Stephane Boucheron (Paris)
- Benjamin Doerr (Kiel)
- Devdatt Dubhashi (Goeteborg)
- Helena Fohlin (Goeteborg/Kiel)
- Michael Gnewuch (Kiel)
- Rene Hakenjos (Kiel)
- Nils Hebbinghaus (Kiel)
- Peter Hegarty (Goeteborg)
- Cecilia Holmgren (Goeteborg)
- Lasse Kliemann (Kiel)
- Urban Larsson (Goeteborg)
- Oskar Sandberg (Goeteborg)
- Anand Srivastav (Kiel)
- Soeren Werth (Kiel)
Program
Monday, 30.8.2004 (Chernoff-Hoeffding Bounds)
| 9.15 -- 10.30 | S. Boucheron | From exponential Inequalities to Concentration of Measure |
| 11.00 -- 11.45 | D. Dubhashi | Chernoff-Hoeffding Bounds in Dependent Settings |
| 16.15 -- 17.00 | O. Sandberg/C. Holmgren | Chernoff Bounds for Reversible Markov Chains |
| 17.10 -- 17.55 | B. Doerr | Dependent Randomized Rounding |
Tuesday, 31.8.2004 (Martingales)
| 9.15-- 10.30 | A. Srivastav | Introduction to Martingale Inequalities |
| 11.00 -- 11.45 | R. Hakenjos | Concentration of Polynomials and its Applications |
| 14.45 -- 15.45 | A. Baltz/ H. Fohlin | Divide and Conquer Martingales and the Number of Triangles in a Random Graph |
| 16.15 -- 17.00 | N. Hebbinghaus | Two Quick Number Theoretical Applications for the Probabilistic Method |
| 17.10 -- 17.55 | P. Hegarty/U. Larsson | Thin Bases |
Wednesday, 1.9.2004 (Talagrand-Inequality)
| 9.15 -- 10.00 | D. Dubhashi | Isoperimetric Inequalities and Concentration |
| 10.30 -- 11.15 | A. Srivastav | Two Talagrand Bounds |
| 11.30 -- 12.15 | S. Werth | Probability Theory of Euclidean Optimization Problems |
Thursday, 2.9.2004 (Information-Theoretic Bounds)
| 9.15 -- 10.00 | M. Gnewuch | Probabilistic Methods in Discrepancy Theory |
| 10.05 -- 10.45 | D. Dubhashi | Tranportation Cost Inequalities and Concentration |
| 11.15 -- 12.15 | D. Dubhashi | Transportation Cost Inequalities, cont'd |
| 16.15 -- 17.00 | L. Kliemann | Mixed Strategies in a Non-Cooperative Routing Game |
| 17.10 -- 17.55 | D. Dubhashi | Transportation Cost Inequalities and Talagrand's Inequality |
Friday, 3.9.2004 (Log-Sobolev Inequalities)
| 9.15 -- 10.30 | S. Boucheron | Concentration Inequalities from the Entropy Method |
| 11.00 -- 12.00 | S. Boucheron | Some Applications of the Entropy Method |
Technicalities
Arrival is planned on Sunday, August 29 and departure on
Friday, September 3, after Lunch. Schloss Dagstuhl provides
full-board accommodation for the participants.
The webpage of Schloss Dagstuhl is http://www.dagstuhl.de and contains all relevant information, especially travel information (http://www.dagstuhl.de/TravelInfo/WorkshopGuest/index.en.html).
