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

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Activity Report 2006

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
"Deciding Relaxed Two-Colorability", Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 11, 2006).
"Relaxed Two-Coloring of Cubic Graphs", Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17, 2006).
"Deciding Relaxed Two-Colorability - A Hardness Jump", 14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 13, 2006).

B. GÄRTNER
"Linear Programming and Unique Sink Orientations", 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, USA (Jan 23, 2006).
Short course: "Linear Programming Methods", Part of the Predoc-Course Optimization Methods in Discrete Geometry, Technical University Berlin, Germany (We/Th Apr 5-20, 2006).
"Simple Stochastic Games, Linear Complementarity Problems, and Unique Sink Orientations", London School of Economics, London, Great Britain (May 26, 2006).
"Clarkson's Randomized Linear Programming Algorithms Revisited", Mini-Symposium on Random Discrete Structures and Algorithms, Jahrestagung der Deutschen Mathematiker-Vereinigung, Universität Bonn, Germany (Sep 21, 2006).

M. HOFFMANN
"Connecting Line Segments", Symposium Diskrete Mathematik 2006, Technical University Berlin, Berlin, Germany (Apr 4, 2006).

L. RÜST
"Violator Spaces: Structure and Algorithms", 14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 12, 2006).

D. SCHEDER
"Approximation Algorithms for Multi-Criteria Traveling Salesman Problems", Fourth Workshop on Approximation and Online Algorithms, ETH Zurich, Switzerland (Sep 14, 2006).

E. SCHUBERTH
"A Framework for Image-dependent Gamut Mapping", IS&T/SPIE 18th Annual Symposium on Electronic Imaging, San Jose, USA (Jan 17, 2006).
"Approximate Sorting", Latin American Theoretical Informatics Symposium (LATIN), Valdivia, Chile (Mar 21, 2006).
"Preference Analysis", DIMACS Workshop on Polyhedral Combinatorics of Random Utility, DIMACS center, Rutgers University, New Jersey (May 24, 2006).
"Einführung in Java (Teil 2)", Schnupperstudium am Departement Informatik ETH Zurich, Switzerland (Aug 30 and Sep 1, 2006).
"A Kernel Approach to Gamut Boundary Determination", 14th European Signal Processing Conference (EUSIPCO), Florence, Italy (Sep 6, 2006).
"Psychovisuelle Tests für Parametrisierte Algorithmen", Meeting of Departement 292, EMPA Zurich, Switzerland (Nov 10, 2006).
"Frauenförderung am Departement Informatik der ETH Zürich - Erfahrungen und Motivation", Swiss ICT- KNIT, ETH Zurich, Switzerland (Nov 30, 2006).

T. SZABÓ
"Characters and the Projective Norm-Graphs", Doc-Course, Harmonic Analysis in Computer Science and Combinatorics, Charles University, Prague, Czech Republic (Feb 16, 2006).
"Relaxed Two-Coloring of Cubic Graphs", Theoretical Computer Science and Discrete Math Seminar, Institute for Advanced Study, Princeton, USA (Mar 20, 2006).
"Lower Bounds for Algorithms in Abstract Cubes", Discrete Math and Theory of Computing Seminar, Rutgers University, New Brunswick, USA (Mar 23, 2006).
"Making or Avoiding Planar Graphs", Geometry Seminar, Courant Institute, New York University, New York City, USA (Mar 28, 2006).
"Making, Breaking, Avoiding, Enforcing", Discrete Mathematics Seminar, Princeton University, Princeton, USA (Mar 29, 2006).
"Making vs Avoiding in Positional Games", Symposium Diskrete Mathematik 2006, Technical University Berlin, Berlin, Germany (Apr 3, 2006).
Short course: "Positional Games", Trimester Programme Phenomena in high dimension, Institute Henri Poincare, Paris, France (Apr 24-26, 2006).
"Making vs Avoiding in Positional Games" Workshop: Complexity of Games, Polyhedra and Lattice Points, FIM (Institute for Mathematical Research), ETH Zurich, Switzerland (May 18, 2006).
"Turán's Theorem in the Hypercube", Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 10, 2006).
"Turán's Theorem in the Hypercube", Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17, 2006).
"Relaxed Coloring of Cubic Graphs -- Extremal Graph Theory meeting Complexity Theory", Workshop on Combinatorics, Probability, and Computing, Mathematisches Forschungsinstitut Oberwolfach, Germany (Oct 29, 2006).
"Making vs. Avoiding in Positional Games", MHC Autumn School in Discrete Algorithms, Seto, Japan (Nov 15, 2006).

