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

Talks in 2007

January

January 04, Johann A. Makowsky (Technion IIT, Haifa): Why is the chromatic polynomial a polynomial [details]
Friday, January 05, Boris Aronov (Department of Computer and Information Science, Polytechnic Univ., Brooklyn NY): Sparse geometric graphs with small dilation [details]
January 09, Martin Marciniszyn: Resilience of Random Graphs [details]
January 11, Julian Lorenz: Optimal Competitive Algorithms for the k-Search Problem with Application in Robust Valuation of Lookback Options [details]
January 16, Leslie Valiant (Division of Engineering and Applied Sciences, Harvard Univ.): Robust Logics [details]
January 18, Tobias Christ: An Introduction to Homogenization Theory [details]
January 23, Jan Hladky (Charles Univ., Prague): Maximum matching in graphs: an algebraic approach [details]
January 25, Robert Berke: The Morphism Chromatic Number - Between Layouts and Colorings [details]
January 30, Bernd Gärtner: Random Walks on Polytope Digraphs - Episode I [details]

February

February 06, Alexander Engström (KTH Stockholm): A proof of a conjecture of Björner on simplicial polytopes [details]
February 08, Dan Hefetz (Tel Aviv Univ.): Fast winning strategies in positional games [details]
Friday, February 09, Kiyohito Nagano (Univ. of Tokyo): Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization [details]
February 13, Miloš Stojaković (Univ. u Novom Sadu): Slow losing strategies in positional games [details]
February 15, Patrick Traxler: Unique Satisfiability [details]
February 20, Florian Zickfeld (TU Berlin): Counting Graph Orientations with Fixed Out-Degrees [details]
February 27, Marc Noy (Univ. Politècnica de Catalunya): Growth of minor-closed families [details]

March

March 01, Anusch Taraz (TU München): An Erdős-Stone type theorem for spanning subgraphs [details]
March 08, Dominik Scheder: Partial Satisfaction [details]
March 15, Marek Sulovský: Lower bounds for the rectilinear crossing number [details]
March 20, Elias Vicari: The Fascinating World of Micro-Robots [details]
March 22, Andreas Razen: Transforming Spanning Trees [details]
March 27, Leo Rüst: The Hidden-K-Matrix Linear Complementarity Problem [details]
March 29, Yves Brise: LP-type problems, a linear time algorithm further simplified [details]

April

April 03, Micha Sharir (Tel Aviv Univ.): Weak epsilon nets in convex position: (inverse) Ackermann strikes again [details]
April 05, Penny Haxell (Univ. of Waterloo): On stable paths [details]
April 10, Jack Snoeyink (Univ. of North Carolina at Chapel Hill): Questions for graph rigidity from modeling allostery [details]
April 17, Eva Schuberth: Measuring the Perceived Quality of Visualization Algorithms using Conjoint Analysis [details]
April 19, Rahul Savani (Department of Computer Science, Univ. of Warwick, UK): From discounted payoff games to P-matrix linear complementarity problems [details]
April 24, Dominik Scheder: Unsatisfiable Linear k-CNF Formulas [details]
April 26, Petr Škovroň (Charles Univ., Prague): Removing degeneracy may require unbounded dimension increase [details]

May

May 03, Jiří Matoušek (Charles Univ., Prague): How many points can be reconstructed from k projections? [details]
May 08, Fabian Kuhn: On the Complexity of Distributed Graph Coloring [details]
May 15, Julian Lorenz: Observational Learning in Random Networks [details]
May 22, Joachim Giesen (Max-Planck-Institut für Informatik, Saarbrücken): Total Absolute Gaussian Curvature of a surface mesh [details]
May 24, Nicla Bernasconi: Properties of Random Graphs via Boltzmann Samplers [details]
May 29, Jack Snoeyink (Univ. of North Carolina at Chapel Hill): Convex hulls of intersections of line segments and planes [details]
May 31, Jiří Matoušek (Charles Univ., Prague): Large Monochromatic Components in Two-colored Grids [details]

June

