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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 2007

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

R. BERKE
"The Morphism Chromatic Number", 21st British Combinatorics Conference (BCC 07), University of Reading, UK (Jul 10, 2007).
"Transversals in Multipartite Graphs", Oxford Combinatorics Seminar, Oxford, UK (Jul 17, 2007).
"Deciding relaxed two-colorability", Theory Seminar, CS Departement, SFU, Vancouver, BC, Canada (Sep 19, 2007).

B. GÄRTNER
"Solving Linear and Quadratic Programs in CGAL", ACS General Workshop, FU Berlin, Germany (May 11, 2007).
"Approximate smallest enclosing ellipsoids in CGAL", ACS Workshop on Robust Shape Operations, INRIA, Sophia Antipolis, France (Sep 28, 2007).

M. HOFFMANN
"Maximizing Maximal Angles in Planar Straight Line Graphs", Complexity Theory and Algorithmics Seminar, University of Liverpool, UK (Nov 8, 2007).

A. RAZEN
"Transforming Spanning Trees: A Lower Bound", 23rd European Workshop on Computational Geometry (EuroCG 07), TU Graz, Austria (Mar 20, 2007).

D. SCHEDER
"Partial Satisfaction of k-Satisfiable Formulas", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 07) , Seville University, Sevilla, Spain (Sep 14, 2007).

T. SZABÓ
"On a Hamiltonicity Criterion and Positional Games", Workshop on Quasi-random structures, regularity lemmas and their applications, Renyi Institute, Budapest, Hungary (Jan 25, 2007).
"Relaxed Coloring of Cubic Graphs -- a Hardness Jump", Combinatorics Seminar, Renyi Institute, Budapest, Hungary (Feb 22, 2007).
"Maker-Breaker Games on the Complete Graph", Miniworkshop on Positional Games, Mathematisches Forschungsinstitut Oberwolfach, Germany (Apr 9, 2007).
"Avoider-Enforcer Games on the Complete Graph", Miniworkshop on Positional Games, Mathematisches Forschungsinstitut Oberwolfach, Germany (Apr 10, 2007).
"Random graph intuition and pseudorandomness in positional games", Mathematics Colloquium, EPFL, Lausanne, Switzerland (May 10, 2007).
"Pseudorandomness in positional games", 13th International Conference on Random Structures and Algorithms, Tel Aviv University, Tel Aviv, Israel (May 31, 2007).
"On the randomized simplex algorithm in abstract cubes", Optimization and Applications Seminar, ETH Zurich and University of Zurich, Switzerland (Nov 19, 2007).
"Random graph intuition and pseudorandomness in positional games", Monday Lecture of the Research Training Group "Methods for Discrete Structures", Freie Universität Berlin, Berlin, Germany (Dec 3, 2007).

U. WAGNER
"h-Matrices of Levels in Arrangements", Cornell Discrete Geometry and Combinatorics Seminar, Cornell University, Ithaca, USA (Nov 26, 2007).

E. WELZL
"Counting Crossing-Free Configurations on Planar Point Sets", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 07), Seville University, Sevilla, Spain (Sep 12, 2007; invited talk).
"Counting of Crossing-Free Geometric Graphs", Significant Advances in Computer Science (SACS 07), Graz University of Technology, Graz, Austria, (Nov 6, 2007).

P. ZUMSTEIN
"Satisfiability with Exponential Families", Tenth International Conference on Theory and Applications of Satisfiability Testing (SAT 07), Lisbon, Portugal (May 29, 2007).


Courses and Seminars


top

Fall 07

Summer 07

Winter 06/07


Organization of Workshops etc.


top

Dissertations


top

Master and Diploma Theses


top

Bachelor and Semester Theses / Internship Projects


top

Miscellaneous


top

