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

CGAL Geometric Algorithms Library
  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


Guests


Grants

  • Linear Time Kernel Methods and Matrix Factorizations

    (Financed by Google Research Awards) The goal of this research is to study fast approximation algorithms for kernel methods on the one hand, and for approximate matrix factorizations and semi-definite programs on the other hand. Building on the coreset paradigm, we try to contribute to the understanding of sparsity and algorithmic performance on large scale problems of this form, and will also consider several practical applications from machine learning.

    Contact: B. Gärtner, M. Jaggi

  • 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: B. Gärtner, M. Jaggi

  • 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, J. Foniok, ETHZ


Publications

  • Books

  • Journals (with refereeing)

    R. Berke, D. Mitsche, Colorings at Minimum Cost, Discrete Mathematics 310:3 (2010), 561-569.

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

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

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

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

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

    R. Moser, G.Tardos, A Constructive Proof of the General Lovász Local Lemma, Journal of the ACM (2010), to appear.

  • Conference Proceedings (with selection process)

  • Other (including submitted work)

    Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Computational Geometry: Theory and Applications (2010), submitted.

    K. Buchin, J. Matoušek, R. Moser, D. Pálvölgyi, Vectors in a Box (2010), submitted.

    T. Christ, D. Pálvölgyi, M. Stojaković, Consistent digital line segments, Symposium of Computational Geometry (SoCG) (2010), submitted.

    J. Foniok, K. Fukuda, L. Klaus, Combinatorial Characterizations of K-matrices, (2010), submitted.

    B. Gärtner, J. Giesen, M. Jaggi, A combinatorial algorithm to compute regularized part-worth values in choice based conjoint analysis, (2010), submitted.

    J. Giesen, M. Jaggi, S. Laue, Approximating Parameterized Convex Optimization Problems, (2010), submitted.

    D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, Fast winning strategies in Avoider-Enforcer games, (2010), submitted.

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

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

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

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


Lectures

M. HOFFMANN
"Plane Graphs with Parity Constraints", Noon Seminar, TU Eindhoven, Netherlands (Jan 18, 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).


Courses and Seminars

Spring 10

See also the Course Catalogue.

Fall 09

See also the Course Catalogue

Spring 09

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


Organization of Workshops etc.


Dissertations


Master and Diploma Theses

  • Stefan Kraft, The Structure of Minimal Unsatisfiable CNF Formulas,
    Advisor: Heidi Gebauer, Dominik Scheder / to be completed

Bachelor and Semester Theses / Internship Projects

  • Timon Hertli, A Simple Algorithm for 3-SAT,
    Advisor: Dominik Scheder / to be completed
  • Urs Holzer, Relations between the exponential time complexity of NP-complete problems,
    Advisor: Dominik Scheder / to be completed

Miscellaneous

Y. BRISE
Webmaster www-gremo.
Teach. Assistance Informatik I (D-MAVT) (Spring 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.
Program committee member of

H. GEBAUER
Teach. Assistance Coordinator

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

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

M. SULOVSKÝ
Contact Assistant Graph Drawing (D-INFK) (Spring 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

  • Professor of Orthopedic Technologies in Aging, Department of Mechanical and Process Engineering, ETH Zurich (chair)

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

Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
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.


18-Jan-2010 / ybrise@inf.ethz.ch