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

Talks in 2011

January 20, Reto Spöhel (MPI Saarbrücken): Creating small subgraphs in the Achlioptas process. [details]
January 25, Robin Künzler: The Equivalence of the Random Oracle Model and the Ideal Cipher Model. [details]

Friday, February 11, József Solymosi (Univ. of British Columbia): Incidences and singularities [details]
February 15, Miloš Stojaković (Univ. of Novi Sad): A threshold for the Maker-Breaker clique game [details]
February 22, Uli Wagner: An elementary construction of expanders [details]
February 24, Dominik Scheder: Mahaney's Theorem: A Complexity Theory Classic [details]

March 01, Jan Foniok: On Ramsey classes of structures [details]
March 03, Martin Jaggi: Convex Optimization with a Parameter, and Regularization Paths for Matrix Factorizations [details]
March 08, Michael Farber (Univ. of Durham): Random Complexes [details]
March 10, Yury Person (FU Berlin): (Hyper-)graph quasi-randomness [details]
March 15, Tobias Christ: How to describe an orthogonal polyhedron by cones. [details]
March 17, Aris Anagnostopoulos (Univ. of Rome): Algorithms on Dynamic Data [details]
March 22, Kenneth Clarkson (IBM Research Almaden): Sublinear Optimization for Machine Learning [details]
Wednesday, March 23, Ramamohan Paturi (UC San Diego): Sparsification lemma [details]
March 24, Ramamohan Paturi (UC San Diego): Complexity of Evaluating Quantified k-CNFs [details]
March 29, Yves Brise: Hypergraph Matching by Linear and Semidefinite Programming [details]
March 31, Frank Staals (TU Eindhoven): Geographic Grid Embeddings [details]

April 05, Henning Thomas: Explosive Percolation: Defused and Reignited [details]
April 07, Gabriel Nivasch: Lower bounds for epsilon-nets [details]
April 12, Micha Sharir (Tel Aviv University): From joints to distinct distances and beyond: The dawn of an algebraic era in combinatorial geometry I [details]
Wednesday, April 13, Micha Sharir (Tel Aviv University): From joints to distinct distances and beyond: The dawn of an algebraic era in combinatorial geometry II [details]
April 14, Pankaj Agarwal (Duke University): Euclidean Bipartite Matching, Old and New Results [details]
April 19, Christoph Krautz: Firing-Rate Analysis in Feedforward-Inhibition Networks [details]
April 21, Emo Welzl: Kasteleyn and the Number of Crossing-Free Matchings and Cycles on a Planar Point Set [details]
April 26, Edward D. Kim (TU Delft): Polyhedral graph abstractions and weaker versions of the Hirsch Conjecture [details]
April 28, Lutz Warnke (University of Oxford): Achlioptas process phase transitions are continuous [details]

May 03, Anna Gundert: Counting "hypertrees": A generalization of Cayley's formula [details]
May 05, Adarsh Amirtham: Sperner's Lemma in Fair Division (student talk, 45 min.) [details]
Friday, May 06, József Solymosi (Univ. British Columbia, Canada): Pseudoline-Point Incidences [details]
Monday, May 09, Carsten Lange (FU Berlin): Optimal topological simplification of discrete functions on surfaces [details]
May 10, Torsten Mütze: Explicit matchings in the middle levels graph [details]
May 12, Luca Gugelmann: A Randomized Version of Ramsey's Theorem [details]
May 17, Robin Moser: Introduction to the PPSZ Algorithm [details]
May 19, Timon Hertli: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General [details]
May 24, Arnau Padrol (UPC Barcelona): Constructing Gale duals of neighborly polytopes [details]
May 26, Thomas Rast: Buffon machines [details]
May 31, Hanna Sumita: Simple Stochastic Games are LP-type problems (student talk, 45 min.) [details]

