Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 2011

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

Institut für Theoretische Informatik
Departement Informatik
ETH Zürichphone +41-44-632 73 92
CH-8092 Zürichfax+41-44-632 10 63


Personnel


top

Guests


top

Grants


top

Publications


top

Lectures


top

Y. BRISE
"Sparse Quadratic Programming Solver", CGAL Developer Meeting, Heraklion, Greece (Apr 13, 2011).

T. CHRIST
"Wireless Localization with Vertex Guards", 27th European Workshop on Computational Geometry (EuroCG), Morschach, Switzerland (Mar 28, 2011).
"Wireless Localization within Orthogonal Polyhedra", 23rd Canadian Conference on Computational Geometry (CCCG 2011), Fields Institute, Toronto, Canada (Aug 12, 2011).
"Beyond Triangulation: Covering Polygons with Triangles", 12th Algorithms and Data Structures Symposium (WADS 2011), NYU Polytech, Brooklyn, New York, U.S.A. (Aug 15, 2011).

B. GÄRTNER
"Support Vector Machines Meet Goldfarb Cubes", IPAM Workshop Efficiency of the Simplex Method - Quo Vadis Hirsch Conjecture, Institute for Pure And Applied Mathemtics, University of California in Los Angeles, USA (Jan 19, 2011).
"Leben und Karriere - wer muss sich anpassen?" Doktorandenkolloquium der Informatik Ruhr, Haus Nordhelle, Valbert, Germany (Oct 7, 2011)

H. GEBAUER
"The Local Lemma is Tight for SAT", 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, USA (Jan 24, 2011).
"Game Theoretic Ramsey Numbers", Pure mathematics seminar, Royal Holloway University of London, UK (Mar 1, 2011).
"Game Theoretic Ramsey Numbers", Combinatorics Study Group, Queen Mary University of London, UK (Mar 4, 2011).
"A Doubly Exponentially Crumbled Cake ", European Conference on Combinatorics, Graph Theory and Applications (EuroComb11), Rényi Institute, Budapest, Hungary (Aug 31, 2011).
"The Local Lemma is Tight For SAT", Combinatorial Geometry and Optimization Seminar, EPFL, Lausanne (Nov 3, 2011).

A. GUNDERT
"High-Dimensional 'Graph Theory'", 4th European Women in Mathematics Summer School, Lorentz Center, Leiden, The Netherlands (Jun 7, 2011).
"Expansion for 2-complexes", Noon Lecture, Department of Applied Mathematics (KAM), Charles University, Prague, Czech Republic (Oct 20, 2011).

T. HERTLI
"Improving PPSZ for 3-SAT using Crtitical Variables", 28th Symposium on Theoretical Aspects of Computer Science (STACS), TU Dortmund, Germany (Mar 10, 2011).
"3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General", China Theory Week (CTW), Department of Computer Science, Aarhus University, Denmark (Oct 10, 2011).
"3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General", 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs CA, USA (Oct 23, 2011).

M. HOFFMANN
"Counting Plane Graphs: Flippability and Its Applications", 12th Algorithms and Data Structures Symposium (WADS 2011), NYU Polytech, Brooklyn, New York, U.S.A. (Aug 15, 2011).
"Counting Plane Graphs: Pseudo-Flippability and Applications", Seminar of Algorithms Group, TU Eindhoven, The Netherlands (Oct 13, 2011).

R. MOSER
"A full derandomization of Schoening's k-SAT algorithm", Combinatorics, Mathematisches Forschungsinstitut Oberwolfach, Germany (Jan 4, 2011).
"A full derandomization of Schoening's k-SAT algorithm", Humboldt-Universität Berlin, Germany (Jan 14, 2011).
"A survey on exact algorithms for constraint satisfaction problems", Computational Complexity of Discrete Problems, Schoss Dagstuhl, Wadern, Germany (Mar 25, 2011).
"A full derandomization of Schoening's k-SAT algorithm", Computational Complexity of Discrete Problems, Schloss Dagstuhl, Wadern, Germany (Mar 25, 2011).
"A survey on exact algorithms for constraint satisfaction problems", Universität Ulm, Germany (Jun 14, 2011).
"A Full Derandomization of Schöning's Algorithm", 43rd annual ACM symposium on Theory of computing (STOC), San Jose, California, USA (Jun 6, 2011).

D. SCHEDER
"A Full Derandomization of Schoening's k-SAT Algorithm", Algorithms and Complexity Theory Seminar, Aarhus University, Denmark (Mar 2, 2011).
"A Full Derandomization of Schoening's k-SAT Algorithm", Seminar of Algorithms Group, Warsaw University, Poland (Mar 31, 2011).

