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

Talks in 2012

February 21, Yury Person (FU Berlin): Powers of Hamilton Cycles in Pseudorandom Graphs [details]
February 23, Michael Hoffmann: Counting Plane Graphs: Pseudo-Flippability and Applications [details]

March 06, Johannes Lengler: Evolutionary Algorithms on Quantum Computers [details]
March 15, Dominik Scheder (Aarhus University): A 29 Minutes Intro to Communication Complexity (Plus 1 Minute of Questions) [details]
Friday, March 16, in CAB G61, David Cimasoni (Université de Genève): Counting perfect matchings on graphs [details]
March 20, Yves Brise: Low Rank Updating of Matrix Factorizations [details]
March 22, Ueli Peter: How Random Is The Web? [details]
March 27, Vincent Kusters: Cinderella and the Wicked Stepmother [details]

April 03, Sebastian Stich: The Heavy Ball Method [details]
April 05, Henning Thomas: Mastermind [details]
April 17, Boris Bukh (University of Cambridge): Generalized Erdős-Szekeres theorems [details]
April 19, Komei Fukuda: Revisiting the polyhedral redundancy removal problem [details]
Monday, April 23, Hemant Tyagi (EPFL): Learning multi ridge functions in high dimensions via low rank matrix recovery [details]
April 24, Daniel Johannsen (Tel Aviv University): Embedding spanning trees in random graphs [details]
April 26, Matias Korman (Universitat Politècnica de Catalunya): Geometric problems in Ad-Hoc Networks [details]

May 03, Jean Cardinal (Université Libre de Bruxelles): The Clique Problem in Ray Intersection Graphs [details]
Friday, May 04, in CAB G11, Carsten Lange (Freie Universität Berlin): Posets and Polytopes [details]
Monday, May 07, Benny Sudakov (University of California, Los Angeles): The phase transition in random graphs -- a simple proof [details]
May 08, Ola Svensson (EPFL): Approximating Graphic TSP by Matchings [details]
May 10, Stephan Kollmann: Topology Learning in Spiking Recurrent Competitive Networks (Master thesis) [details]
May 15, Akaki Mamageishvili: The Unsatisfiability Threshold of Random Formulas [details]
May 22, Joshua Zahl (University of California, Los Angeles): A Szemerédi-Trotter theorem in R⁴ [details]
Wednesday, May 23, in CAB G61, Hang Zhou (ENS Paris): Approximation for Maximum Surjective Constraint Satisfaction Problems [details]
May 24, Anna Gundert: Expansion for 2-complexes [details]
May 29, Luca Gugelmann: Sharp thresholds and hypergraph 2-colorability [details]
May 31, Trinh Huynh: The Communication Complexity and Block Sensitivity of Search Problems [details]

June 12, in HG D5.2, Andrea Roth (INRIA Sophia-Antipolis): On Discrete Morse-Smale Decompositions and Bifurcations Diagrams [details]
June 14, in HG D5.2, Francis Sergeraert (Inst. Fourier, Grenoble): The Eilenberg-Zilber Combinatorial Contraction [details]
Friday, June 15, Reto Spöhel (MPI Saarbrücken): PAC learning and genetic programming [details]
June 19, Rajko Nenadov: On Counting Lemma for sparse graphs (Master thesis) [details]
June 21, Uri Zwick (Tel Aviv University): Lower bounds for randomized pivoting rules [details]

