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

Talks in 2006

January

January 10, Maria Chudnovsky (Princeton Univ./CMI): Testing for a theta [details]
January 12, Samuel Zürcher: On 0-1-matrices and small excluded submatrices [details]
Monday, January 16, Kiyohito Nagano (Univ. of Tokyo): A strongly polynomial algorithm for line search in submodular polyhedra [details]
January 17, Eric Fusy (Ecole Polytechnique, Palaiseau Cedex): Random generation of combinatorial structures using Boltzmann samplers [details]
January 19, Mirco Fröhlicher: An Algorithm for Segment-Dragging [details]
January 24, Christian Balderer: A simple approximation algorithm for Connected Facility Location [details]
January 26, Thomas Bruderer: Comparing Top k Lists [details]
January 31, Takeaki Uno (National Institute of Informatics (NII): Maximization Problem of Intersection of Polytopes [details]

February

February 02, Andreas S. Schulz (MIT and ETH Zürich): Sometimes some NP-hard problems can be solved in polynomial time [details]
February 07, Joachim Giesen: Conformal Alpha Shapes [details]
February 09, Michael Mascagni (The Florida State Univ. and ETH Zürich): Random Number Generation: A Practitioner's Overview [details]
February 14, Eva Schuberth (with Dieter Mitsche): Collaborative Sorting [details]
February 16, Patrick Traxler (TU Wien): Recognizing Transversal Hypergraphs [details]
Monday, February 20, Martin Skutella (Univ. Dortmund): Computing earliest arrival flows with multiple sources [details]
February 21, Leo Rüst: Violator spaces [details]
Wednesday, February 22, Satoru Iwata (Tokyo University): Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems [details]
February 23, Masashi Kiyomi (National Institute of Informatics (NII): Enumerating Chordal Graphs [details]
February 28, Eva Schuberth: Approximate Sorting [details]

March

March 02, Joshua Cooper (Courant Inst., NYU and ETH Zürich): Deterministic Random Walks on the Integers [details]
March 07, Konstantinos Panagiotou: Extremal Subgraphs of Random Graphs [details]
March 09, Julian Lorenz: Optimal Execution of Portfolio Transactions [details]
March 16, Tobias Müller (Univ. of Oxford): Two-point concentration in random geometric graphs [details]
March 21, Takeaki Uno (National Institute of Informatics, Japan (NII): Constructing canonical form of Distance Hereditary Graphs [details]
March 23, Joshua Cooper (Courant Inst., NYU and ETH Zürich): Random Linear Extensions of Grids [details]
March 30, Andreas Weissl: Properties and Sampling of Tree-like Structures with Blocks of Higher Connectivity [details]

April

April 06, Sofya Raskhodnikova (Weizmann Institute of Science): Sublinear Algorithms for String Compressibility and the Distribution Support Size [details]
April 11, Jan Remy: A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation [details]
April 13, Tibor Szabó: Turan's Theorem in the hypercube [details]
April 18, Philipp Zumstein: Fourier Analysis in Computer Science and Combinatorics (Part I) [details]
April 20, Dominik Scheder: Fourier Analysis in Computer Science and Combinatorics (Part II) [details]
Friday, April 21, Akiyoshi Shioura (Tohoku Univ., Japan and Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB): Algorithms for M-convex Function Minimization [details]
April 25, Jiří Matoušek (Charles Univ., Prague): Zone diagrams [details]

May

May 02, Gábor Fejes Tóth (Hungarian Academy of Sciences): A short, unconventional introduction to packing and covering [details]
May 04, Jiří Matoušek (Charles Univ., Prague): On the Johnson-Lindenstrauss flattening lemma [details]
May 09, Miloš Stojaković (Univ. u Novom Sadu): The game of planarity [details]
May 11, Dan Hefetz (Tel Aviv Univ.): Minor games on the complete graph [details]
May 16, Pavel Valtr (Charles Univ., Prague): Traversing the cube [details]
May 23, Jakub Cerny (Charles Univ., Prague): Geometric and Topological Graphs with No Forbidden Subgraphs [details]
May 30, Stefan Geisseler: Overhang [details]

June

June 01, Reto Spöhel: Online Ramsey Games in Random Graphs [details]
June 06, Robin Moser: How good is the information theory bound in sorting? [details]
June 08, Robin Künzler: Optimal Search and One-Way Trading Online Algorithms [details]
June 13, Dominic Meier: On Enumerating Minimal Dicuts and Strongly Connected Subgraphs [details]
June 15, Björn Steffen: Closest-point problems simplified on the RAM [details]
June 20, Bettina Speckmann (Department of Mathematics and Computer Science, TU Eindhoven): Kinetic Collision Detection for Convex Fat Objects [details]
June 22, Eran Nevo (Department of Mathematics, Hebrew University): Combinatorial embedding obstructions for simplicial complexes [details]
June 27, Tetsuo Asano (School of Information Science, JAIST (Japan Advanced Institute of Science and Technology): Angular and Aspect-Ratio Voronoi Diagram with Applications [details]
Wednesday, June 28, Yoshio Okamoto (Toyohashi University of Technology): Enumeration Algorithmics for Multi-Criteria Optimization [details]
June 29, Shuji Kijima (The University of Tokyo): Perfect Sampler for Closed Jackson Networks [details]
Friday, June 30, Carsten Lange (University of Washington, Seattle): Realisations for the associahedron and the cyclohedron [details]

July

Wednesday, July 05, Csaba Dávid Tóth (Massachusetts Institute of Technology): Spanning Trees and Cuttings across Disks and Axis-Aligned Rectangles in Three-Space [details]
Wednesday, July 05, József Solymosi (Department of Mathematics, University of British Columbia,Vancouver, Canada): Examples of when number theory and incidence geometry intertwine [details]
July 11, Stefanie Gerke: Sequences with changing dependencies [details]
July 20, Felix Fischer (Univ. of Munich): Symmetries and the complexity of pure Nash equilibrium [details]
July 25, Yoshiharu Kohayakawa (Univ. de São Paulo): The size-Ramsey number of short subdivisions [details]
July 27, Marek Sulovský (Charles Univ., Prague): T-paths and Related Packing Problems [details]

August

August 29, Pavel Valtr (Charles Univ., Prague): Paths with no small angles [details]

September

September 07, Gregory B. Sorkin (IBM T.J. Watson Research Center): Faster solving, counting, and sampling [details]
September 19, Michael Krivelevich (Tel Aviv University): Packing Hamilton cycles in random graphs [details]
September 21, Venkatesan Guruswami (Univ. of Washington): Error-correction when Noise Overwhelms Correct Data [details]

October

October 03, Amin Coja-Oghlan (HU Berlin): Graph Partitioning via Adaptive Spectral Techniques [details]
October 05, Torsten Mütze (TU Dresden): Switch-Setting Games [details]
October 24, Emo Welzl: Encoding Lattice Triangulations [details]
October 26, Lars Engebretsen (Google Switzerland, Zurich): Computing in Unstable Environments [details]
October 31, Dominik Scheder: Fast deterministic algorithms for 3-SAT [details]

November

November 02, Andreas Razen: On the Number of Crossing-Free Partitions [details]
November 07, Riko Jacob: Optimal Randomized Comparison Based Algorithms for Collision [details]
November 09, Uli Wagner: Set pairs (and, time permitting, quadrupels) [details]
November 14, Fabian Kuhn (Microsoft Research Silicon Valley, California): Reconstructing Approximate Tree Metrics [details]
November 16, Philipp Zumstein: Satisfiability With Exponential Families [details]
November 21, Jan Remy: Prize-Collecting Point Sets [details]
November 23, Reto Spöhel: Asymmetric Ramsey Properties of Random Graphs [details]
November 28, Stefanie Gerke: Connectivity of random instances of addable graph classes [details]
November 30, Joachim Giesen (Max-Planck-Institut für Informatik, Saarbrücken): Medial Axis Approximation and Unstable Flow Complex [details]

December

December 05, Justus Schwartz: The Santa Claus Problem in a Probabilistic Setting [details]
December 07, Rico Zenklusen: A bound on the collection of edges in MST's of fixed-size subgraphs [details]
December 12, Michael Hoffmann: Maximizing Angles in Plane Straight Line Graphs (Part I) [details]
December 14, Tibor Szabó: Polychromatic edge-colorings of the hypercube (Part I) [details]
December 19, Paul Balister (Department of Mathematical Sciences, Univ. of Memphis): Cycle Decompositions [details]
December 21, Tibor Szabó: Polychromatic edge-colorings of the hypercube (Part II) [details]