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

Talks in 2009

January

January 13, Richard Královič: An Exponential Gap between Linear and Exponential Expected Time in Probabilistic Sweeping Finite Automata [details]
January 20, Konstantinos Panagiotou (Max-Planck-Institut für Informatik, Saarbrücken): Random Graphs from Classes with Constraints [details]
January 22, Panagiotis Cheilaris (City Univ. of New York and Rényi Institute): Online conflict-free coloring for geometric hypergraphs [details]
January 27, Christian Lorenz Müller (Mosaic Group): Stochastic search and randomized algorithms for energy landscapes (Part II) [details]

February

February 03, Sonny Ben-Shimon (Tel Aviv Univ.): Local resilience of regular graphs [details]
February 05, Birte Schrader (Mosaic Group): Diffusion operators in particle methods - constructing problem-independent kernel choice criteria [details]
February 10, Robin Moser: A Constructive Proof of the Lovász Local Lemma [details]
February 17, Andreas Razen: How to move a chair through a door (Part I) [details]
February 19, Michael Hoffmann: Happy points [details]
February 24, Kenya Ueno (The Univ. of Tokyo): A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints [details]
February 26, Viola Mészáros (Charles Univ., Prague): The Pizza Problem [details]

March

March 03, Patrick Traxler: Hashing techniques in exponential time complexity [details]
March 05, Rolf Harren (Max-Planck-Institut für Informatik, Saarbrücken): An Absolute 2-Approximation for Two-dimensional Bin Packing [details]
March 10, Philipp Zumstein: On Polychromatic 3- and 4-Colorings of Plane Graphs [details]
March 12, Michael Belfrage: Online Ramsey games involving trees [details]
March 17, Yves Brise: Disjoint Covering Number [details]
March 19, Anna Huber (Max-Planck-Institut für Informatik, Saarbrücken): Quasirandom Rumour Spreading [details]
March 24, Jo Helmuth (Mosaic Group): Analysis of Spatial Point Patterns in Live Cells [details]
March 26, Martin Jaggi: Kernels, Margins, Coresets and The Fight of High- vs. Low-Dimensional Spaces [details]
March 31, Rajesh Ramaswamy (Mosaic Group): A new class of highly efficient exact stochastic simulation algorithm for chemical reaction networks [details]

April

April 02, Sabrina Wiedersheim: Spanning Trees, Spiders and Snowflakes [details]
April 07, Florian Jug: Factor Fields [details]
Wednesday, April 08, David Belius (Univ. of Cambridge): Discrete Harmonic Analysis and the Divisible Sandpile [details]
April 14, Tobias Christ: How to Move a Chair Through a Door (Part II) [details]
April 16, Shai Ben-David (Univ. of Waterloo, Canada): New Theoretical Challenges emerging from Machine Learning applications [details]
April 21, Boris Bukh (Princeton Univ.): Geometric selection theorems [details]
April 23, Benny Sudakov (UCLA): Triangle packings and 1-factors in oriented graphs [details]
April 28, David Avis (McGill Univ., Montreal): The shelling property for polytopal digraphs [details]
April 30, Bernd Gärtner: K-Matrix Linear Complementarity Problems and Unique Sink Orientations [details]

May

May 05, Christian Helbling: Sokoban is PSPACE-complete [details]
May 07, Andrea Francke: The Euclidean Degree-4 Minimum Spanning Tree Problem is NP-hard [details]
May 12, Jiří Matoušek (Charles Univ., Prague): Kakeya's conjecture over finite fields according to Zeev Dvir [details]
Friday, May 15, Nathan Linial (Hebrew Univ. of Jerusalem, Israel): Topology meets the probabilistic method [details]
May 19, Marek Krčál (Charles Univ., Prague): Graph balancing [details]
Wednesday, May 20, Martin Tancer (Charles Univ., Prague): Non-representability of finite projective planes by convex sets [details]
May 26, Angelika Steger: Synchrony and Asynchrony in Neural Networks [details]
May 28, Robert E. Tarjan (Princeton Univ. and HP Labs): Rank-Balanced Trees [details]

June

June 02, Bálint Miklós (Applied Geometry Group): The Scale Axis Transform [details]
June 04, Gabriel Nivasch (Tel Aviv Univ., Israel): Encounters with the inverse Ackermann function [details]
June 09, Jan Foniok: Interlacing adjoints on directed graphs [details]
June 11, Micha Sharir (Tel Aviv Univ., Israel): Sharing joints, in moderation: A groundshaking clash between algebraic and combinatorial geometry [details]
June 16, Akitoshi Kawamura (Univ. of Toronto, Canada): Computational Complexity of Ordinary Differential Equations [details]
June 25, Rico Zenklusen: A Flow Model Based on (Poly-)Linking Systems [details]
June 30, Otfried Cheong (Korea Advanced Institute of Science and Technology - KAIST, Daejeon, South Korea): Lines pinning lines [details]