S. STICH
"Random derivative-free optimization of convex functions using a line search oracle", 5th workshop on Theory of Randomized Search Heuristics (ThRaSH 2011) Copenhagen, Danmark (Jul 9, 2011).
"Gradient-free optimization with Random Pursuit", CGLearning Review Meeting/Workshop Zürich, Switzerland (Dec 15, 2011).

U. WAGNER
"On Gromov's method of selecting heavily covered points", Combinatorial Geometry Seminar, Tel-Aviv University, Israel (Jan 2, 2011).
"Complete Minors of Hypergraphs: Random and Expanding Hypergraphs", 27th Annual Symposium on Computational Geometry, Paris, France, (Jun 14, 2011).
"Isoperimetry, Crossing Numbers, and Multiplicities of (Equivariant) Maps", Workshop on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Germany, (Sep 7, 2011).
"Isoperimetric Inequalities in the Simplex and Multiplicities of Maps, after Gromov", ERC Workshop High-Complexity Discrete Geometry, Freie Universität Berlin, Germany, (Oct 25, 2011).

E. WELZL
"Zählen kreuzungsfreier Konfigurationen in der Ebene", Fakultätskolloquium, Department of Mathematics, Munich Technical University, Germany (Jan 25, 2011).
"When Conflicting Constraints Can be Resolved -- the Lovász Local Lemma and Satisfiability", Vienna ETH-day at The Erwin Schrödinger International Institute for Mathematical Physics, Vienna, Austria (Mar 4, 2011).
"Kasteleyn and the Number of Crossing-Free Matchings and Cycles on a Planar Point Set", Seminar on Computational Geometry, Leibniz-Center for Informatics, Schloss Dagstuhl, Germany (Mar 17, 2011).
"Counting Simple Polygonizations of Planar Point Sets", 23rd Canadian Conference on Computational Geometry (CCCG), Toronto, Canada (Aug 12, 2011; plenary talk).
"Counting Simple Polygonizations of Planar Point Sets", Seminar, Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, China (Oct 28, 2011).
"Counting Simple Polygonizations of Planar Point Sets", Friday Algorithms Seminar, University of Sydney, Sydney, Australia (Nov 11, 2011).


Courses and Seminars


top

Fall 11

See also the Course Catalogue

Spring 11

See also the Course Catalogue


Organization of Workshops etc.


top

Dissertations


top

Master and Diploma Theses


top

Bachelor and Semester Theses / Internship Projects


top

Miscellaneous


top

Y. BRISE
Webmaster www-gremo (until Oct 25).
Teach. Assistance Informatik I (D-MAVT) (Spring 11).
Contact Assistant Informatik (D-MATH, D-PHYS) (Fall 11).

T. CHRIST
Teach. Assistance Computational Geometry (Fall 11).

A. FRANCKE
Fulbright Foreign Student Grant 2011/12.
Visiting Student Researcher at the University of Washington, Seattle WA, USA (Sept 2011 - Aug 2012).

K. FUKUDA
Editorial Board Member of European J. Combinatorics, Computational Geometry: Theory and Applications, Applied Mathematics Research eXpress.

B. GÄRTNER
Member of the CGAL Editorial Board.

Program committee member of

Organisation des Kinderprogramms am Treffpunkt Science City (Nov 6, 2011).
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Kursleiter "Programmieren fuer Kinder" an der Primarschule Kloten.
Referent am 2. Schweizer Tag für den Informatikunterricht, Jan 14 2011.

H. GEBAUER
Teach. Assistance Coordinator (until Nov 20).
Contact Assistant Graphs and Algorithms: Advanced Topics (D-INFK) (Fall 11).

A. GUNDERT
Teach. Assistanc Topological Methods in Combinatorics and Geometry (Spring 11).

T. HERTLI
Teach. Assistance Coordinator (since Nov 20).
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 11).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 11).

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.

Program committee chair of

Program committee member of
Teach. Assistance Algorithms Lab (D-INFK) (Fall 11).

M. JAGGI
Teach. Assistance Graph Drawing (Spring 11).
Teach. Assistance Informatik I (D-MATH) (Fall 11).

V. KUSTERS
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 11).

R. MOSER
Coordinator Mittagsseminar (since Jun 23).
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 11).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 11).

G. NIVASCH
Program committee member of

D. SCHEDER
Teach. Assistance Informatik (D-BIOL, D-PHARM) (Spring 11).

S. STICH
Webmaster www-gremo (since Oct 25).
Teach. Assistance Algorithms Lab (D-INFK) (Fall 11).

M. SULOVSKÝ
Coordinator Mittagsseminar (until Jun 22).

U. WAGNER
Program committee member of

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich, and member of the board of the Department of Computer Science, ETH Zurich.

Program committee member of

Editorial Board member of

Member (chair, contact person) of selection committees for

Member of the

Mitglied der Lehrkommission (ehemalige Studienkommission) der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.
Mitglied der Unterrichtskommission des Departements Informatik der ETH Zürich.


Software


top