E. WELZL
"On the Number of Crossing-Free Matchings, (Cycles, and Partitions)", 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, USA (Jan 24, 2006).
"On the Number of Crossing-Free Configurations on Planar Point Sets", Colloquium Combinatorics, Geometry, and Computation, Technical University Berlin, Germany (Jan 30, 2006).
"Random Triangulations of Planar Point Sets", Workshop on Algorithmic Graph Theory, Mathematisches Forschungsinstitut Oberwolfach, Germany (Feb 14, 2006).
"On the Number of Triangulations and other Crossing-Free Configurations on Planar Point Sets", Discrete and Computational Geometry -- Twenty Years Later, AMS-SIAM Summer Research Conference, Snowbird, Utah, USA (Jun 22, 2006; invited talk).
"Random Triangulations of Planar Points Sets", V Jornadas de Matemática Discreta y Algorítmica (V JDMA), Campus de Soria, Universidad de Valladolid, Spain (Jul 13, 2006; invited talk).
"The Number of Crossing-Free Configurations on Planar Point Sets", 14th International Symposium on Graph Drawing, Karlsruhe, Germany (Sep 18, 2006; invited talk).
"On the Number of (and Random) Triangulations on Planar Point Sets", Workshop on Combinatorics, Probability, and Computing, Mathematisches Forschungsinstitut Oberwolfach, Germany (Nov 2, 2006).
"Lattice Triangulations", Colloquium Methods for Discrete Structures, Berlin Free University, Germany (Nov 13, 2006).
"Combinatorics of Boolean CNF Formulas", Ramakrishna Mission Vivekananda University, Belur Math, Howrah, West Bengal, India (Dec 12, 2006).
"The Number of Crossing Free Configurations on Finite Point Sets in the Plane", 26th Conference on Foundations of Software Technology and Theoretical Computer Science, Indian Statistical Institute, Kolkata, West Bengal, India (Dec 13, 2006; invited talk).


Courses and Seminars


top

Winter 05/06

Summer 06


Organization of Workshops etc.


top

Dissertations


top

Diploma/Master Theses


top

Semester Theses / Internship Projects


top

Miscellaneous


top

R. BERKE
Teach. Assistance Graph Theory (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
Symposium Diskrete Mathematik, Berlin, Germany (Apr 3-4, 2006).
Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 10-15, 2006).
Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17-21, 2006).
Summer School - Extremal Graph Theory and Random Graphs, Chorin, Germany (Jul 31 - Aug 4, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).

Y. BRISE
Attended the conferences/courses/workshops:
Algorithms for the SAT problem, Humboldt-Universität Berlin, Germany (Oct 27-29, 2006).

K. FISCHER
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS05/06).

K. FUKUDA
Courses taught:
"Predoc-Course: Polyhedral Computation", Optimization Methods in Discrete Geometry, Berlin, Germany (May 17 - Jun 2, 2006).
"Discrete and Algorithmic Geometry" (with A. Prodon), Graduate Course, EPF Lausanne, Switzerland (WS05/06).

Editor of European Journal of Combinatorics, Applied Mathematics Research eXpress.

Member of

B. GÄRTNER
Coordinator ACS.
Member of the CGAL Editorial Board.
Editor of a special issue of Computational Geometry: Theory and Applications on CGAL.
PhD examiner for Rahul Savani, London School of Economics, London, GB (Jun 26, 2006).

J. GIESEN
Program committee member of

M. HOFFMANN
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS05/06).
Informatik Koordinator.
Member of the CGAL Editorial Board.

S. LAKSHMINARAYANAN
Teach. Assistance External Memory Algorithms and Data Structures (WS05/06).

D. MITSCHE
Teach. Assistance Logik (WS05/06).
Coordinator Mittagsseminar (until Mar 31).

A. RAZEN
Teach. Assistance Erfüllbarkeit logischer Formeln (WS05/06).
Teach. Assistance Extremal Combinatorics (SS06).
Coordinator Mittagsseminar (since Apr 1).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation, Prague, Czech Republic (Feb 2 - Mar 3, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).

L. RÜST
Teach. Assistance Digitales Publizieren I: Farbwiedergabe (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
Summer School on Game Theory, University of Aarhus, Denmark (Jun 26-30, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).

D. SCHEDER
Teach. Assistance Logik (WS05/06).
Teach. Assistance Seminar SAT (SS06).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation, Prague, Czech Republic (Feb 2 - Mar 3, 2006).

E. SCHUBERTH
Teach. Assistance Algorithmische Geometrie (WS05/06).
Teach. Assistance Approximate Methods in Geometry (SS06).
Head of Frauenförderung.
Presentation of booth on Gamut Mapping and Psychovisual Tests at 25 Years of Computer Science at ETH exhibition "Die Welt zwischen 0 und 1" (Oct 20-29, 2006).
Attended the conferences/courses/workshops:
IS&T/SPIE 18th Annual Symposium on Electronic Imaging, San Jose, USA (Jan 15-19, 2006).
Latin American Theoretical Informatics Symposium (LATIN), Valdivia, Chile (Mar 20-24, 2006).
DIMACS Workshop on Polyhedral Combinatorics of Random Utility, DIMACS center, Rutgers University, New Jersey (May 24-26, 2006).
14th European Signal Processing Conference (EUSIPCO), Florence, Italy (Sep 4-8, 2006).

P. TRAXLER
Teach. Assistance Approximation: Theorie & Algorithmen (SS06).

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
Vice-Chair, Department of Computer Science, ETH Zurich (until Sep 30).

Program committee member of

Editorial Board member of

Member (chair, contact person) of selection committees for

Member of the EATCS Council (European Association for Theoretical Computer Science).

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.

Coreferee for habilitation of

P. ZUMSTEIN
Teach. Assistance Theory of Computing (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation, Prague, Czech Republic (Feb 2 - Mar 3, 2006).
Summer School - Extremal Graph Theory and Random Graphs, Chorin, Germany (Jul 31 - Aug 4, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).
Algorithms for the SAT problem, Humboldt-Universität Berlin, Germany (Oct 27-29, 2006).