Monday May 16th, 2005
 

09:00 - 09:10    Opening
Chair:                 Martin Dyer

9:10 -  9:40        Alan Frieze (CMU - Pittsburgh)
                            Average Case Performance of an Approximation Algorithm for the Facility Location Problem
9:40 - 10:10       Moses Charikar (Princeton University)
                            Aggregating Inconsistent Information: Ranking and Clustering
10:10 - 10:40     Uri Zwick (Tel Aviv University )
                           Approximate Distance Oracles and Spanners with sublinear surplus

Coffee break

Chair:                 Mark Jerrum

11:00 - 11:30    Thomas Hayes (Univ. California - Berkeley)
                          A general lower bound for mixing of single-site dynamics on graphs
11:30 - 12:00    Leslie Ann Goldberg (University of Warwick)
                           Sampling from Antiferromagnetic Potts Model on the Integer Lattice

12:15                  Lunch break

Chair:                 Marek Karpinski

15:00 - 15:30    Anupam Gupta (CMU - Pittsburgh)
                           Simple Sampling Solutions for Stochastic Optimization
15:30 - 16:00     R. Ravi (CMU - Pittsburgh)
                           LP Based Solutions for Stochastic Optimization

16:00 - 16:30    Coffee break

Chair:                 Alan Frieze

16:30 - 17:00    Michael Langberg (CalTech - Pasadena)
                          The Encoding Complexity of Network Coding
17:00 - 17:30    Markus Bläser (ETH Zürich)
                          Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems

18:00                  Dinner
 

Tuesday, May 17th, 2005
 

Chair:                 Johan Håstad

09:00 - 09:30    Mark Jerrum (University of Edinburgh)
                           The complexity of the ferromagnetic Ising model with local fields
09:30 - 10:00    Andrei Krokhin (University of Durham)
                           On the approximability of non-Boolean Max CSP
10:00 - 10:30    Magnus Bordewich (University of Leeds)
                           Independent Sets and Colorings in Hypergraphs

10:30 - 11:00    Coffee break

Chair:                 Moni Naor

11:00 - 11:30    Christian Borgs (Microsoft Research - Seattle)
                           Proof of the local REM conjecture for number partitioning
11:30 - 12:00    Mary Cryan (University of Edinburgh)
                           Sampling Integer Network Flows

12:15                  Lunch break

Chair:                 Michael Paterson

15:00 - 15:30    Gregory Sorkin (IBM TJ Watson Research Center)
                           Fast Algorithms for Max Cut, Max 2-SAT, etc.
15:30 - 16:00    Amin Coja-Oghlan (Humboldt-University Berlin)
                           A Spectral Heuristic for Bisecting Random Graphs

16:00 - 16:30    Coffee break

Chair:                 Uri Zwick

16:30 - 17:00    Berthold Vöcking (RWTH Aachen)
                           Approximation Techniques for Utilitarian Mechanism Design
17:00 - 17:30    Stefanie Gerke (ETH Zürich)
                          Algorithmic Aspects of the Regularity Lemma

18:00                  Dinner
 

Wednesday May 18th, 2005
 

Chair:                 Moses Charikar

09:00 - 09:30    Marek Karpinski (University of Bonn)
                           Approximating Metric Bisection and Related Partitioning Problems
09:30 - 10:00    Kamal Jain (Microsoft Research - Seattle)
                           Building Scalable and Robust Peer-to-Peer Overlay Networks for Broadcasting using Network Coding
10:00 - 10:30    Tim Roughgarden (Stanford University)
                           Computing Correlated Equilibria in Multi-Player Games

10:30 - 11:00    Coffee break

Chair:                 Berthold Vöcking

11:30 - 12:00    Russell Martin (University of Warwick)
                            Distributed Selfish Load Balancing
11:30 - 12:00    Nicolas Schabanel (École Normale Supérieure - Lyon)
                           Asynchronous randomized automata

12:15                  Lunch break

13:30 - 17:30     Excursion

18:00                  Dinner

20:00                  Evening Session

Chair:                  R. Ravi
 

Thursday May 19th, 2005
 

Chair:                 Christian Borgs

09:00 - 09:30    Johan Håstad (KTH Stockholm)
                           Every 2-CSP allows nontrivial Approximation                         
09:30 - 10:00    Moni Naor (Weizmann Institute - Rehovot)
                           Succinct Constructions of k-Wise (Almost) Independent Permutations                         
10:00 - 10:30    Miklos Santha (Université Paris Sud)
                           Query Complexity of Local Search                         

10:30 - 11:00    Coffee break

Chair:                 Klaus Jansen

11:00 - 11:30    Jennifer Chayes (Microsoft Research - Seattle)
                           The Spread of Viruses on Scale-Free Graphs
11:30 - 12:00    Andrej Lingas (Lund University)
                           Approximating Maximum Clique Minor and some Subgraph Homomorphism Problems

12:15                  Lunch break

16:00                  Coffee

18:00                  Dinner
 

Friday May 20th, 2005
 

Chair:                Jennifer Chayes

09:00 - 09:30    Klaus Jansen (University of Kiel)
                           Approximation algorithms for scheduling malleable tasks with precedence constraints
09:00 - 10:00    Olga Gerber (University of Kiel)
                           On Packing Squares with Resource Augmentation: Maximizing the Profit                         
10:00 - 10:30    Martin Dyer (University of Leeds)
                           Sampling Regular Graphs and a Peer-to-Peer Network

10:30 - 11:00    Coffee break

Chair:                 Leslie Ann Goldberg

11:00 - 11:30    David B. Wilson (Microsoft Research - Seattle)
                           Balanced Boolean functions that can be evaluated so that every bit is unlikely to be read
11:30 - 12:00    Artur Czumaj (NJIT - Newark)
                           MST in Metric Spaces

END OF WORKSHOP

12:15                  Lunch