Department of Computer Science
Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
People
Activity Report
    2009
Previous Reports
Research
Mittagsseminar
Teaching
Workshops
Social Activities
Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2009

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


Guests


Grants

  • Combinatorial and Computational Aspects of Embeddings

    (Financed by the Swiss National Science Foundation). The goal of this project is to study combinatorial and algorithmic questions related to the embeddability of simplicial complexes into Euclidean space and obstructions thereto. For graphs, the study of such questions has a long history and is best exemplified by classical results such as Euler's polyhedral formula, Kuratowski's characterization of planar graphs in terms of forbidden minors, or the fact that planarity is testable in linear time.
    On the topological side, embeddings of polyhedra and obstructions to their existence are also a classical and well studied topic in geometric topology. However, in contrast to the closely related topic of classifying embeddings up to isotopy, in particular knot theory, which has been studied extensively also from an algorithmic viewpoint, the computational complexity of the embeddability problem had, until recently, not been addressed.
    The first part of the present project concerns the systematic study of this complexity question. Together with J. Matousek and Martin Tancer, we have shown that embeddability of a given simplicial complex is at least NP-hard to test for a wide range of the parameters (dimension k of the complex and ambient dimension d), essentially, if they fall outside the metastable range of the Haefliger-Weber Theorem. Moreover, in some cases the problem is even algorithmically undecidable. Numerous open problems remain, such as elucidating the complexity situation within the metastable range.
    The second part of the project is concerned with extremal problems for simplicial complexes and with threshold phenomena for random simplicial complexes as introduced by Linial and Meshulam, both in the context of embeddability. A fundamental extremal question is, for instance: How many triangles can a 2-dimensional simplicial complex contain (in terms of the number of vertices or the number of edges) if it admits an embedding into 4-space? The corresponding question for random complexes is: If K is a 2-dimensional complex on n vertices where every possible triangle is chosen independently with probability p, what is the threshold probability p=p(n) for K being embeddable in 4-space?

    Contact: U. Wagner

  • k-Sets and Geometric Graphs

    (Financed by the Swiss National Science Foundation). The goal of this project is to investigate two basic and interrelated problems in discrete and computational geometry.
    The first part concerns triangulations and crossing-free geometric graphs in the plane. These structures are omnipresent, for example optimal Euclidean matchings, spanning trees and tours are crossing-free, triangulations provide structure to scattered points sets, etc. Moreover, combinatorial structures relate to this notion, e.g. well-formed parenthesis expressions or binary trees.
    While the situation is well-understood for point sets in convex position (then it amounts to Catalan structures whose investgation goes back to Euler around 1750), the general setting is much less understood. This concerns extremal problems, algorithmic counting and enumeration.
    The second part of the project concerns the combinatorics partitioning point sets in the plane by a line into two parts of prescribed sizes. The question how many such partitions there can be for a point set of a given size is known as the "k-set problem". Apart from its intrinsic interest as a combinatorial question, this problem arises in the analysis of a number of geometric algorithms, and also turns out to be pivotal for numerous other geometric questions, some of which seem at first quite unrelated.
    One focus of this part will be on identities for k-sets and k-facets through continuous motion, in particular in the 3-dimensional case. Moreover, we plan to further investigate applications of k-sets to other geometric problems, e.g. circle and sphere containment problems and to rectilinear crossing numbers.

    Contact: U. Wagner

  • Support Vector Machines: Geometry, Combinatorics and Algorithms

    (Financed by the Swiss National Science Foundation). The goal of this project is to study the geometric, combinatorial, and algorithmic foundations of support vector machines (SVM). The focus is on techniques that are orthogonal to the techniques used and developed in the machine learning community. The project will be carried out as an (inter)national collaboration, with two partners from Switzerland (ETH Zürich), and one partner from Germany (Friedrich-Schiller-Universität Jena).

    Contact: Bernd Gärtner

  • Boolean Satisfiability - Combinatorics and Algorithms

    (Financed by the Swiss National Science Foundation.) SAT is the problem of deciding whether a boolean formula in propositional logic is satisfiable, i.e. whether there is a true/false assignment to the boolean variables so that the given formula evaluates to true. The problem is of importance in various areas of computer science, including algorithmics, artificial intelligence, and program and system verification. Frequently, problems are modeled as SAT instances, and SAT-solvers like Mini-SAT, zCHAFF, HaifaSAT, etc. are used to solve such instances.

    This project concentrates on the theoretical aspects of the problem, which plays a key role in theoretical computer science for several reasons, one being that it is considered the `mother' of NP-complete problems. The goal of the project is to obtain a deeper understanding of the computational complexity of SAT and the structural properties of CNF formulas.

    Contact: E. Welzl, D. Scheder, P. Traxler, P. Zumstein

  • A Fresh Look at the Complexity of Pivoting in Linear Complementarity

    (Financed by the Swiss National Science Foundation.) We propose to study both linear and convex quadratic programming in a more general setting: by examining the linear complementarity problem with sufficient matrices. Besides providing a unifying framework for the two problems, linear complementarity also has many direct applications, e.g. in control theory, finance, algorithmic game theory.
    The tools we will use in our research can generally be described as combinatorial abstract models of optimisation problems. We concentrate on two of them: oriented matroids and unique-sink orientations.
    Several algorithms have been suggested by previous research in this area. For most of them there are both positive and negative results: they are known to be polynomial on some subclasses of the problems, but super-polynomial on other, larger classes. For many classes, however, such analysis is missing (among them are the two we consider the most important, that is, LCP with P-matrices and with sufficient matrices). At present randomised algorithms appear promising, and hence we plan to concentrate on their analysis.
    We plan to attack the problem from two sides. We aim to find new classes of problems for which some algorithm runs in polynomial (or expected polynomial) time; and we will search for new examples of abstract optimisation problems for which known algorithms are slow. This will in turn reduce the gap between positive and negative results for these algorithms. We believe that this approach will eventually lead to a strongly polynomial algorithm for the linear complementarity problem with sufficient matrices.

    Contact: K. Fukuda, ETHZ and EPFL, Jan Foniok, ETHZ


Publications

  • Books

  • Journals (with refereeing)

    R. Aharoni, T. Szabó, Vizing's theorem for chordal graphs, Discrete Mathematics (2009), to appear.

    N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, P. Zumstein, Polychromatic Coloring of Plane Graphs, Discrete and Computational Geometry (2009), to appear.

    R. Berke, D. Mitsche, Colorings at Minimum Cost, Discrete Mathematics (2009), to appear.

    R. Berke, T. Szabo, Deciding Relaxed Two-Colorability - A Hardness Jump, Combinatorics, Probability and Computing (2009), to appear.

    K. Buchin, A. Razen, T. Uno, U. Wagner, Transforming Spanning Trees: A Lower Bound, Computational Geometry - Theory and Applications 42:8 (2009), 724 - 730.

    T. Christ, M. Hoffmann, Y. Okamoto, T. Uno, Improved Bounds for Wireless Localization, Algorithmica (2009), to appear.

    J. Foniok, K. Fukuda, B. Gärtner, H. J. Lüthi, Pivoting in Linear Complementarity: Two Polynomial-Time Cases, Discrete and Computational Geometry42:2 (2009), 187-205

    K. Fukuda, S. Moriyama, H. Nakayama and J. Richter-Gebert, Every non-euclidean oriented matroid admits a biquadratic final polynomial, Combinatorica (2009), to appear.

    K. Fukuda, S. Moriyama, Y. Okamoto, The Holt-Klee condition for oriented matroids, European J. Combinatorics (2009), to appear.

    K. Fukuda, C. Weibel, A linear equation for minkowski sums of polytopes relatively in general position, European J. Combinatorics (2009), to appear.

    S. Gandhi, S. Suri, E. Welzl, Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks, ACM Transactions on Sensor Networks (2009), to appear.

    H. Gebauer, Y. Okamoto, Fast exponential-time algorithms for the forest counting and the Tutte polynomial computation in graph classes, International Journal of Foundations of Computer Science 20 (2009), 25-44.

    H. Gebauer, T.Szabo, Asymptotic random graph intuition for the biased connectivity game, Random Structures & Algorithms (2009), to appear.

    D. Hefetz, M. Krivelevich, M. Stojakovíc, T. Szabó, A sharp threshold for the Hamilton cycle Maker-Breaker game, Random Structures and Algorithms, 34 (2009), 112-122.

    D. Hefetz, M. Krivelevich, M. Stojakovíc, T. Szabó, Avoider-Enforcer: the rules of the game, Journal of Combinatorial Theory (Series A) (2009), to appear.

    D. Hefetz, M. Krivelevich, T. Szabó, Hamilton cycles in highly connected and expanding graphs, Combinatorica (2009), to appear.

    M. Hoffmann, B. Speckmann, Cs.D. Tóth, Pointed binary encompassing trees: simple and optimal, Computational Geometry - Theory and Applications 43/1 (2009), 35-41.

    J. Matoušek, Removing degeneracy in LP-type problems revisited, Discrete and Computational Geometry, (2009), to appear.

    E. Nevo, U. Wagner, On the Embeddability of Skeleta of Spheres, Israel Journal of Mathematics (2009), to appear.

  • Conference Proceedings (with selection process)

    O. Aichholzer, T. Hackl, M. Hoffmann, A. Pilz, G. Rote, B. Speckmann, B. Vogtenhuber, Plane Graphs with Parity Constraints, Proc. 10th Algorithms and Data Structures Symposium (WADS) (2009), 13-24.

    M. Al-Jubeh, M. Hoffmann, M. Ishaque, D. Souvaine, Cs. Tóth, Convex Partitions with 2-Edge Connected Dual Graphs, Proc. 15th Ann. Internat. Conf. Computing and Combinatorics (COCOON) (2009), 192-204.

    S. Columbano, K. Fukuda, C. Jones, An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices, In D. Avis, D. Bremner, and A. Deza, editors, Polyhedral Computation, CRM-AMS proceedings, AMS (2009), to appear.

    T. Galkovskyi, B. Gärtner, B. Rublev, The Domination Heuristic for LP-type Problems, Proc. 10th Workshop on Algorithm Engineering and Experiments (ALENEX) (2009), 74-84.

    H. Gebauer, Disproof of the Neighborhood Conjecture and its Implications to SAT, Proc. 17th Annual European Symposium on Algorithms (ESA) (2009), 764-775.

    A. Francke, M. Hoffmann, Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard, Proc. 25th Annual Symposium on Computational Geometry (SoCG) (2009), 179-188.

    B. Gärtner, M. Jaggi, Coresets for Polytope Distance, Proc. 25th Annual Symposium on Computational Geometry (SoCG) (2009), 33-42.

    O. Goussevskaia, M. Halldorsson, R. Wattenhofer, and E. Welzl, Capacity of Arbitrary Wireless Networks, Proc. 28th Annual IEEE Conference on Computer Communications (INFOCOM) (2009), to appear.

    J. Matoušek, M. Tancer, and U. Wagner, Hardness of Embedding Simplicial Complexes, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2009), 855-864.

    R. Moser, A Constructive Proof of the Lovász Local Lemma, Proc. 41st Annual ACM Symposium on Theory of Computing (STOC) (2009), 343-350.

    P. Traxler, Variable Influences in Conjunctive Normal Forms, Proc. 11th International Conference on Theory and Applications of Satisfiability Testing (SAT) (2009), 101-113.

  • Other (including submitted work)

    Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Proc. 21st Canadian Conference on Computational Geometry (CCCG) (2009), 9-12.

    T. Christ, M. Hoffmann, Wireless Localization with Vertex Guards is NP-hard, Proc. 21st Canadian Conference on Computational Geometry (CCCG) (2009), 149-152.

    T. Christ, M. Hoffmann, Y. Okamoto, Natural Wireless Localization is NP-hard, Abstracts 25th European Workshop on Computational Geometry (EuroCG) (2009), 175-178.

    H. Gebauer, R. A. Moser, D. Scheder, E. Welzl, The Lovász Local Lemma and Satisfiability, Efficient Algorithms - Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday , (2009) LNCS 5760, 30-54.

    J. Giesen, M. Jaggi, S. Laue Approximate Regularization Paths for Support Vector Machines, (2009), submitted.

    D. Hefetz, M. Krivelevich, M. Stojakovíc, T. Szabó, Fast winning strategies in Avoider-Enforcer games, submitted.

    J. Matoušek: Blocking visibility for points in general position (2009), submitted.

    R. Moser, G.Tardos, A Constructive Proof of the General Lovász Local Lemma, (2009), submitted.

    H. Nakayamka, S. Moriyama, K. Fukuda, Realizations of oriented matroids by polynomial optimization, (2009), submitted.

    H. Nakayamka, S. Moriyama, K. Fukuda, Three characteristic rank-4 oriented matroids, (2009), submitted.

    A. Razen, E. Welzl, Counting Crossing-Free Geometric Graphs with Exponential Speed-Up, (2009), submitted.

    A. Razen, E. Welzl, On the Number of Crossing-Free Partitions in the Plane, Abstracts 25th European Workshop on Computational Geometry (EuroCG) (2009), 147-150.

    T. Szabó, P. Zumstein, S Zürcher, On the Minimum Degree of Minimal Ramsey Graphs (2009), submitted.


Lectures

Y. BRISE
"Clarkson's Algorithm for Violator Spaces", 21st Canadian Conference on Computational Geometry (CCCG 2009), UBC, Vancouver, Canada (Aug 17, 2009).

T. CHRIST
"On the Wireless Localization Problem", 25th European Workshop on Computational Geometry (EuroCG 2009), ULB Brussels, Belgium (Mar 17, 2009).
"Wireless Localization with Vertex Guards is NP-hard", 21st Canadian Conference on Computational Geometry (CCCG 2009), UBC, Vancouver, Canada (Aug 19, 2009).
"The Wireless Localization Problem", Laboratoire d'Informatique Théorique et Quantique, University of Montreal, Canada (Aug 26, 2009).

A. FRANCKE
"The Euclidean Degree-4 Minimum Spanning Tree Problem is NP-hard", 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Åarhus, Denmark (Jun 9, 2009).

B. GÄRTNER
"K-matrix linear complementarity problems and unique sink orientations", Otto-von-Guericke-Universität Magdeburg, Germany (May 4, 2009).

H. GEBAUER
"The Lovász Local Lemma is tight for SAT", 14th International Conference on Random Structures and Algorithms (RSA 2009), Poznań, Poland (Aug 4, 2009).
"Disproof of the Neighborhood Conjecture with Implications to SAT", 17th Annual European Symposium on Algorithms (ESA 2009), Copenhagen, Denmark (Sept 9, 2009).

M. HOFFMANN
"Bounded Degree Euclidean Minimum Spanning Trees", Computational Geometry Seminar, Tel Aviv University, Israel (Mar 25, 2009).
"Happy Points - Plane Graphs with Parity Constraints", 11th Algorithms and Data Structures Symposium (WADS 2009), Banff Conference Centre, Banff, Alberta, Canada (Aug 22, 2009).

M. JAGGI
"Coresets for Polytope Distance", 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Åarhus, Denmark (Jun 8, 2009).

R. MOSER
"A Constructive Proof of the Lovász Local Lemma", Combinatorial Geometry and Optimization Seminar, EPF Lausanne (Feb 12, 2009).
"A Constructive Proof of the Lovász Local Lemma", Combinatorics and Probability, MFO, Oberwolfach (April 29, 2009).
"A Constructive Proof of the Lovász Local Lemma", CS Theory Seminar, Simon Fraser University, Vancouver BC, Canada (May 21, 2009).
"A Constructive Proof of the Lovász Local Lemma", CanaDAM, Centre de recherches mathématiques, Montréal, Canada (May 26, 2009).
"A Constructive Proof of the Lovász Local Lemma", Symposium on Theory of Computing (STOC) 09, Washington DC, USA (Jun 1, 2009).

A. RAZEN
"On the Number of Crossing-Free Partitions in the Plane", 25th European Workshop on Computational Geometry (EuroCG 2009), ULB Brussels, Belgium (Mar 17, 2009).

D. SCHEDER
"Deterministic Local Search for the k-SAT Problem: An Algorithm and some Improvements", 23rd European Conference on Operational Research (EURO 2009), Bonn (July 7, 2009).

P. TRAXLER
"Variable Influences in Conjunctive Normal Forms", 11th International Conference on Theory and Applications of Satisfiability Testing (SAT 2009), Swansea, Wales (Jun 30, 2009).

U. WAGNER
"Hardness of Embedding Simplicial Complexes in R^d", Discrete Geometry and Combinatorics Seminar, Cornell University, Ithaca, NY, USA (Mar 23, 2009).
"Complexity of Embedding Simplicial Complexes in R^d", Discrete Mathematics and Optimization Seminar, McGill University, Montreal, Canada (Mar 30, 2009).
"Complexity of Embedding Simplicial Complexes in R^d", Combinatorics Seminar, University of Minnesota, Minneapolis, MN, USA (April 7, 2009).

E. WELZL
"Triangulations of Convex Polygons - A Historical Note", Seminar on Computational Geometry, Leibniz-Center for Computer Science, Schloss Dagstuhl, Germany (Mar 12, 2009).
"Counting Crossing-free Configurations", Discrete Mathematics and Optimization Seminar, McGill University, Montreal, Canada (Apr 14, 2009).
"Satisfiability of Boolean Formulas - Combinatorics and Algorithms", Seminar of the School of Computer and Communication Sciences, Ecole Polytechnique Fédérale de Lausanne, Switzerland (Mar 11, 2009).
"Satisfiability - Combinatorics and Algorithms", Symposium Information Processing - Modern Perspectives (in honour of the 75th birthday of the Academician Arto Salomaa), Turku, Finland (May 25, 2009).
"Randomization in Computational Geometry", SoCG 25th Anniversary Celebration, at 25th Annual ACM Symp. on Computational Geometry, Aarhus, Danmark (Jun 7, 2009; invited talk).
"On the Number of Crossing Free Configurations of Planar Point Sets", Algorithmic and Combinatorial Geometry, Alfréd Rényi Institute of Mathematics, Budapest, Hungary (Jun 16, 2009).
"Erfüllbarkeit logischer Formeln - Kombinatorik und Algorithmen", Mathematisch-naturwissenschaftliche Klasse, Berlin-Brandenburgische Akademie der Wissenschaften, Berlin, Germany (Jun 26, 2009).
"The Lovász Local Lemma and Satisfiability", Colloquium in honor of Kurt Mehlhorn's 60th Birthday, Saarbrücken, Germany (Aug 28, 2009).


Courses and Seminars

Fall 09

See also the Course Catalogue

Spring 09

See also the Course Catalogue and our table summary ordered by your course of studies

Fall 08

See also the Course Catalogue

Organization of Workshops etc.


Dissertations


Master and Diploma Theses

  • Andrea Francke, Quasioptima for Linear Programs,
    Advisors: Bernd Gärtner, Uli Wagner / to be completed
  • Andrei Giurgiu, Random Walk Algorithms for SAT,
    Advisor: Robin Moser / to be completed
  • Urs Holzer, Relations between the exponential time complexity of NP-complete problems,
    Advisor: Dominik Scheder / to be completed
  • Dave Meyer, Geometric Algorithms for Support Vector Machines,
    Advisor: Martin Jaggi / 13.8.2009
  • Sabrina Wiedersheim, Spiders and Snowflakes,
    Advisor: Michael Hoffmann / 13.3.2009

Bachelor and Semester Theses / Internship Projects

  • Timon Hertli, A Simple Algorithm for 3-SAT,
    Advisor: Dominik Scheder / to be completed
  • Stefan Kraft, The History of Mersenne's Conjecture,
    Advisor: B. Gärtner / 15.9.2009
  • Zygmunt Malecki, Fairy Chess Endgames
    Advisors: B. Gärtner / 23.6.2009

Miscellaneous

Y. BRISE
Teach. Assistance Inormatik II (D-BAUG) (Spring 09)
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 09).
Webmaster www-gremo.

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

K. FUKUDA
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.
Editor-in-Chief of CGAL.

H. GEBAUER
Teach. Assistance Coordinator
Teach. Assistance Graphs and Algorithms (Fall 09)

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

M. JAGGI
Teach. Assistance Inormatik II (D-BAUG) (Spring 09)
Teach. Assistance Algorithms, Probability, and Computing (Fall 09)

A. RAZEN
Coordinator Mittagsseminar.
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 09)

D. SCHEDER
Teach. Assistance Algorithms, Probability, and Computing (Fall 09)
Teach. Assistance Satisfiability of Boolean Formulas (Fall 09)

M. SULOVSKÝ
Teach. Assistance Algorithms Lab (Fall 09)

P. TRAXLER
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 09).

U. WAGNER
Program committee member of

  • 7th Annual European Symposium on Algorithms (ESA 2009), Design and analysis track, Copenhagen, Denmark (7-9 Sep, 2009)

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

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.


19-Jan-2009 / ybrise@inf.ethz.ch