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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 2008

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 Linear Arboricity of Odd Regular Graphs with Large Girth", Conference on Relations, Orderings, and Graphs in Computer Science (ROGICS 2008), Mahdia, Tunisia (May 13, 2008).
"Polychromatic Colorings of Plane Graphs", Symposium on Computational Geometry (SoCG 2008), Washington DC, USA (June 11, 2008).

Y. BRISE
"Violator Spaces - An Optimization Framework", Combinatorial Geometry and Optimization Seminar, EPFL, Lausanne (Nov 20, 2008).

T. CHRIST
"Improved Bounds for Wireless Localization", 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), Göteborg, Sweden (Jul 2, 2008).

K. FUKUDA
"Exact algorithms and software in optimization and polyhedral computation", The International Symposium on Symbolic and Algebraic Computation (ISSAC 2008), Hagenberg, Austria (Jul 20-23, 2008, tutorial lecture).

B. GÄRTNER
"Regular Unique Sink Orientations", Internationales Begegnungs- und Forschungszentrum für Informatik, Workshop on Design and Analysis of Randomized and Approximation Algorithms, Schloss Dagstuhl, Germany (May 14, 2008).
"Regular Unique Sink Orientations", Monday Lecture of the Graduiertenkolleg Methods for Discrete Structures, Freie Universität Berlin, Germany (May 19, 2008).
"Regular Unique Sink Orientations", Otto-von-Guericke-Universität Magdeburg, Germany (May 20, 2008).

H. GEBAUER
"On the Number of Hamilton Cycles in Bounded Degree Graphs", 5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2008), San Francisco, USA (Jan 19, 2008).
"On the number of Hamilton Cycles in 3-regular graphs", Discrete Mathematics and Optimization Seminar, McGill University, Montreal, Canada (Dec 1, 2008).

A. RAZEN
"A Lower Bound for the Transformation of Compatible Perfect Matchings", 24th European Workshop on Computational Geometry (EuroCG 2008), Loria Nancy, France (Mar 19, 2008).
"Number of Crossing-Free Geometric Graphs vs. Triangulations", Topological & Geometric Graph Theory (TGGT 2008), Paris, France (May 22, 2008).

P. SANKOWSKI,
"Algebraic Graph Algorithms", 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland (Aug 25, 2008; invited lecture).

M. SULOVSKÝ
"On Center Regions and Balls Containing Many Points", The 14th Annual International Computing and Combinatorics Conference (COCOON 2008), Dalian, China (Jun 29, 2008).

D. SCHEDER
"Guided Search and a Faster Deterministic Algorithm for 3-SAT", 8th Latin American Theoretical Informatics Symposium (LATIN 2008), Buzios, Brazil (April 7, 2008).
"How many conflicts does it need to be unsatisfiable?", 11th International Conference on Theory and Applications of Satisfiability Testing (SAT 2008), Guangzhou, China (May 15, 2008).

T. SZABÓ
"Thresholds for Positional Games", Mathematisches Forschungsinstitut Oberwolfach, Workshop on Combinatorics, Oberwolfach, Germany (Jan 8, 2008).
"Thresholds for biased positional games", Renyi Institute, Combinatorics Seminar, Budapest, Hungary (Feb 21, 2008).
"On the rules of avoiding", Special Session "Extremal and Probablistic Combinatorics", American Mathematical Society / Brazilian Mathematical Society Joint International Meeting, Rio de Janeiro, Brazil (Jun 5, 2008).
"Relaxed Colorings of Graphs", Minisymposium "Graph Coloring", 14th SIAM Meeting on Discrete Mathematics, University of Vermont, Burlington, USA (Jun 18, 2008).

P. TRAXLER
"The Time Complexity of Constraint Satisfaction", 3rd International Workshop on Parameterized and Exact Computation, Victoria, Canada (May, 2008).
"Exponential Time Complexity of Constraint Satisfaction", Internationales Begegnungs- und Forschungszentrum für Informatik, Seminar on Moderately Exponential Time Algorithms, Schloss Dagstuhl, Germany (Oct 23, 2008).

U. WAGNER
"Hardness of Embedding Simplicial Complexes", Theoretical Computer Science Seminar, Hebrew University of Jerusalem, Israel (Jul 16, 2008).
"Hardness of Embedding Simplicial Complexes", Computational Geometry Seminar, Tel-Aviv University, Israel (Jul 23, 2008).
"On the circle containment problem", Prague Midsummer Combinatorial Workshop, Czech Republic (Aug 1, 2008).
"Hardness of Embedding Simplicial Complexes", Workshop of Discrete Geometry, Oberwolfach, Germany (Sep 24, 2008).