June 05, Martin Dietzfelbinger (Technische Univ. Ilmenau): Blind search on the integers [details]
June 07, Hossein Hajiabolhassan (Shahid Beheshti Univ., Tehran): Graphs homomorphisms and spectral conditions [details]
June 12, Bernd Gärtner: Exactly solving linear and quadratic programs in CGAL [details]
June 14, Michał Karoński (Univ. of Poznań, Poland): Irregular assignments [details]
June 19, Reto Spöhel: Euclidean Vehicle Routing with Allocation [details]
June 26, Subir Ghosh (Tata Institute of Fundamental Research, Mumbai, India): Computing the maximum clique in visibility graphs [details]
Friday, June 29, Jared Saia (Computer Science Department, Univ. of New Mexico): Attack-Resistant Algorithms for Massive Networks [details]

July

Friday, July 13, Torsten Mütze: Understanding Radio Irregularity in Wireless Networks [details]
July 17, Tobias Christ: On Dinur's Proof of the PCP Theorem - Part I [details]
Wednesday, July 18, Sonja Čukić (Binghamton University, USA): Why topology is fun. Sometimes... [details]
Wednesday, July 18, Karl Lieberherr (Northeastern Univ., Boston): The Evergreen Game: The Promise of Polynomials to Boost Boolean MAX-CSP Solvers [details]
July 19, Tobias Christ: On Dinur's Proof of the PCP Theorem - Part II [details]

August

August 07, Trung Nguyễn (INRIA Sophia Antipolis Research Unit, France): A disk-covering problem with application in optical interferometry [details]
August 14, Eric Fusy (Laboratoire d'Informatique, LIX, France): On a family of plane triangulations: combinatorial study, straight-line drawing, and analysis [details]
August 21, Walter Morris (George Mason Univ., Virginia): Good Hidden P-matrix Sandwiches [details]

September

September 25, Rico Zenklusen: High-Confidence Estimation of Small s-t Reliabilities in Acyclic Networks [details]
September 27, Michael Hoffmann: Maximizing Angles in Plane Straight Line Graphs (Part II) [details]

October

October 02, Michael Krivelevich (Tel Aviv Univ.): Avoiding small subgraphs in Achlioptas processes [details]
October 04, Penny Haxell (Univ. of Waterloo): Independent dominating sets and Hamilton cycles [details]
October 09, Yves Brise: On the Autocorrelation of Sets of Disks [details]
October 11, Philipp Zumstein: On the Minimum Degree of Ramsey Minimal Graphs [details]
October 16, Dominik Scheder: Saving Space -- Two Classical Results from Complexity Theory [details]
October 18, Andreas Razen: Transforming Perfect Matchings [details]
October 23, Marek Sulovský: Curves and Arrangements [details]
October 25, Konstantinos Panagiotou: On the Chromatic Number of Random Graphs [details]
October 30, Patrick Traxler: Constraint Systems and the Number of their Solutions [details]

November

November 01, Gabriel Katz: Jenga [details]
November 06, Justus Schwartz: Computation of Lower Bounds for Steiner Trees in Road Network Design [details]
November 08, Jan Foniok: Generating Tree Duality: A Quest for Deltas and Sproinks [details]
November 15, Lorenz Klaus: k-Sets in Three Dimensions [details]
November 20, Dan Hefetz: Antimagic graphs via the Combinatorial Nullstellensatz [details]
November 22, Herbert Edelsbrunner (Arts and Sciences Professor of Computer Science and Mathematics, Duke Univ.): Measuring Periodicity in Gene Expression with Persistence [details]
November 27, Divesh Aggarwal: The Angel of Power 2 wins [details]
November 29, Heidi Gebauer: On the Number of Hamilton Cycles in 3-regular Graphs [details]

December

December 04, Reto Spöhel: On Von Neumann Poker with Community Cards [details]
December 06, Andreas Razen: On the Number of Crossing-Free Geometric Graphs (Part I) [details]
December 11, Tibor Szabó: On the rules of avoiding [details]
Wednesday, December 12, Anna Hanulová: A short list color proof of Grötzsch's Theorem [details]
December 13, Julian Lorenz: Adaptive Execution of Portfolio Transactions [details]
December 18, Micha Sharir (Tel Aviv Univ.): On Lines Meeting Convex Polyhedra - Ray Shooting and Transversals [details]
December 20, Jörg Priewasser: Exact and approximative algorithms for coloring G(n,p) [details]