Organisatoren:

Dr. Stefanie Gerke ETH Zürich Institute of Theoretical Computer Science CAB H 36.2 Universitätsstr. 6 8092 Zürich, Switzerland

Prof. Dr. Anusch Taraz Technische Universität München Angewandte Geometrie und Diskrete Mathematik Boltzmannstr. 3 85747 Garching bei München, Germany

The area of random discrete structures has grown out of the so-called probabilistic method, originally a tool for proving the existance of combinatorial objects, into an independent field of research. One of its central themes is to determine typical properties of an object that is chosen at random from a certain class of discrete structures, and it is then particularly fascinating to watch how these properties can appear or disappear suddenly with only minor changes to the probability distribution on the class.

Knowledge of such typical properties, together with their evolution and their respective phase transitions, often form the basis for the design and the average-case analysis of algorithms. In general, although its roots were mostly in pure mathematics, the study of random discrete structures has by now found its applications both in related disciplines such as computer science or statistical physics as well as in practical problems.

During this minisymposium, we will bring together a variety of different topics and techniques. There will be lectures on structural topics such as graph colourings, expansion, and limit theorems, as well as talks focussing on algorithmic issues like probabilistic analysis, randomized rounding, and adversarial mixing.

Auszug zu diesem Minisymposium aus dem Programmheft (Stand: 15. Juli 2006). Weitere nützliche Informationen rund um die Tagung können der verkürzten Ausgabe des Programmheftes entnommen werden.

Programm (Stand: 07.09.2006):

Donnerstag	Übungsraum 2, Geographisches Institut, Meckenheimer Allee 166
15:00-15:25	Ralph Neininger (Frankfurt) Probabilistic analysis of game tree evaluation
15:30-15:55	Christian Scheideler (TU München) Adversarial mixing in virtual space
16:00-16:25	Benjamin Doerr (MPI Saarbrücken) Dependant Randomized Rounding
16:30-16:55	Bernd Gärtner (ETH Zürich) Clarkson's randomized linear programming algorithms revisited
17:00-17:25	Anand Srivastav (Kiel) Euclidean Nearest Neighbor Problems for Random Points
17:30-17:55	Berthold Vöcking (Aachen) Probabilistic Analysis of Local Search Algorithms for TSP
Freitag	Übungsraum 2, Geographisches Institut, Meckenheimer Allee 166
15:00-15:25	Volker Kaibel (TU Berlin, ZIB) 0/1-Polytopes With Exponentially Small Vertex-Expansion
15:30-15:55	Mihyun Kang (HU Berlin) Zufällige planare Strukturen
16:00-16:25	Amin Coja-Oghlan (HU Berlin) Central and local limit theorems for the giant component
16:30-16:55	Dieter Rautenbach (Bonn) Beyond Acyclic Colorings
17:00-17:25	Mathias Schacht (HU Berlin) On the bandwidth conjecture of Bollobás and Komlós