R. BERKE
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Diskrete Mathematik (SS07).
Teach. Assistance Informatik II (D-BAUG) (SS07).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
21st British Combinatorics Conference (BCC 07), Reading University, UK, (Jul 9-13, 2007).
Combinatorial Potlatch, University of Victoria, BC, Canada, (Sep 29, 2007).

Y. BRISE
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Geometric Computations in Molecular Biology (SS07).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 07).
Webmaster www-gremo (since June).

T. CHRIST
Teach. Assistance Diskrete Mathematik (D-ITET) (WS06/07).
Teach. Assistance Diskrete Mathematik (SS07).
Teach. Assistance Theory of Computing (Fall 07)
Attended the conferences/courses/workshops:
The Victor Rothschild Memorial Symposium, 11th Midrasha Mathematicae, Polytopes Graphs and Convexity, Hebrew University of Jerusalem, Israel (May 6-11, 2007).

K. FUKUDA
Member of Organization committee for 5th Joint IBM-Swiss OR Days
Editorial Board Member of European J. Combinatorics, Computational Geometry: Theory and Applications, Applied Mathematics Research eXpress.

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

H. GEBAUER
Teach. Assistance Algorithms, Probability, and Computing (Fall 07).

M. HOFFMANN
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Graphs & Algorithms: Advanced Topics (Fall 07).
Informatik Koordinator.
Member of the CGAL Editorial Board.

M. JAGGI
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 07).

D. MITSCHE
Teach. Assistance Theory of Computing (WS06/07).

A. RAZEN
Teach. Assistance Graph Theory (WS06/07).
Teach. Assistance Discrete Geometry (SS07).
Teach. Assistance Diskrete Mathematik (Fall 07).
Coordinator Mittagsseminar.
Attended the conferences/courses/workshops:
23rd European Workshop on Computational Geometry (EuroCG 07), TU Graz, Austria, (Mar 19 - 21, 2007).
The Victor Rothschild Memorial Symposium, 11th Midrasha Mathematicae, Polytopes Graphs and Convexity, Hebrew University of Jerusalem, Israel (May 6-11, 2007).

L. RÜST
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Diskrete Mathematik (SS07).
Webmaster www-gremo (until June).

D. SCHEDER
Teach. Assistance Erfüllbarkeit logischer Formeln (SAT) - Kombinatorik und Algorithmen (WS06/07).
Teach. Assistance Datenstrukturen & Algorithmen (SS07).
Teach. Assistance Seminar SAT (SS07).

E. SCHUBERTH
Teach. Assistance Algorithmische Geometrie (WS06/07).
Head of Frauenförderung.

M. SULOVSKÝ
Teach. Assistance Theoretische Informatik (WS06/07).
Teach. Assistance Approximate Methods in Geometry (SS07).
Teach. Assistance Algorithmische Geometrie (Fall 07).
Attended the conferences/courses/workshops:
The Victor Rothschild Memorial Symposium, 11th Midrasha Mathematicae, Polytopes Graphs and Convexity, Hebrew University of Jerusalem, Israel (May 6-11, 2007).

P. TRAXLER
Teach. Assistance Algorithms, Probability, and Computing (WS06/07).
Teach. Assistance Datenstrukturen & Algorithmen (SS07).
Teach. Assistance Algorithms, Probability, and Computing (Fall 07).

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.

Program committee member of

Program committee chair of

Editorial Board member of

Member (chair, contact person) of selection committees for

Member of the EATCS Council (European Association for Theoretical Computer Science).
Member of the EATCS Award committee (with Catuscia Palamidessi and David Peleg, chair).

Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Algorithmik grosser und komplexer Netzwerke" der Deutschen Forschungsgemeinschaft (DFG).
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.
Election to the Berlin-Brandenburg Academy of Sciences (Mathematisch-Naturwissenschaftliche Klasse).

P. ZUMSTEIN
Teach. Assistance Algorithms, Probability, and Computing (WS06/07).
Teach. Assistance Extremal Combinatorics (SS07).
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 07).