E. WELZL
"Crossing Free Configurations on Planar Point Sets", Jahrestagung der Deutschen Mathematikervereinigung (DMV' 08), Erlangen, Germany (Sep 16, 2008; plenary lecture).

P. ZUMSTEIN
"On the Minimum Degree of Ramsey Minimal Graphs", Discrete Mathematics and Optimization Seminar, McGill University, Montreal, Canada (Nov 5, 2008).


Courses and Seminars


top

Fall 08

See also the Course Catalogue

Spring 08

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

R. BERKE
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Coordinator. (until Sep 12)
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

Y. BRISE
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 08).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

T. CHRIST
Teach. Assistance Algebraic Methods in Combinatorics (Fall 08).
Attended the conferences/courses/workshops:
MDS (Pre)Doc-Course 2008 - Random and Quasirandom Graphs, HU Berlin, Germany (May 5 - 9, 2008).
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

K. FUKUDA
Editorial Board Member of European J. Combinatorics, Computational Geometry: Theory and Applications, Applied Mathematics Research eXpress.
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

B. GÄRTNER
Coordinator ACS.
Member of the CGAL Editorial Board.
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

H. GEBAUER
Teach. Assistance Algorithms, Probability, and Computing (Fall 08).
Teach. Assistance Coordinator. (from Sep 13)
Attended the conferences/courses/workshops:
MDS (Pre)Doc-Course 2008 - Random and Quasirandom Graphs, HU Berlin, Germany (May 19 - 30, 2008).
5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 08), San Francisco, USA (Jan 19).
19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 08), San Francisco, USA (Jan 20 - 22).

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Program committee member of 16th Annual European Symposium on Algorithms (ESA 08), Engineering and Applications Track, Karlsruhe, Germany, (Sep 15-19, 2008).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

M. JAGGI
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

R. MOSER
Teach. Assistance Satisfiability of Boolean Formulas (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

A. RAZEN
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Theoretische Informatik (Fall 08).
Coordinator Mittagsseminar.
Attended the conferences/courses/workshops:
24th European Workshop on Computational Geometry (EuroCG 08), Loria Nancy, France (Mar 18 - 20, 2008).
MDS (Pre)Doc-Course 2008 - Random and Quasirandom Graphs, HU Berlin, Germany (May 5 - 9, 2008).
Topological & Geometric Graph Theory (TGGT 2008), Paris, France (May 19-23, 2008).
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

P. SANKOWSKI
Program committee member of ICALP 2009.

D. SCHEDER
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Algorithms, Probability, and Computing (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).
Building Bridges - A conference on mathematics and computer science in honour of László Lovász, Budapest, Hungary (Aug 5 - 9, 2008).
Fete of Combinatorics and Computer Science, An international conference on combinatorics and computer science, Keszthely, Lake Balaton, Hungary (Aug 11 - 15, 2008).

M. SULOVSKÝ
Teach. Assistance Approximate Methods in Geometry (Spring 08).
Teach. Assistance Computational Geometry (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).
The 14th Annual International Computing and Combinatorics Conference (COCOON 2008), Dalian, China (Jun 27 - 29, 2008).
Building Bridges - A conference on mathematics and computer science in honour of László Lovász, Budapest, Hungary (Aug 5 - 9, 2008).
Fete of Combinatorics and Computer Science, An international conference on combinatorics and computer science, Keszthely, Lake Balaton, Hungary (Aug 11 - 15, 2008).

P. TRAXLER
Teach. Assistance Anwendungsnahes Programmieren (Spring 08).
Teach. Assistance Informatik I (D-BAUG) (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zürich.

Program committee member of

Editorial Board member of

Member (chair, contact person) of selection committees for

Coreferee for dissertations of

Member of the EATCS Council (European Association for Theoretical Computer Science).
Member of the EATCS Award committee (with Catuscia Palamidessi, chair, and Pavlos Spirakis).
Member of the European Symposium on Algorithms (ESA)-steering committee.
Member of the peer evaluation committee of the Computer Science Department of the University of Vienna.

Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.

P. ZUMSTEIN
Teach. Assistance Datenstrukturen und Algorithmen (D-INFK) (Spring 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).
Building Bridges - A conference on mathematics and computer science in honour of László Lovász, Budapest, Hungary (Aug 5 - 9, 2008).