June 07, Jiří Matoušek (Charles Univ.): Discrepancy, Bansal's algorithm and the determinant bound [details]
June 09, Zuzana Safernová (Charles Univ.): On the nonexistence of k-reptile simplices in R^3 and R^4 [details]
June 21, Eric Sedgewick (DePaul Univ.): Recognition of a knot complement [details]
Wednesday, June 22, Martin Tancer (Charles Univ.): Good covers are algorithmically unrecognizable [details]
June 23, Boris Aronov (NYU Poly): Algebra can do amazing things [details]
June 28, Andrea Francke: A Metric Embedding: Ulam Metric into l_1 [details]

July 19, Chandrajit Bajaj (Univ. of Texas at Austin): Octrees Revisited: Efficient Energetic Calculations and Neighborhood Maintenance for Molecular Simulations [details]
July 28, in ML J37.1, Dominik Scheder: A very different algorithm for k-SAT [details]

August 09, Chandan Dubey: Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle [details]
August 11, Shakhar Smorodinsky (Ben-Gurion University): Hitting Sets Online and Vertex Ranking [details]

September 01, Joseph O'Rourke (Smith College, Northampton, MA, USA): New Methods for Unfolding Convex Polyhedra [details]
September 13, in ML J37.1, Yoshio Okamoto (Japan Advanced Institute of Science and Technology): Vertex Angle and Crossing Angle Resolution of Leveled Tree Drawings [details]
September 15, in ML J37.1, Philipp Hupp (TU München): On the I/O Complexity of Stencil Computations on 2 Dimensional Grids [details]
September 20, Dominik Scheder (Aarhus University): Truthful Mechanisms for Facility Location [details]
September 22, Thomas Dueholm Hansen (Aarhus University): Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor [details]
September 27, Heidi Gebauer: A Doubly Exponentially Crumbled Cake [details]
September 29, Sebastian Stich: The Johnson-Lindenstrauss Lemma [details]

October 04, Christoph Krautz: Interacting Maps for Fast Visual Interpretation [details]
October 06, Elad Hazan (Technion): Learning in the game of investing [details]
Monday, October 10, Amir Shpilka (Technion): Tight lower bounds for 2-query LCCs over finite fields [details]
October 13, Frank Mousset: Rainbow Paths in Proper Edge Colorings of Complete Graphs [details]
October 18, Sandro Bosio: A time extension of combinatorial optimization problems [details]
October 20, Tomasz Łuczak (Adam Mickiewicz University, Poznań, Poland): On a generalization of VC-dimension [details]
Friday, October 21, Tibor Szabó (Freie Universität Berlin): Sharp threshold for bounded degree spanning trees with many leaves or a long bare path [details]
October 25, Yves Brise: Range Assignment Problems [details]
October 27, Anastasios Zouzias (University of Toronto): A Matrix Hyperbolic Cosine Algorithm and Applications [details]

November 01, Vincent Kusters: Characterizing graphs with a sliceable rectangular dual [details]
November 03, Bernd Gärtner: Back to the Future - Computer Science for Kids [details]
November 08, Andreas Bärtschi: Conflict-free art gallery coverage (master's thesis) [details]
November 10, Martin Jaggi: Structured Sparsity [details]
November 15, Timon Hertli: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains [details]
November 17, Thomas Rast: Pancake flipping is NP-hard [details]
November 22, József Balogh (University of Illinois at Urbana-Champaign): On the Ramsey-Turan numbers of graphs and hypergraphs [details]
November 24, Henning Thomas: The Game Chromatic Number of Random Graphs [details]
November 29, Tobias Christ: Rational Tangles [details]

December 01, Isabelle Hurbain-Palatin: Sorting by placement and shift [details]
December 06, Gabriel Nivasch (EPFL): Upper bounds for centerflats [details]
December 08, Ueli Peter: The Degree Sequence of Hyperbolic Random Graphs [details]
December 13, Luca Gugelmann: Exponentially Many Matchings in Cubic Bridgeless Graphs [details]
December 15, Florian Jug: Neural Computation - Measurements and Models [details]
December 20, Christian Lorenz Müller: The Lovasz-Vempala algorithm for computing the volume of a convex body in O*(n⁴) - Theory and Implementation [details]