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

Talks in 2013

January

Monday, January 07, Christof Lutteroth (University of Auckland): Constraint-based User Interfaces - Specification and Solving [details]
January 10, Jan Foniok (Queen's University): Adjoint functors in graph theory [details]
January 15, Hemant Tyagi: Tangent space estimation for smooth embeddings of manifolds [details]
January 17, Vincent Kusters: On Universal Point Sets for Planar Graphs [details]
January 29, Emo Welzl: Upward Planar Orientations of Maximal Planar Graphs [details]

February

February 07, Daniel Graf: The Cops and Robbers Problem [details]
February 14, Matthias Mnich (Universitaet des Saarlandes): Max-Cut Parameterized above the Edwards-Erdos Bound [details]
February 19, Andrea Francke: On Perfect Matchings, Counting, Sampling, and Self-Reducibility [details]
February 21, Johannes Lengler: Drift Analysis - with applications to Yet Another Random Decline [details]
February 26, Yann Disser (TU Berlin): Stealing with Unknown Knapsack [details]
February 28, Pascal Schweitzer: Aspects of the Graph Isomorphism Problem [details]

March

March 05, Anna Gundert: A Cheeger Inequality in Dimension 2 [details]
March 07, Ueli Peter: Fast Simulation of the IDLA Process [details]
March 12, Torsten Mütze: Scheduling with few changes [details]
March 14, Asaf Ferber (Tel Aviv University): Counting and packing Hamilton cycles in dense graphs and oriented graphs [details]
Friday, March 15, in CAB G11, Christoph Lenzen (Massachusetts Institute of Technology): Early-deciding Consensus is Expensive [details]
March 19, Benjamin Doerr (MPI Saarbruecken): Mastermind With Many Colors [details]
Friday, March 22, in CAB G11, Jan Vondrak (IBM Almaden Research Center): Online Algorithms for Welfare Maximization in Allocation Problems [details]
March 26, Konstantinos Panagiotou (LMU Muenchen): Catching the k-NAESAT Threshold [details]
Wednesday, March 27, Dominik Scheder (Aarhus University): After Traxler and Amano: The relationship between average sensitivity, clause size, and solution density [details]
March 28, Heuna Kim (Korea Advanced Institute of Science and Technology): On the Numbers of Edges of a Fan-Crossing Free Graph [details]

April

April 02, Nemanja Skoric: On Stack Implementations on Turing Machines [details]
April 04, Antonis Thomas (University of Edinburgh): Pure Nash Equilibria and Treewidth [details]
April 09, Gianpaolo Oriolo (Università degli Studi di Roma): Large decomposition methods for independent sets in claw-free graphs [details]
April 11, Michel Verlinden: Sublinear-time algorithms for support vector machines [details]
April 16, Matias Korman (Universitat Politècnica de Catalunya): On the Complexity of Barrier Resilience for Fat Regions [details]
April 18, Yoichi Iwata (University of Tokyo): Linear Time FPT Algorithms [details]
April 23, Thilo Weghorn: Program Extraction in Constructive Analysis with the Proof Assistant MINLOG [details]
April 25, Michal Adamaszek (Universität Bremen): Extremal graph theory and flag manifolds [details]
April 30, József Solymosi (University of British Columbia): On Erdos' unit distances problem [details]

May

May 02, Uli Wagner (Institute of Science and Technology Austria): Helly vs. Betti [details]
Friday, May 03, in CAB G11, Nathan Linial (Hebrew University of Jerusalem): Simplicial complexes - A combinatorial perspective [details]
May 07, Manuel Wettstein: Algorithms for Counting and Enumerating Crossing-free Perfect Matchings on a Planar Point Set and Related Problems. [details]
May 14, Hafsteinn Einarsson: A short survey on bootstrap percolation [details]
May 16, Tillmann Miltzow (Freie Universität Berlin): Counting Exchange Stable Matchings [details]
May 21, Frank Mousset: Hypergraph Containers [details]
Wednesday, May 22, Marc Noy (Universitat Politècnica de Catalunya): Zero-one laws for minor-closed classes of graphs [details]
May 23, Komei Fukuda: Searching for a simplex region [details]
May 28, Vincent Kusters: Planar Packing of Binary Trees [details]
May 30, Sebastian Stich: The Stochastic Bandit Problem [details]

June

June 04, Zuzana Safernová (Charles University): Helly vs. Betti II [details]
June 06, Timon Hertli: Strong ETH Holds for Regular Resolution [details]
June 11, Katarzyna Mieczkowska (Adam Mickiewicz University): On Erdos' conjecture on matchings in hypergraphs [details]
June 13, Imre Bárány (Alfréd Rényi Mathematical Institute): Jarnik's convex lattice n-gon for non-symmetric norms [details]
June 18, Marek Elias (Charles University): Some Ramsey questions in discrete geometry [details]
June 20, Chandan Dubey: Search to Decision Reduction of Unique Shortest Vector Problem [details]

July

July 02, Edgardo Roldan-Pensado (University College London): An almost dual of Erdős-Szekeres [details]
July 04, Benjamin Matschke: The width of 5-dimensional prismatoids [details]
July 16, Hemant Tyagi: Continuum armed bandit problem of few variables in high dimensions [details]
Wednesday, July 17, in CAB G11, Mert Saglam (University of Washington): On the communication complexity of sparse set disjointness and exists-equal problems [details]
July 18, Julia Pap: Complexity of Hilbert bases, TDL-ness and g-polymatroids [details]
July 30, Ralph Keusch: The game chromatic number of dense random graphs [details]
Wednesday, July 31, Gal Kronenberg (Tel Aviv University): Random-turn Maker-Breaker games [details]

August

Wednesday, August 14, Mathias Schacht (Universität Hamburg): On the structure of dense graphs with small clique number [details]
August 15, Chengzhe Tian: Extending Network Motifs by Monotone Systems (Master Thesis) [details]
August 20, Sandro Feuz: Conjectured Lower Bounds for Dynamic Problems with a Communication Complexity Advice Model [details]
August 22, Christoph Schwirzer: Learning object classification fast [details]
August 27, May Szedlák: On the Cheeger Inequality for Simplicial Complexes [details]

September

September 03, Stefan Schneider (UC San Diego): A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits [details]
September 17, Humberto Naves: The maximum number of q-colorings in graphs [details]
September 19, Micha Sharir (Tel Aviv University): Recent progress on incidences and distinct distances: Variants of the Elekes-Ronyai problem [details]
September 24, Po-Shen Loh (Carnegie Mellon University): Anarchy is free in network creation [details]
Wednesday, September 25, Matan Harel (Courant Institute of Mathematical Sciences): Localization in Random Geometric Graphs with Too Many Edges [details]
September 26, Mike Molloy (University of Toronto): Frozen vertices in colourings of a random graph [details]
Friday, September 27, in CAB G61, Raimund Seidel (Universität des Saarlandes): Estimating the Number of Triangulations of a Planar Point Set [details]

October

October 01, Torsten Mütze: Binary Decision Diagrams - A general-purpose toolkit for combinatorial problems [details]
October 08, Johannes Lengler: The (F)utility of Choices [details]
October 10, Andreas Noever: A mixed density embedding lemma [details]
October 15, Miloš Stojaković (University of Novi Sad): Maker-Breaker games on random geometric graphs [details]
October 17, Sebastian Stich: Natural Gradient in Evolution Strategies [details]
October 22, Timon Hertli: A Faster Algorithm For Unique 3-SAT [details]
October 24, Roman Glebov: Finitely forcible graphons [details]
October 29, Felix Weissenberger: Two-Prover Games for Parallel Repetition [details]
October 31, Antonis Thomas: Using SETH to prove lower bounds for graph problems with bounded treewidth. [details]

November

November 05, Rajko Nenadov: On the threshold for the Maker-Breaker H-game [details]
November 07, Kerstin Weller (Univesity of Oxford): Connectivity of relatively bridge-addable classes of graphs [details]
November 12, Alexander Pilz (TU Graz): Combinatorial Algorithms for Combinatorial Problems: Selection of Extreme Points [details]
November 14, Nemanja Skoric: Hard problems imply efficient derandomization [details]
Monday, November 18, Noga Alon (Tel Aviv University and IAS, Princeton): The geometry of majority sequences [details]
November 19, Bernd Gärtner: Fourier-Motzkin Elimination [details]
November 21, Michael Farber (University of Warwick): Geometry and topology of random 2-dimensional complexes [details]
Friday, November 22, in CAB G11, Uli Wagner (Institute of Science and Technology Austria): Can a balloon be shrunk to a point in the presence of obstacles? --- An Introduction to Computational Homotopy Theory [details]
November 26, Hafsteinn Einarsson: Controlled Explosions: Restraining Bootstrap Percolation [details]
November 28, Frank Mousset: Counting graphs without large cliques [details]

December

December 03, Choongbum Lee (MIT): Two approaches to Sidorenko's conjecture [details]
December 05, Chandan Dubey: Counting solutions of Quadratic equations over quotient rings [details]
December 10, Nick Spooner: Edge-Based Representation Beats Vertex-Based Representation in Shortest-Path Problems [details]
December 12, David Conlon (University of Oxford): Cycle Packing [details]
December 19, Hemant Tyagi: The adversarial multi-armed bandit problem [details]

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)