July 03, József Solymosi (University of British Columbia): On the Sum-Product Problem [details]
July 05, Peter Chvojka (Slovak University of Technology in Bratislava, Slovakia): Secret sharing schemes on nonstandard structures [details]
Friday, July 06, Daniel Tschudi: Complexity of Multi-Party Computations Secure Against General Adversaries [details]
July 10, Gerald Weber (University of Auckland): The Centroid is a Reference Point for the Symmetric Difference in d Dimensions [details]
July 12, Vissarion Fisikopoulos (National and Kapodistrian University of Athens): Constructing Polytopes via a Vertex Oracle [details]
Monday, July 16, Jan Foniok (Queen's University): Ramsey Classes Defined by Forbidden Homomorphisms [details]
July 17, Anton Krohmer (MPI Saarbrücken): Finding Cliques in Scale-Free Networks [details]

August 07, Micha Sharir (Tel Aviv University): Waiting for the ceiling to fall: On the longest path in the randomized incremental point-location DAG [details]
August 16, in HG D5.2, Otfried Cheong (Korea Advanced Institute of Science and Technology (KAIST), South Korea): Fan-Crossing Free Graphs and other edge crossing properties [details]
August 30, Andreas Noever: Online Ramsey Games for Triangles in Random Graphs [details]

September 11, Gábor Tardos (Alfréd Rényi Institute of Mathematics): Tight lower bounds for geometric epsilon nets [details]
September 11, in NO C44, Uwe Schöning (Universität Ulm): Probability Distributions for Local Search and Make versus Break [details]
Wednesday, September 12, in NO C44, Ignaz Rutter (Karlsruhe Institute of Technology (KIT)): Cubic Augmentation of Planar Graphs [details]
September 13, in NO C44, Friedrich Eisenbrand (EPFL): Subdeterminants and the Diameter of Polyhedra [details]
September 18, Robin Künzler: Does SAT have a Checker? [details]
September 20, Christian Sommer (MIT): Simple Cycle Separators and Recursive Decompositions for Planar Graphs [details]
September 25, Alexander Pilz (Graz University of Technology): Flip Distance Between Triangulations of a Simple Polygon is NP-Complete [details]
Wednesday, September 26, Raimund Seidel (Saarland University): An Aggregative Counting Algorithm for the Triangulations of a Planar Point Set [details]
September 27, Alexander Souza (Apixxo AG): Approximation Algorithms for Generalized and Variable Sized Bin Covering [details]

October 02, Jan Hazla: Concentration Bounds using Bayes' Rule [details]
October 04, Timon Hertli: Using Integrals to Compute Probabilities on Permutations [details]
October 09, Mihai Stupariu (University of Bucharest): Algorithms for curvature calculation in Digital Terrain Modelling [details]
October 16, Noga Alon (Tel Aviv University): On graphs and communication [details]
October 18, Robin Moser: Towards a Generalization of the PPSZ Algorithm to Larger Domains, Part I [details]
October 23, Sonoko Moriyama (Tohoku University): Holt-Klee condition on SEB cubes [details]
October 25, Sebastian Millius: Towards a Generalization of the PPSZ Algorithm to Larger Domains, Part II [details]
October 30, Hafsteinn Einarsson: One shot learning [details]

November 01, Federico Padua: Search for CP violation in the charm decays with the BaBar experiment [details]
November 13, Francisco Valero-Cuevas (University of Southern California): Applications of vertex enumeration to understanding the neural control of musculature [details]
November 15, in HG D5.2, Ueli Peter: Compressing Separable Graphs [details]
Friday, November 16, in HG D3.2, Dominik Scheder (Aarhus University): Exponential Lower Bounds for the PPSZ k-SAT Algorithm [details]
November 20, Johannes Lengler: Black Box Complexities [details]
November 22, Gerth Stølting Brodal (Aarhus University): Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree [details]
Friday, November 30, Michael Kaufmann (Universität Tübingen): On Partial Edge Drawings [details]

December 04, Sebastian Stich: Variable Metric Random Pursuit [details]
December 06, Henning Thomas: Dependent Random Choice [details]
December 11, Anna Gundert: The Containment Problem for Random 2-Complexes [details]
December 13, Carla Michini: The Hirsch Conjecture for the Fractional Stable Set Polytope [details]
December 18, Wolfgang Woess (Graz University of Technology): On the duality between jump processes on ultrametric spaces and random walks on trees [details]
December 20, Bernd Gärtner: Semiproduct Unique Sink Orientations [details]