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

Talks in 2008

January 08, Tobias Christ: A Lower Bound Example for the Wireless Localization Problem [details]
January 15, Fedor Fomin (Univ. of Bergen, Norway): Parameterized Algorithms for Directed Maximum Leaf Problems [details]
January 24, Philipp Zumstein: Polychromatic Colorings of Plane Graphs [details]
January 29, Dominik Scheder: Hardness, Pseudo-Randomness and Derandomization (Part I) [details]
January 31, Dominik Scheder: Hardness, Pseudo-Randomness and Derandomization (Part II) [details]

February 05, Miloš Stojaković (Univ. u Novom Sadu): Slow losing again [details]
February 07, Viola Mészáros (Univ. of Szeged, Charles Univ. Prague): Alternating Paths in Bicolored Point Sets [details]
February 12, Joachim Giesen (Max-Planck-Institut für Informatik, Saarbrücken): The solution path of the slab SVM [details]
February 19, Bernd Gärtner: Can you get drunk on unique sink orientations? [details]
February 21, Uli Wagner: Van Kampen's Obstruction and Embeddability of Skeleta of Spheres [details]
February 26, Michael Hoffmann: An improved upper bound for wireless localization [details]
February 28, Martin Jaggi: Geometry of Support Vector Machines [details]

March 04, Marek Sulovský: Circle containment problem and centerpoints [details]
March 06, Matthew Cook (Institute of Neuroinformatics): The Correspondence between Closed Sets of Functions and Closed Sets of Relations (Part I) [details]
March 11, Imre Bárány (Alfréd Rényi Mathematical Institute, Hungarian Academy of Sciences): Paths with no small angle [details]
March 13, Dominik Scheder: How many conflicts does it need to be unsatisfiable? [details]
March 18, Robert Berke: Matching Transversals in Multipartite Graphs [details]
March 20, Matthew Cook (Institute of Neuroinformatics): The Correspondence between Closed Sets of Functions and Closed Sets of Relations (Part II) [details]

April 01, Yves Brise: Lipschitzian Optimization, DIRECT Algorithm, and Applications [details]
April 03, Nicla Bernasconi: Quadratic exact-size and linear approximate-size random generation of planar graphs [details]
April 08, Joel Spencer (Courant Institute, New York Univ.): Neuron Firing [details]
April 10, Lutz Warnke: Asymptotic Packing via A Branching Process [details]
April 15, Robert Almgren (Courant Institute, New York Univ.): Portfolios from sorts [details]
April 17, Jesús Jerónimo Castro (Univ. Autónoma de Guerrero, Acapulco, México): Shaken Rogers's Theorem [details]
April 22, Fabian Kuhn: Tight Bounds for Distributed Selection [details]
April 24, Torsten Mütze: Antimagic Labellings of Graphs [details]
April 29, Henning Thomas: Balanced Online Ramsey Games in Random Graphs [details]

May 06, Martin Tancer (Charles Univ., Prague): On the complexity of recognition of d-collapsible complexes [details]
May 08, Jiří Matoušek (Charles Univ., Prague): On the difficulty of removing degeneracy in LP-type problems: The way of topology [details]
May 13, Alexandru Tomescu (Univ. of Bukarest): Minimal Graphs with respect to the Degree Distance [details]
Wednesday, May 14, Sándor Kovács (University of Washington): Algebra=Geometry [details]
May 20, Anastasios Sidiropoulos (MIT): Circular Partitions with Applications to Visualization and Embeddings [details]
May 22, Eran Nevo (Cornell Univ., Ithaca): A characterization of simplicial polytopes with g₂=1 [details]
May 27, Jiří Matoušek (Charles Univ., Prague): Low-distortion embeddings in R^d [details]
May 29, Gábor Fejes Tóth (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary): Shortest path among circles [details]

June 05, Piotr Sankowski (ETH Zurich): Stochastic Analyses for Combinatorial Optimization Problems [details]
June 12, Dirk Nowotka (Univ. Stuttgart): When the Maximum Intersection Problem Is Easy: On the Use of Threshold Phenomena in Randomized Graph Models [details]

