Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
| Institut für Theoretische Informatik | ||
| Departement Informatik | ||
| ETH Zürich | phone | +41-44-632 73 92 |
| CH-8092 Zürich | fax | +41-44-632 10 63 |
| Quick Links: | Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Bachelor Theses, Miscellaneous |
(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
(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
(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
(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
(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
(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.
R. Aharoni, T. Szabó, Vizing's conjecture for chordal graphs, Discrete Mathematics 300 (2009), 1766-1768.
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 42:3 (2009), 421-442.
R. Berke, T. Szabo, Deciding Relaxed Two-Colorability - A Hardness Jump, Combinatorics, Probability and Computing (2009), 18:1-2, 53-81.
K. Buchin, A. Razen, T. Uno, U. Wagner, Transforming Spanning Trees: A Lower Bound, Computational Geometry - Theory and Applications 42:8 (2009), 724 - 730.
J. Foniok, K. Fukuda, B. Gärtner, H. J. Lüthi, Pivoting in Linear Complementarity: Two Polynomial-Time Cases, Discrete and Computational Geometry 42: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 29:6 (2009), 691-698.
K. Fukuda, S. Moriyama, Y. Okamoto, The Holt-Klee condition for oriented matroids, European J. Combinatorics 30:8 (2009), 1854-1867.
S. Gandhi, S. Suri, E. Welzl, Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks, ACM Transactions on Sensor Networks 6:1 (2009), Article No.: 1.
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, 35 (2009), 431-443.
D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, Fast winning strategies in Avoider-Enforcer games, Graphs and Combinatorics, 25 (2009), 533-544.
D. Hefetz, M. Krivelevich, T. Szabó, Hamilton cycles in highly connected and expanding graphs, Combinatorica 29 (2009), 547-568.
D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, Avoider-Enforcer: the rules of the game, Journal of Combinatorial Theory (Series A) 117 (2009), 152-163.
D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, A sharp threshold for the Hamilton cycle Maker-Breaker game, Random Structures and Algorithms, 34 (2009), 112-122.
J. Matoušek, Blocking visibility for points in general position, Discrete and Computational Geometry, 42:2 (2009), 19-22.
J. Matoušek, Removing degeneracy in LP-type problems revisited, Discrete and Computational Geometry, 42:4 (2009), 517-526.
E. Nevo, U. Wagner, On the embeddability of skeleta of spheres, Israel Journal of Mathematics 174 (2009), 381-402.
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), LNCS 5664, 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), LNCS 5609, 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 Proceedings and Lecture Notes, Amer. Math. Soc., Vol. 48 (2009), 73-102.
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 with Implications to SAT, Proc. 17th Annual European Symposium on Algorithms (ESA) (2009), LNCS 5757, 764-775.
O. Goussevskaia, R. Wattenhofer, M. M. Halldórsson, E. Welzl, Capacity of Arbitrary Wireless Networks, Proc. 28th IEEE International Conference on Computer Communications (Infocom) (2009), 1872-1880.
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.
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), LNCS 5584, 101-113.
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.
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.
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).
"Einfache und schwierige Informatikprobleme",
Schnupperstudium Informatik, Zurich (Sep 1, 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 für Polytop-Distanz",
Computational Geometry II Lecture, FSU
Jena, Germany (May 5, 2009).
"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, Germany (Jul 7, 2009).
"Deterministic Local Search for 3-SAT",
Mittagsseminar in Discrete Mathematics, FU Berlin, Germany (Oct 26, 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).
"Combinatorial and Computational Aspects of Embeddability",
Combinatorics: Methods & Applications - Combinatorial Geometry Workshop,
Institute for Pure & Applied Mathematics (IPAM), University of California, Los Angeles
(October 20, 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).
"The Lovász Local Lemma and Satisfiability",
Memorial Colloquium in honor of Ingo Wegener,
Dortmund, Germany (Nov 27, 2009).
P. ZUMSTEIN
"Polychromatic Colorings of Plane Graphs",
Mittagssminar in Discrete Mathematics, FU Berlin, Germany (Nov 9, 2009).
"On the minimum degree of Ramsey-minimal graphs",
6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary (May 16, 2009).
Y. BRISE
Teach. Assistance Informatik II (D-BAUG) (Spring 09).
Contact Assistant Informatik (D-MATH, D-PHYS) (Fall 09).
Webmaster www-gremo.
T. CHRIST
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 09).
Contact Assistant Computational Geometry (Fall 09).
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.
Teach. Assistance Datenstrukturen und Algorithmen (Spring 09).
Contact Assistant Graphs and Algorithms (Fall 09).
Best Student Paper Award
at the Annual European Symposium on Algorithms 2009 (ESA '09) for her paper
"Disproof of the Neighborhood Conjecture with Implications to SAT".
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Contact Assistant Algorithms Lab (Fall 09).
M. JAGGI
Teach. Assistance Informatik II (D-BAUG) (Spring 09).
Teach. Assistance Algorithms, Probability, and Computing (Fall 09).
R. MOSER
Best Paper and Best Student Paper Award
at the 41st ACM Symposium on Theory of Computing 2009 (STOC '09)
for his paper "A Constructive Proof of the Lovász Local Lemma".
Internship with Microsoft Research, Redmond, WA, USA, (Sep 14 - Dec 4, 2009).
A. RAZEN
Coordinator Mittagsseminar (until Sep 30).
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 09).
D. SCHEDER
Contact Assistant Algorithms, Probability, and Computing (Fall 09).
Contact Assistant Satisfiability of Boolean Formulas (Fall 09).
M. SULOVSKÝ
Coordinator Mittagsseminar (since Oct 1).
Contact Assistant Approximation Algorithms and Semidefinite Programming (Spring 09).
Contact Assistant Algorithms Lab (Fall 09).
P. TRAXLER
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 09).
U. WAGNER
Program committee member of
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
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.
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.
Mitglied der Unterrichtskommission des Departements Informatik der ETH Zürich.
P. ZUMSTEIN
Teach. Assistance Datenstrukturen und Algorithmen (Spring 09).
