[ University of Bonn | Department of Computer Science | Chair V ]
Monday, June 4th |
|
| 7:30 - 8:45 | Breakfast |
| 9:00 - 9:10 | Opening |
| Chair: | Marek Karpinski |
| 9:10 - 9:55 | Sanjeev Khanna (Penn Univ.) |
| Algorithms for Minimizing Weighted Flow Time | |
| 9:55 - 10:25 | Alan Frieze (CMU) |
| Edge Disjoint Paths in Expander Diagraphs | |
| 10:25 -11:00 | Coffee break |
| Chair: | Martin Dyer |
| 11:00 - 11:30 | Gregory Sorkin (IBM) |
| Optimal Myopic algorithms for Random 3SAT | |
| 11:30 - 12:00 | Graham Brightwell (London) |
| Connectivity among H-colorings | |
| 12:15 | Lunch break |
| Chair: | Mark Jerrum |
| 15:00 - 15:30 | Claire Kenyon (Paris-Sud) |
| Coalescing Particles on a Tree | |
| 15:30 - 16:00 | Michael Langberg (Weizmann Institute) |
| The RPR2 Rounding Technique for Semidefinite Programs | |
| 16:00 - 16:30 | Coffee break |
| Chair: | Alan Frieze |
| 16:30 - 17:00 | Malwina Luczak (Oxford) |
| Routing Random Calls on Graphs | |
| 17:00 - 17:30 | Gregory Sorkin (IBM) |
| Optimal myopic algorithms for random 3SAT | |
| 17:00 - 17:30 | Dana Randall (Georgia Tech) |
| Decomposition Swapping + Mean Field Models | |
| 18:00 | Dinner |
Tuesday, June 5th |
7:30 - 8:45 | Breakfast |
| Chair: | Ravi Kannan |
| 9:00 - 9:30 | Marek Karpinski (Bonn) |
| Approximability of Dense Nearest Codeword Problem | |
| 9:30 - 10:00 | Mark Jerrum (Edinburgh) |
| A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Non-Negative Entries, Part I | |
| 10:00 - 10:30 | Eric Vigoda (Edinburgh) |
| A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Non-Negative Entries, Part II | |
| 10:30 -11:00 | Coffee break |
| Chair: | Sanjeev Khanna |
| 11:00 - 11:30 | Piotr Berman (Bonn) |
| Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION | |
| 11:30 - 12:00 | Alex D. Scott (London) |
| Judicious Partitions of Graphs and Hypergraphs | |
| 12:15 | Lunch break |
| Chair: | Sanjeev Arora |
| 15:00 - 15:30 | W. Fernandez de la Vega (Paris-Sud) |
| Sampling k-Uniform Hypergraphs and Design of PTASs for Dense Instances of Min-CSP | |
| 15:30 - 16:00 | Jennifer Chayes (Microsoft) |
| The Phase Transition in the Random Partition Problem | |
| 16:00 - 16:30 | Coffee break |
| Chair: | Alexander Barvinok |
| 16:30 - 17:00 | Angelika Steger (München) |
| A New Performance Measure for Stochastic Scheduling | |
| 17:00 - 17:30 | Christian Borgs (Microsoft) |
| Slow Mixing for H-Colorings of the Hypercubic Lattice | |
| 18:00 | Dinner |
Wednesday, June 6th |
7:30 - 8:45 | Breakfast |
| Chair: | Jennifer Chayes |
| 9:00 - 9:30 | Eli Upfal (Brown) |
| Can Entropy Predict On-Line Performance? | |
| 9:30 - 10:00 | M. Karonski (Poznan) |
| Distributed Graph Coloring Algorithms | |
| 10:00 - 10:30 | Miklos Santha (Paris-Sud) |
| Quantum Algorithms for Some Instances of the Hidden Subgroup Problem | |
| 10:30 -11:00 | Coffee break |
| Chair: | W. Fernandez de la Vega |
| 11:00 - 11:30 | Klaus Jansen (Kiel) |
| Polynomial-time Approximation Schemes for Preemptive Resource Constrained Scheduling and Fractional Graph Coloring | |
| 11:30 - 12:00 | Catherine Greenhill (Melbourne) |
| Connectedness of Bounded Degree Star Processes | |
| 12:15 | Lunch break |
| 13:30 - 17:30 | Excursion |
| 18:00 | Dinner |
| 20:30 - | Evening Session |
| (Chair: A. Barvinok) | |
Thursday, June 7th |
7:30 - 8:45 | Breakfast |
| Chair: | Claire Kenyon |
| 9:00 - 9:30 | Sanjeev Arora (Princeton) |
| On On-Line Algorithms for Bandwidth Utilization | |
| 9:30 - 10:00 | Alexander Barvinok (Michigan) |
| Metric Geometry of Counting | |
| 10:00 -11:00 | Coffee break |
| Chair: | Michael Paterson |
| 11:00 - 11:45 | Ravi Kannan (Yale) |
| What Can You Do in One or Two Passes | |
| 11:45 - 12:15 | Colin Cooper (London) |
| Random Graphs Which Model the Internet | |
| 12:15 | Lunch break |
| Chair: | Eli Upfal |
| 15:00 - 15:30 | David B. Wilson (Microsoft) |
| Perfect Simulation for Quenchal Disordered Systems | |
| 15:30 - 16:00 | Petra Berenbrink (Warwick) |
| The Natural Work Stealing Algorithm is Stable | |
| 16:00 - 16:30 | Coffee break |
| Chair: | Gerhard Woeginger |
| 16:30 - 17:00 | Artur Czumaj (NJIT) |
| On Certain Property Testing Algorithms | |
| 17:00 - 17:30 | Thomas Jansen (Dortmund) |
| On the Analysis of Evolutionary Algorithms | |
| 18:00 | Dinner |
Friday, June 8th |
7:30 - 8:45 | Breakfast |
| Chair: | Graham R.Brightwell |
| 9:00 - 9:30 | Jung-Bae Son (Edinburgh) |
| Average Conductance and Log-Sobolev Constant of Balanced Matroids | |
| 9:30 - 10:00 | Piotr Krysta (MPI Saarbrücken) |
| Approximating Minimum Size 2-Connectivity Problems Using Local Search | |
| 10:00 - 10:30 | Lars Engebretsen (MIT) |
| Approximation Hardness of Traveling Salesman Problem with Bounded Metric | |
| 10:30 -11:00 | Coffee break |
| 12:15 | Lunch |