July 08, Karl Lieberherr (Northeastern University, Boston, USA): Using Artificial Markets to Teach Computer Science Through Trading Robots [details]
Monday, July 14, Jiří Matoušek (Charles Univ., Prague): Blocking visibility for points in general position [details]
July 17, Jeong Han Kim (Yonsei Univ., South Korea): Random Graphs, Random Regular Graphs and Couplings [details]
July 22, Jeong Han Kim (Yonsei Univ., South Korea): Optimal Query Complexity Bounds for Finding Graphs [details]

August 21, Philipp Zumstein: Analytic Methods in Extremal Graph Theory [details]

September 04, Bernd Gärtner: Nests, Whirls, and Twists [details]
September 11, Thomas Rast: On the Degree Sequence of 3-connected Planar Maps [details]
September 16, Stefanie Gerke (Royal Holloway, Univ. of London): Uniform Random Intersection Graph [details]
September 18, Robin Moser: Derandomizing the Lovász Local Lemma more Effectively [details]
September 23, Luca Gugelmann: Balanced Online Vertex-Coloring Games in Random Graphs [details]
September 25, Dominik Scheder: Almost Disjoint Formulas and Almost Tight Bounds [details]
September 30, Emo Welzl: Triangulations of Convex Polygons - A Historical Note [details]

October 02, Tobias Christ: NP-Hardness of the Wireless Localization Problem [details]
October 07, Raimund Seidel (Univ. des Saarlandes): Making the Inverse Ackermann Function Appear Natural(ly) [details]
October 09, Martin Jaggi: Core-sets for polytope distance [details]
October 14, Gabriel Katz: Tropical Centerpoints and Tverberg Points [details]
October 16, Michael Krivelevich (Tel Aviv Univ.): Perfectly balanced partitions of smoothed graphs [details]
October 21, Uli Wagner: Hardness of Embedding Simplicial Complexes in R^d (Part I) [details]
October 23, Uli Wagner: Hardness of Embedding Simplicial Complexes in R^d (Part II) [details]
October 28, Peter Sanders (Univ. Karlsruhe): Improving Kruskal's Algorithm [details]
October 30, Heidi Gebauer: Unsatisfiable CNF-Formulas with Small Neighborhoods [details]

November 04, Andreas Razen: Counting Crossing-Free Geometric Graphs with Exponential Speed-Up (Part I) [details]
November 06, Andreas Razen: Counting Crossing-Free Geometric Graphs with Exponential Speed-Up (Part II) [details]
November 11, Tom Rackham (Mathematical Institute, Oxford Univ.): Methods of distance-constraint precolouring [details]
November 13, Dominik Scheder: Bollobás' and Riordan's Proof of the Harris-Kesten Theorem [details]
November 18, Robin Künzler: The Power of Interactive Proofs, IP = PSPACE [details]
November 20, Marek Sulovský: Circle containment problem [details]
November 25, Torsten Mütze: Small subgraphs in random graphs and the power of multiple choices: The online case [details]
November 27, Reto Spöhel: Small subgraphs in random graphs and the power of multiple choices: The offline case [details]

December 02, Christian Lorenz Müller (Mosaic Group, ETH Zürich): Stochastic search and randomized algorithms for energy landscapes (Part I) [details]
December 04, Yves Brise: Covering Spheres with Spheres [details]
December 09, Dan Hefetz: Weighted colorings and Alon-Tarsi choosability (Part I) [details]
December 11, Dan Hefetz: Weighted colorings and Alon-Tarsi choosability (Part II) [details]
December 16, Rom Pinchasi (Technion, Israel): Some new results related to the 'halving lines problem' [details]
December 18, Zhen Hao (Univ. Heidelberg, Research Group Combinatorial Optimization): Construction of a PTAS for the Steiner tree problem with neighborhoods in the plane [details]