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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 2010

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, Sophia-Antipolis, France (Jun 2, 2010).

T. CHRIST
"Consistent digital line segments", 26th SoCG, Snowbird, Utah, USA (Jun 14, 2010).

K. FUKUDA
"On the complexity of Minkowski sums of polytopes", plenary talk, Workshop on Combinatorial Geometry and Algorithms, Tokyo Institute of Technology, Japan (Sep 21 2010).
"Recent advances in oriented matroids: Interplay between linearity and combinatorics", invited talk, Bernoulli Conference on Discrete and Computational Geometry, EPF Lausanne (Aug 30 - Sep 3 2010).

B. GÄRTNER
"Abstract Optimization - The German and the Swiss Approach", Informatik-Kolloquium, Universität Paderborn, Germany (Jun 22, 2010).
"Geometric Unique Sink Orientations", Conference on Geometric Graph Theory, EPF Lausanne, Switzerland (Sep 30, 2010).

H. GEBAUER
"Game Theoretic Ramsey Numbers", Mittagsseminar Diskrete Mathemtik, FU Berlin, Germany (Feb 23, 2010).
"Game Theoretic Ramsey Numbers", Workshop on Extremal and Probabilistic Combinatorics, Frauenchiemsee, Germany (Aug 25, 2010).

A. GUNDERT
"Introduction to Random Graphs", Arbeitsgemeinschaft on Topological Robotics, Math. Forschungsinstitut Oberwolfach, Germany (Oct 10, 2010).

M. HOFFMANN
"Plane Graphs with Parity Constraints", Noon Seminar, TU Eindhoven, Netherlands (Jan 18, 2010).
"Minimum and Maximum Against k Lies", 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Bergen, Norway (Jun 22, 2010).

R. MOSER
"Schöning's Walk-SAT Algorithm - Progress and Barriers", Random Graals 2010, The 5th Bertinoro Workshop on Randomized Algorithms and Graphs, Bertinoro (Forlì-Cesena), Italy (Jun 2, 2010).
"A Constructive Proof of The Lovász Local Lemma", The 24th European Conference on Operational Research (EURO XXIV), Lisbon, Portugal (Jul 13, 2010).
"A Constructive Proof of The Lovász Local Lemma", China Theory Week (CTW), Institute for Theoretical Computer Science, Tsinghua University, Beijing, China (Sep 12, 2010).

D. SCHEDER
"Unsatisfiable Linear CNF Formulas Are Large and Complex", 27th International Symposium on Theoretical Aspects of Computer Science (STACS '10), Nancy, France (Mar 4, 2010).
"Using a Skewed Hamming Distance to Speed Up Deterministic Local Search", Mitarbeiterseminar Logik in der Informatik, Humboldt-Universität Berlin (Apr 6, 2010).
"Using a Skewed Hamming Distance to Speed Up Deterministic Local Search", DMI, University of Novi Sad, Novi Sad, Serbia (Jun 9, 2010).
"A Full Derandomization of Schoening's k-SAT Algorithm", Seminar Talk, Max-Planck-Institut Saarbrücken, Germany (Oct 5, 2010).

M. SULOVSKÝ
"k-sets and continuous motion in R3", CCCG 2010, Winnipeg, Canada, (Aug 9, 2010).
"Crossing identities of k-edges and k-facets", Discrete and Computational Geometry Seminar, Ben-Gurion University of Negev, Be'er Sheva, Israel (Oct 26, 2010).
"k-facet crossing identities", Combinatorics Seminar, Technion and University of Haifa (joint seminar), Haifa, Israel (Nov 3, 2010).
"Conflict-free coloring geometric hypergraphs revisited", Culminating Workshop of the Semester on Discrete Geometry, EPF Lausanne, (Dec 2, 2010).

U. WAGNER
"Complete Minors in Simplicial Complexes", Combinatorics Seminar, The Hebrew University of Jerusalem, Israel (Jan 18 & 25, 2010).
"Complete Minors in Hypergraphs and Simplicial Complexes", Combinatorics Seminar, Tel-Aviv University, Tel-Aviv, Israel (Jan 24, 2010).
"Minors in Hypergraphs and Embeddability", Conference on Geometric Graph Theory, EPF Lausanne (Oct 1, 2010).
"Expansion and Minors in Hypergraphs", Culminating Workshop of the Semester on Discrete Geometry, EPF Lausanne, (Nov 30, 2010).
"On Gromov's method of selecting heavily covered points", Combinatorics Seminar, The Hebrew University of Jerusalem, Israel (Dec 28, 2010).

E. WELZL
"When Conflicting Constraints Can be Resolved - the Local Lemma and Satisfiability", Rejewski-Rózycki-Zygalski Lecture in Computer Science, Adam Mickiewicz University, Poznan, Poland (May 28, 2010).
"When Conflicting Constraints Can be Resolved - the Local Lemma and Satisfiability", Festkolloqium zu Ehren von Sabine Koppelberg, Martin Aigner, Ralph-Hardo Schulz, und Elmar Vogt, Berlin Free University, Berlin, Germany (Jul 10, 2010).


Courses and Seminars


top

Fall 10

See also the Course Catalogue

Spring 10

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.
Teach. Assistance Informatik I (D-MAVT) (Spring 10).
Contact Assitant Informatik (D-MATH, D-PHYS) (Fall 10).

T. CHRIST
Contact Assistant Computational Geometry (D-INFK) (Fall 10).

A. FRANCKE
Recipient of the Google Anita Borg Scholarship EMEA 2010
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 10).

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

B. GÄRTNER
Member of the CGAL Editorial Board.
Editor-in-Chief of CGAL (until April 30).
Program committee member of

Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Kursleiter "Programmieren fuer Kinder" an den Primarschulen Küsnacht und Kloten.

H. GEBAUER
Teach. Assistance Coordinator.
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 10).
Contact Assitant Graphs and Algorithms: Advanced Topics (D-INFK) (Fall 10).
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 10).

A. GUNDERT
Contact Assistant Graphs and Algorithms (D-INFK) (Spring 10).

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

M. JAGGI
Software Engineer Internship at Google Zurich (Feb - June 2010).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 10).

R. MOSER
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 10).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 10).

G. NIVASCH
Contact Assistant Metric Embeddings (D-INFK) (Spring 10).

D. SCHEDER
Contact Assistant Satisfiability of Boolean Formulas (D-INFK) (Fall 10).

M. SULOVSKÝ
Coordinator Mittagsseminar.
Contact Assistant Graph Drawing (D-INFK) (Spring 10).
Contact Assistant Algorithms Lab (D-INFK) (Fall 10).

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

Coreferee for dissertations of

Chair of the EATCS Award committee (with Eugenio Moggi and Pavlos Spirakis).

Member of the 2010 Rolf Nevanlinna Prize committee (with Ravindran Kannan (chair), Stanley Osher, Olivier Pironneau, Madhu Sudan).

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.