Erdös Magic
for Algorithms and Games

24-29 April 2005
University of Bologna Residential Center
Bertinoro (Forlì), Italy

[ What the Meeting is About
| Seminar Schedule
| Important Dates
| Location
| How to Reach Bertinoro
| List of Participants
| Abstracts
| Organization and Sponsorship
| Local Weather Forecast
| Conference Photos ]

What the Meeting is About

The topics are probabilistic methods in a broad sense and efficiency of randomization.

The goal of the workshop is to bring together researchers from various areas related to the application of the probabilistic method. This includes such topics as such as probabilistic combinatorics, (probabilistic) games, discrepancy and randomized algorithms. We plan to have ample time for discussions and joint work.

Seminar Schedule

Monday, 25th
7:00 - 9:00 Breakfast
9:40 - 10:30 Tic-Tac-Toe like games
Jozsef Beck
10:30 Coffee
11:00 - 11:30 Liar games over an arbitrary channel
Ioana Dumitriu
11:35 - 12:05 Positional Games on random graphs
Milos Stojakovic
12:30 Lunch
15:30 Afternoon Coffee
16:15 - 16:55 Selfish Multicast Routing
Lasse Kliemann
17:00 - 17:30 Selfish Routing with Incomplete Information
Martin Gairing
17:35 - 18:05 The Fully Mixed Nash Equilibrium Conjecture
(and Supermarket Queing)

Andreas Baltz
19:30 Dinner

Tuesday, 26th
7:00 - 9:00 Breakfast
9:40 - 10:30 Large girth regular graphs versus random regular graphs
Nick Wormald
10:30 Coffee
11:00 - 11:30 Random constraint satisfaction problems
Michael Molloy
11:35 - 12:05 Planar subgraphs in dense graphs, sparse random graphs
and random graph processes

Anusch Taraz
12:30 Lunch
15:30 Afternoon Coffee
16:15 - 16:45 How many queries does it take to decide if there's
a percolating cluster?

David Bruce Wilson
16:55 - 17:25 Optimal Group Testing Algorithms with Interval Queries
and Their Application to Slice Site Detection

Ferdinando Cicalese
17:30 - 18:00 A Separation Theorem in Property Testing
Asaf Shapira
19:30 Dinner

Wednesday, 27th
7:00 - 9:00 Breakfast
9:40 - 10:30 Lifts of Graphs
Nati Linial
10:30 Coffee
11:00 - 11:30 A Sophisticated Solution to an Elementary Problem
Devdatt Dubhashi
11:35 - 12:05 Balls-in-Bins with feedback and Brownian motion
Roberto Oliveira
12:30 Lunch
15:30 Afternoon Coffee
19:30 Dinner

Thursday, 28th
7:00 - 9:00 Breakfast
9:40 - 10:30 The game of JumbleG
Michael Krivelevich
10:30 Coffee
11:00 - 11:30 On Avoider-Enforcer Games
Dan Hefetz
11:35 - 12:05 Random walk on oriented hypercubes
Tibor Szabo
12:30 Lunch
15:30 Afternoon Coffee
16:15 - 16:45 Discrepancy of Arithmetic Structures
Nils Hebbinghaus
16:55 - 17:25 Discretisation of Discrepancy and Applications
Michael Gnewuch
17:30 - 18:00 Randomized Rounding: Binary Reductions Make Life Easy
Benjamin Doerr
19:30 Dinner

Friday, 29th
7:00 - 9:00 Breakfast
9:40 - 10:30 Exact values of infinitely many game numbers
Jozsef Beck
10:30 Coffee
11:00 - 11:30 Planar Multi-Depot TSP for Random Points
Anand Srivastav
11:35 - 12:05 Generalized Turan Theorem
Jozef Skokan
12:30 Lunch and End of the Workshop

Important Dates

Arrival: Sunday 24 April, 2005
Departure: Friday 29 April, 2005


The location of the workshop is a veritable XIII-th century fortress in Bertinoro -- a small, peaceful medieval hilltop town -- now turned into a nice conference center with all of the modern conveniences. Here is a map putting it in context. It is easily reached by train and taxi from Bologna and is close to many splendid Italian locations such as Ravenna, a treasure trove of byzantine art and history, and the Republic of San Marino (all within 35km) as well as some less well-known locations like the thermal springs of Fratta Terme and the castle and monastic gardens of Monte Maggio.  Bertinoro can also be a base for visiting some of the better-known Italian locations such as Padua, Ferrara, Vicenza, Venice, Florence and Siena.

Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak.  From the fortress you can enjoy a beautiful the vista that stretches from the Tuscan Apennines to the Adriatic coast.

How to Reach Bertinoro

List of participants

The following colleagues have agreed to participate in the workshop (status April 2005).
  1. Vera Asodi, Tel Aviv University, Israel
  2. Andreas Baltz, Universität Kiel, Germany
  3. Jozsef Beck, Rutgers University, USA
  4. Malgorzata Bednarska, Uniwersytet Adama Mickiewicza Poznan, Poland
  5. Ferdinando Cicalese, Universität Bielefeld, Germany
  6. Emilio De Santis, Università degli Studi di Roma La Sapienza, Italy
  7. Benjamin Doerr, Universität Kiel, Germany
  8. Devdatt Dubhashi, Chalmers University of Technology, Gothenburg, Sweden
  9. Ioana Dumitriu, U.C. Berkeley, USA
  10. Robert Ellis, Texas A&M University, USA
  11. Martin Gairing, Universität Paderborn, Germany
  12. Michael Gnewuch, Universität Kiel, Germany
  13. Nils Hebbinghaus, Universität Kiel, Germany
  14. Dan Hefetz, Tel Aviv University, Israel
  15. Lasse Kliemann, Universität Kiel, Germany
  16. Michael Krivelevich, Tel Aviv University, Israel
  17. Nathan Linial, Hebrew University of Jerusalem, Israel
  18. Tomasz Luczak, Uniwersytet Adama Mickiewicza Poznan, Poland
  19. Michael Molloy, University of Toroto, Canada
  20. Roberto Oliveira, New York University, USA
  21. Alessandro Panconesi, Università degli Studi di Roma La Sapienza, Italy
  22. Asaf Shapira, Tel Aviv University, Israel
  23. Jozef Skokan, University of Illinois at Urbana-Champaign, USA
  24. Joel Spencer, New York University, USA
  25. Anand Srivastav, Universität Kiel, Germany
  26. Milos Stojakovic, ETH Zürich, Switzerland
  27. Tibor Szabo, ETH Zürich, Switzerland
  28. Anusch Taraz, Technische Universität München, Germany
  29. Emo Welzl, ETH Zürich, Switzerland
  30. David Bruce Wilson, Microsoft Research and University of Washington, USA
  31. Nick Wormald, University of Waterloo, Canada

Organization and Sponsorship

Scientific Organizing Committee Tomasz Luczak, Uniwersytet im. Adama Mickiewicza, Poznañ
Joel Spencer, New York University
Anand Srivastav, Christian-Albrechts-Universität zu Kiel
Local Organization
Elena Della Godenza, Centro Congressi di Bertinoro
Sponsored by BICI   Bertinoro International Center for Informatics
CAU   Christian-Albrechts-Universität zu Kiel
DFG   Deutsche Forschungsgemeinschaft,   Schwerpunkt 1126 Algorithmik großer und komplexer Netzwerke


Conference Photos

GroupPhoto1.jpg RemainingPeople.jpg