Talks in 2005

January

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

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

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

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

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

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

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

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

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

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

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

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