Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Talks in 2002

January 08, Robert Simons: A very simple algorithm for estimating the number of k-colourings of a low-degree graph (Mark Jerrum, Random Struct. Algorithms 7, No.2, 157-165 (1995)) [details]
January 10, Michael Balmer: Stable Husbands [details]
January 15, Florian Schneider: Storing a Sparse Table with O(1) Worst Case Access Time (M.L.Fredman, J. Komlós and E. Szemerédi, J. ACM 31(3), 1984) [details]
January 17, Heiko Vogler (Technische Universität Dresden): Tree Transducer with cost functions [details]
January 22, Gábor Tardos: Distinct sums and distinct distances [details]
January 24, Gyula Károlyi: Balanced 2-Colorings of Paths in Trees [details]
January 29, Stefan Hilzinger: Resource augmentation for online bounded space bin packing (János Csirik and Gerhard J. Wöginger, ICALP 2000) [details]
January 31, Miloš Stojaković: Limit Shape of Optimal Convex Lattice Polygons in the Sense of Different Metrics [details]

February 07, Jaroslav Nesetril (Charles University, Prague): Ordering of Flows and Tensions [details]
Friday, February 08, Susanne Albers (Freiburg University): Caching in Large Networks [details]
Monday, February 11, Bernhard von Stengel (Department of Mathematics, London School of Economics and Political Science): Coordination in Game Trees [details]
February 14, Ingo Schurr: Finding the Sink Takes Some Time [details]
February 28, Joachim Giesen: Spectral Voronoi Clustering Works for Smooth Curve Reconstruction (Diploma Thesis of Papik Meli) [details]

March 12, Michael Hoffmann: Alternating paths among disjoint line segments [details]
March 14, Alexander Below: Prescribing Shapes of Faces of Polytopes [details]
March 26, Micha Sharir (Tel Aviv University): Incidences between Points and Circles in Higher Dimensions and Their Applications [details]
Wednesday, March 27, Marc van Kreveld (Utrecht University): Sweeping nicely through polyhedra and polygons [details]
March 28, Micha Sharir (Tel Aviv University): What Vladlen and I were working on in Zurich last year [details]

April 02, Csaba Dávid Tóth: From Distinct Distances to Isosceles Triangles [details]
April 04, Joachim Giesen: Flow Diagrams - A Data Structure for Geometric Modeling - Part I [details]
Friday, April 05, Alexander Below: Prescribing Shapes of Faces of Polytopes - The Saga Continues [details]
April 09, Joachim Giesen: Flow Diagrams - A Data Structure for Geometric Modeling - Part II [details]
April 11, Matthias John: Flow Diagrams - A Data Structure for Geometric Modeling - Part III [details]
April 16, Matthias John: Flow Diagrams - A Data Structure for Geometric Modeling - Part IV [details]
April 18, Udo Adamy: Call Control in Chains (joint work with Christoph Ambühl, R. Sai Anand, and Thomas Erlebach) [details]
Friday, April 19, Christoph Ambühl: Call Control in Rings (joint work with Udo Adamy, R. Sai Anand, and Thomas Erlebach) [details]
April 25, Bettina Speckmann: Allocating Vertex pi-guards in Simple Polygons via Pseudo-Triangulations. [details]
Friday, April 26, Falk Tschirschnitz: Admissible grid orientations as example for extendable partial chirotopes. [details]

Friday, May 03, Günter Rote (Freie Universität Berlin): Locked linkages and rigidity of self-touching frameworks. [details]
May 07, Uli Wagner: The CLIQUE Problem in Intersection Graphs of Ellipses [details]
May 14, Alex Brodsky (University of British Columbia): On the Complexity of Buffer Allocation in Message Passing Systems (45 min) [details]
Wednesday, May 15, Josep Diaz (Universitat Politecnica de Catalunya): Bisection of Random Cubic graphs [details]
May 21, Tibor Szabó: Transversals with Bounded Components, I [details]
May 28, Michael Hoffmann: PushPush [details]
May 30, Tibor Szabó: Transversals with Bounded Components, II [details]

June 04, Yoshio Okamoto: Traveling salesman games with the Monge property [details]
June 06, Aaron Zollinger: Towards a Theory of Peer-to-peer Computability [details]
June 11, Uli Wagner: On Rectilinear Crossing Numbers of Complete Graphs [details]
June 18, Friedhelm Meyer auf der Heide (Universität Paderborn): The randomized z-buffer algorithm [details]
June 20, Emil Müller: RUSH HOUR is PSPACE-complete [details]
June 25, Res Völlmy: Point set surfaces [details]
June 27, Lisa von Boehmer: Squashed Cubes [details]

July 02, Christof Marti: Improved Sorting Networks [details]
July 04, Miloš Stojaković: On restricted min-wise independence of permutations [details]
Friday, July 05, Mordecai J. Golin (Hong Kong University of Science and Technology): The Probabilistic Complexity of the Voronoi Diagram of Points on a Polyhedron [details]
July 23, Komei Fukuda (McGill University): From the Zonotope Construction to the Minkowski Addition of Convex Polytopes [details]

September 03, Uli Wagner: On weak epsilon-nets for convex sets [details]
September 05, József Solymosi: On structures of point-line systems with many incidences [details]
September 12, Bettina Speckmann: Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons [details]
September 17, Pavel Valtr (Charles University, Prague): On the maximum number of unit distances among n points on a sphere. [details]
September 19, Pavel Valtr (Charles University, Prague): The maximum number of unit distances for planar point sets in convex position, and extremal questions for convex geometric graphs [details]

October 01, Dmitry Kozlov (KTH Stockholm/Universität Bern): The geometry of coin-weighing problems [details]
October 03, Péter Csorba: Notes on the Index of the Join of Topological Spaces [details]
October 15, Emo Welzl: Sorting in a mesh (or what Adi Shamir told me), I [details]
October 17, Emo Welzl: Sorting in a mesh (or what Adi Shamir told me), II [details]
October 22, Bettina Speckmann: Convexity minimizes pseudotriangulations [details]
October 24, Michael Farber (Tel Aviv University): Algebraic Topology and Robot Motion Planning [details]
October 29, Yoshio Okamoto: Matroid Representation of Clique Complexes [details]
October 31, Kaspar Fischer: MINIBALL and the distance to the convex hull [details]

November 05, Yoshio Okamoto: Submodular-type optimization on abstract convex geometries [details]
November 07, Uli Wagner: Convex Quadrilaterals and j-Edges, Part I [details]
November 12, Uli Wagner: Convex Quadrilaterals and j-Edges, Part II [details]
November 14, Martin Kutz (FU Berlin): News from Angel and Devil [details]
November 19, Falk Tschirschnitz: The Holt-Klee condition is insufficient for LP-cubes. (W. Morris), Part I [details]
November 21, Ferdinando Cicalese (University of Salerno): For Pinocchio La Vita NON e' Bella [details]
November 26, Falk Tschirschnitz: The Holt-Klee condition is insufficient for LP-cubes. (W. Morris), Part II [details]
November 28, Tibor Szabó: Turan's Theorem in sparse random graphs [details]

December 03, Ingo Schurr: Nearly no linear programs on cubes [details]
December 05, Fabio Roncoroni: Similarity Search in High Dimensions via Hashing [A.Gionis, P.Indyk, and R.Motwani] [details]
December 10, Fabian Chudak (IFOR): Approximation algorithms for facility location problems [details]
December 12, Péter Csorba: Chromatic Number and Simplicial Complexes [details]
December 17, Diana Senn: A Combinatorial Proof of Kneser's Conjecture [details]