July

July 02, Lorenz Klaus: On the Number of Unique-Sink Orientations Arising from Pivoting in Linear Complementarity [details]
July 02, József Solymosi (Univ. British Columbia, Canada): Corners in Cartesian products [details]
July 14, Eran Nevo (Cornell Univ., Ithaca): Missing faces and generalized lower bounds on face numbers [details]
Monday, July 27, Shantanu Roy (Univ. of Basel): Towards Biomolecular Structure Prediction using Minima Hopping Algorithm [details]
July 28, Henning Thomas: Avoiding Monochromatic Giants in Edge-Colorings of Random Graphs [details]

August

August 27, Efi Fogel (Tel Aviv Univ., Israel): Polyhedral Assembly Partitioning with Infinite Translations or The Importance of Being Exact [details]

September

September 01, Monique Teillaud (INRIA Sophia Antipolis - Méditerranée): Computing 3D Periodic Triangulations [details]
Monday, September 07, Lutz Warnke: On the Evolution of K_{\ell+1}-free Graphs [details]
September 10, Dominik Scheder: Two-Coloring the Odd Cycle - A Short Introduction To Parallel Repetition [details]
September 15, Pietro Oliveto (Univ. of Birmingham, UK): Analysis of Diversity-preserving Mechanisms for Global Exploration [details]
Wednesday, September 16, Per Kristian Lehre (Univ. of Birmingham, UK): Runtime analysis of population-based EAs using non-selective family trees [details]
September 17, Luca Gugelmann: Random walks and electrical networks [details]
September 22, Tobias Müller (Tel Aviv Univ., Israel): Hamiltonicity of the random geometric graph [details]
September 24, Primoz Skraba (INRIA Saclay, France): Persistent Homology and Clustering [details]
September 29, Anna Gundert (FU/TU Berlin): An Extremal Problem for Embeddable Simplicial Complexes [details]

October

October 01, Thomas Rast: Positive and negative correlation [details]
October 06, Martin Jaggi: Approximate SDP solvers, Matrix Factorizations, the Netflix Prize, and PageRank [details]
October 08, Tobias Christ: Wireless Localization with Vertex Guards is NP-hard [details]
October 13, Heidi Gebauer: The Traveling Salesman Problem in Bounded Degree Graphs [details]
October 15, Uli Wagner: Complete Minors of Hypergraphs & Simplicial Complexes (Part 1. Definitions & Motivation) [details]
October 20, Jan Foniok: A combinatorial characterization of K-matrices [details]
October 22, Stefan Schneider: The Stable Marriage Problem (student talk, 45 min.) [details]
October 27, Torsten Mütze: The Search for Simple Symmetric Venn Diagrams [details]
October 29, Thomas Liphardt: Finding a Heaviest Triangle is not Harder than Matrix Multiplication (student talk, 45 min.) [details]

November

November 03, Yves Brise: C++ Templates are Turing complete [details]
November 05, Dan Hefetz: Playing to retain the advantage [details]
November 10, Andrei Giurgiu: Random Walk Algorithms for SAT (master thesis presentation) [details]
November 12, Jan Foniok: A combinatorial characterization of K-matrices (Part 2) [details]
November 17, Christoph Krautz: Sharpening Projections [details]
November 19, Marek Sulovský: A few words about continuous motion in geometry [details]
November 24, Andrea Francke: A simple proof of the upper bound theorem (student talk, 45 min.) [details]
November 26, Uli Wagner: Complete Minors of Hypergraphs & Simplicial Complexes (Part 2.) [details]

December

December 01, Gabriel Nivasch: On the Sprague-Grundy function for Wythoff's game [details]
December 03, Reto Spöhel: Upper bounds for asymmetric Ramsey properties of random graphs [details]
December 08, Miloš Stojaković (University of Novi Sad): Convex lattice polygons with small perimeter [details]
December 10, Konstantinos Panagiotou (MPI Saarbrücken): Sharp Load Thresholds for Cuckoo Hashing [details]
December 15, Robin Moser: Vectors in the Box [details]
December 17, Lutz Warnke (University of Oxford): A deletion method for local subgraph counts [details]