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

Talks in 2005

January

January 11, Christopher Portmann: Maximum satisfiability: How good is tabu search in the worst-case? [details]
January 13, Mathias Schacht (HU Berlin): Discrepancy and Eigenvalues of Cayley Graphs [details]
January 18, Dejan Dukaric: The Pancake Problem [details]
January 20, Raphael Meyer: Cooperative Facility Location Games [details]
Friday, January 21, Erik D. Demaine (MIT): Origami, Polyhedra, and Linkages: Folding with Algorithms [details]
Monday, January 24, Nir Halman (Technion, Haifa): On the Power of Discrete Helly Theorems and Lexicographic Helly Theorems [details]
January 25, Raphael Boog: An Approximation Scheme for Makespan Scheduling with Capacity Constraints [details]
January 27, Andreas Streich: A new short proof of Kneser's conjecture [details]

February

February 01, Eva Schuberth: What colors have to do with geometry: the gamut mapping project [details]
February 03, Penny Haxell (Univ. of Waterloo): Ramsey numbers for hypergraph cycles [details]
Monday, February 07, Jochen Abhau (Univ. Bonn): The Homology of Moduli Spaces of Riemann Surfaces - Calculations for Genus g [details]
February 08, Johann A. Makowsky (Technion, Haifa): What did Tarski mean with "elementary Geometry is decidable"? [details]
February 10, Christoph Ambühl (Istituto Dalle Molle di Studi sull' Intelligenza Artificiale, Lugano): Minimum spanning trees in the unit disk [details]
February 15, Bartosz Przydatek: Solving Medium-Density Subset Sum Problems in Expected Polynomial Time [details]
February 17, Reto Spöhel: Online graph avoidance games in random graph [details]
February 22, Abraham Flaxman (Carnegie Mellon Univ.): Two stage stochastic programming on average: Minimum Spanning Trees [details]

March

March 01, Johann A. Makowsky (Technion, Haifa): Iteration Graphs and their Polynomials [details]
March 08, Lars Engebretsen (KTH Stockholm): Some of Håstad's optimal inapproximability results [details]
March 10, Jan Remy: Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems [details]
March 17, Nikolay Dichev (TU München): Nonadaptive Search With a Lie [details]
March 22, Shankar Ram Lakshminarayanan: Metric Traveling Salesman Games [details]
March 24, Elias Vicari: Off-Diagonal Ramsey Numbers [details]
March 29, Tibor Szabó: The Discrepancy Game [details]
March 31, Michael Hoffmann: Degree Bounds for Constrained Pseudo-Triangulations [details]

April

April 05, Piotr Krysta (Univ. Dortmund): Approximate Utilitarian Mechanism Design via Primal-Dual Method [details]
April 07, Kevin Buchin (FU Berlin): Incremental Construction along Space-Filling Curves [details]
April 12, Maike Buchin (FU Berlin): Semi-Computability of the Fréchet Distance between Surfaces [details]
April 14, Justus Schwartz: Fast Algorithms for Weighted Bipartite Matching [details]
April 19, Dan Hefetz (Tel Aviv Univ.): Avoider-Enforcer games [details]
Wednesday, April 20, Nick Wormald (Univ. of Waterloo): Birth control for giants [details]
April 21, Uwe Schöning (Univ. Ulm): Quest for the fastest SAT algorithm [details]
Friday, April 22, Uli Wagner (Einstein Inst. of Mathematics, The Hebrew Univ. of Jerusalem): k-Sets and Topological Invariants of Plane Curves [details]
April 28, Emo Welzl: On the Number of Crossing-Free Geometric Graphs (Triangulations) [details]

May

May 03, Jozef Skokan (Univ. of Illinois at Urbana-Champaign and Univ. de São Paulo): On a theorem of Luczak [details]
Friday, May 06, Shakhar Smorodinsky (Courant Inst., New York Univ.): On the Chromatic Number of Some Geometric Hypergraphs [details]
May 10, János Barát (TU Lyngby): The slope parameter of graphs [details]
Wednesday, May 11, Leonhard Vogt: A Tabu Search Algorithm for the Single Vehicle Routing Allocation Problem [details]
May 12, Martin Aigner (FU Berlin): Pancake Problems [details]
May 17, Malwina Luczak (London School of Economics and Political Science): On the maximum queue length and asymptotic distributions in the supermarket model [details]
May 19, Leo Rüst: Simple Stochastic Games via P-matrix Linear Complementarity Problems [details]
Monday, May 23, Marc Noy (Univ. Politècnica de Catalunya): The number of planar graphs and properties of random planar graphs [details]
May 24, András Recski (Budapest Univ. of Technology and Economics): Some applications of combinatorial optimization in statics [details]
May 26, Gyula Károlyi (Eötvös Lorand University): Set addition in noncommutative groups [details]
May 31, Stefan Birrer: Tutte's Spring Theorem [details]

June

June 02, Emo Welzl: On the Number of Crossing-Free Geometric Graphs [details]
June 07, Andreas Meyer: Geometric Complexity Theory: The Bilinear Case [details]
June 09, Christian Borgs (Microsoft Research & Univ. of Washington): Proof of the local REM conjecture for number partitioning [details]
June 14, Ron Aharoni (Technion, Haifa): The Erdős-Menger Conjecture [details]
Wednesday, June 15, Edgar Ramos (Univ. of Illinois at Urbana-Champaign): Manifold Reconstruction from Point Samples [details]
Wednesday, June 15, Pankaj Agarwal (Duke University): Optimal Coresets for Approximating the Extent of Shallow Levels [details]
June 16, Vijay Victor D'Silva: The Topological Structure of Asynchronous Computability [details]
June 21, Csaba Dávid Tóth (MIT): A vertex-face assignment for plane graphs [details]
Wednesday, June 22, Patrick Müller: General lexicographic shellability [details]
June 23, Jiří Matoušek (Charles Univ.): New badly embeddable spaces (presenting work of Subhash Khot and Assaf Naor) [details]
June 28, Manuel Huber: Algorithmic Aspects of Szemerédi's Regularity Lemma [details]
Wednesday, June 29, Vera Vértesi: Identities in Algebras [details]
June 30, Florin Oswald: Popular Matchings [details]

July

Wednesday, July 06, Bettina Speckmann (TU Eindhoven): On Rectangular Cartograms [details]
July 07, Maike Buchin (FU Berlin): Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard [details]
July 07, Kevin Buchin (FU Berlin): The Flow Complex: General Structure and Algorithm [details]
July 07, Yoshio Okamoto (Toyohashi University of Technology): All-pairs shortest paths with real weights in O(n³ /log n) time [details]
July 12, Florian Block: Tropical Convexity via Cellular Rsolutions [details]
July 14, Shankar Ram Lakshminarayanan: Approximation algorithm for Maximum 3-Cycle cover problem [details]
July 19, Hans-Martin Will: Challenges and Opportunities in the Post-Genome Era - An Introduction to Functional Genomics and Proteomics [details]
July 21, Masashi Kiyomi (National Institute of Informatics (NII): Efficient Algorithms for the Electric Power Transaction Problem [details]
July 26, Takeaki Uno (National Institute of Informatics (NII): Tree Enumeration Algorithms [details]

August

August 04, L. Shankar Ram: The Traveling Salesman Problem with Distances One and Two [details]
August 11, Martin Marciniszyn: A Probabilistic Counting Lemma for Complete Graphs [details]
August 18, Mutsunori Yagiura (Kyoto University): Exact Algorithms for Two-Dimensional Strip Packing Problems [details]
Monday, August 22, Naveen Garg (IIT New Delhi): A faster algorithm for computing the Held-Karp bound [details]
August 23, Karl Lieberherr (Northeastern Univ., Boston): Algorithmic Problems Related to the Tyranny of the Dominant Decomposition [details]

September

September 01, Dominik Scheder (Univ. of Colorado at Boulder): Finding highly connected subgraphs of low weight [details]
September 15, Elias Vicari: Communication Complexity in the Algebraic Model [details]
September 20, Volker Roth: Feature Selection in Unsupervised Clustering: Applications in Computer Vision and Bioinformatics [details]
Wednesday, September 21, Michael Krivelevich (Tel Aviv Univ.): Property testing in graphs of general density [details]
September 22, József Beck (Rutgers Univ.): Every finite point set in the plane is a Weak Winner! [details]
September 27, Florian Jug: Computer aided information processing in the Structuralism [details]

October

October 04, Joshua Cooper (Courant Institute, NYU and ETH Zürich): What keeps me up at night [details]
October 06, Joachim Giesen: Critical Point Theory of the Distance to a Point Sample and Applications in Geometric Modeling [details]
Friday, October 07, Mitsuo Motoki (Japan Advanced Institute for Science and Technology): Test Instance Generation for MAX 2SAT [details]
October 11, Ken Satoh (National Institute of Informatics, Japan): Enumerating Minimally Revised Specifications using Dualization [details]
Wednesday, October 12, Micha Sharir (Tel Aviv Univ.): On the ICP algorithm [details]
October 13, Bodo Manthey (Univ. Lübeck): Restricted cycle covers [details]
October 18, Berit Johannes: Earliest Start Time Scheduling in AND/OR-graphs - An Introduction [details]
October 20, Joshua Cooper (Courant Inst., NYU and ETH Zürich): Missing induced subgraphs [details]
October 25, Ryuhei Uehara (Japan Advanced Institute of Science and Technology): Efficient Algorithms for the Longest Path Problem [details]
October 27, Jozef Skokan (Univ. of Illinois at Urbana-Champaign and Univ. de São Paulo): Generalized Turán Theorem [details]

November

November 01, Alexander Engström: Playing with independent sets [details]
November 03, Ulrike von Luxburg (Fraunhofer IPSI, Darmstadt): Convergence of random graph Laplacians [details]
November 08, Konstantinos Panagiotou: Performance Measures for Paging [details]
November 10, Alex Souza-Oftermatt: A New Lower Bound for Paging [details]
November 15, Andreas Razen: Counting satisfying 2SAT Assignments [details]
November 17, Dirk Schlatter (HU Berlin): The random planar graph process [details]
November 17, Leonidas Guibas (Stanford Univ.): Structure from Proximity in Point Data [details]
November 22, Graham Brightwell (London School of Economics): Non-transitive sets of dice [details]
November 24, Emo Welzl: Random Triangulations of Point Sets [details]
November 29, Rüdiger Schultz (Univ. Duisburg): Risk Aversion in Stochastic Integer Programming: Models and Algorithms [details]

December

December 01, Takeaki Uno (National Institute of Informatics (NII): Enumerating Dense Subgraphs [details]
December 06, Andreas S. Schulz (MIT and ETH Zürich): How many diamonds can be packed in a Chinese checkerboard? [details]
December 08, Patrick Müller: Map coloring and the vector cross product [details]
December 13, Rahul Savani (London School of Economics): Hard-to-Solve Bimatrix Games [details]
December 15, Bernhard von Stengel (London School of Economics): Strategic characterization of the index of an equilibrium [details]
December 20, Robert Berke: Testing Relaxed Two-Colorability [details]
December 22, Florian Walpen: Boosted Sampling: Approximation Algorithms for Stochastic Optimization [details]