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, Software |
(Financed by the Swiss National Science Foundation). We use the term simultaneous (geometric) embedding to refer to any kind of problem in which two or more graphs are to be embedded simultaneously, usually subject to certain constraints. One reason for the strong interest in simultaneous embeddings lies in a wealth of applications in areas such as bio-informatics, network analysis, and software engineering. For instance, in order to compare two phylogenetic trees one would like to have a "nice" simultaneous drawing of two trees sharing the same set of leaves, so-called tanglegrams. More generally, simultaneous embeddings come into play whenever large or dynamically changing graphs are to be visualized. Given a large graph, only part of it can be shown at a time with a sufficient level of detail. When browsing from one such part to a neighboring one, it is desirable to have a certain overlap that is common to both parts and drawn the same way for both parts. In this way, the user can maintain her mental map and more easily keep track of her current location in the graph. In the context of dynamic graphs, a simultaneous drawing for several instances of the graph at different timesteps allows to visually examine the differences in order to, for instance, draw conclusions regarding the capacity utilization of a network. Beyond these motivating applications the study of simultaneous embeddings revealed a rich collection of interesting and challenging combinatorial and algorithmic problems, many of which are still far from being solved. The goal of this project is, on one hand, to gain more insights into some of these problems and, on the other hand, to develop new models in order to address some shortcomings of the existing settings studied so far. The project will be carried out as an international collaboration within the collaborative research project "GraDr: Graph Drawings and Representations", which comprises altogether 12 partners from seven European countries.
Contact: M. Hoffmann, V. Kusters
(Financed by European Commission) High dimensional geometric data are ubiquitous in science and engineering, and thus processing and analyzing them is a core task in these disciplines. The Computational Geometric Learning project (CG Learning) aims at extending the success story of geometric algorithms with guarantees, as achieved in the CGAL library and the related EU funded research projects, to spaces of high dimensions. This is not a straightforward task. For many problems, no efficient algorithms exist that compute the exact solution in high dimensions. This behavior is commonly called the curse of dimensionality. We plan to address the curse of dimensionality by focusing on inherent structure in the data like sparsity or low intrinsic dimension, and by resorting to fast approximation algorithms. The following two kinds of approximation guarantee are particularly desirable: first, the solution approximates an objective better if more time and memory resources are employed (algorithmic guarantee), and second, the approximation gets better when the data become more dense and/or more accurate (learning theoretic guarantee). To lay the foundation of a new field---computational geometric learning---we will follow an approach integrating both theoretical and practical developments, the latter in the form of the construction of a high quality software library and application software.
Contact: B. Gärtner, C. Müller
(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.)
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.
Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Computational Geometry - Theory and Applications 44 (2011), 70-81.
J. Foniok, K. Fukuda, L. Klaus, Combinatorial Characterizations of K-matrices, Linear Algebra and its Applications 434 (2011), 68-80.
H. Gebauer, Enumerating all Hamilton Cycles and Bounding the Number of Hamilton Cycles in 3-Regular Graphs, The Electronic Journal of Combinatorics 18:1 (2011), #P132.
H. Gebauer, Finding and Enumerating Hamilton Cycles in 4-Regular Graphs, Theoretical Computer Science 412(35) (2011), 4579-4591.
M. Hoffmann, J. Matoušek, Y. Okamoto, P. Zumstein, The t-Pebbling Number is Eventually Linear in t, Electronic Journal of Combinatorics 18:1 (2011), #P153.
Jiří Matoušek, Martin Tancer, and Uli Wagner, Hardness of embedding simplicial complexes in Rd , Journal of the European Mathematical Society 13:2 (2011), 259–295.
M. Sharir, A. Sheffer, E. Welzl, On Degrees in Random Triangulations of Point Sets, Journal of Combinatorial Theory, Ser. A 118(7) (2011), 1979-1999.
P. Cheilaris, S. Smorodinsky, M. Sulovský, The potential to improve the choice: list conflict-free coloring for geometric hypergraphs, (2011), Proc. 27th ACM Symposium on Computational Geometry (SOCG), (2011), 424-432.
T. Christ, Beyond Triangulation: Covering Polygons with Triangles, Proc. 12th Algorithms and Data Structures Symposium (WADS) (2011), LNCS 6844, 231-242.
T. Christ, A. Francke, H. Gebauer, J. Matoušek, T. Uno, A Doubly Exponentially Crumbled Cake, Electronic Notes in Discrete Mathematics (38), (2011), 265-271.
H. Gebauer, T. Szabó, G. Tardos, The Local Lemma is Tight for SAT, Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011), 664-674.
T. Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General, Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2011), 277-284.
T. Hertli, R. Moser, D. Scheder, Improving PPSZ for 3-SAT using Critical Variables, Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS) (2011), 237-248.
M. Hoffmann, M. Sharir, A. Sheffer, Cs. D. Toth, E. Welzl, Counting Plane Graphs: Flippability and Its Applications, Proc. 12th Algorithms and Data Structures Symposium (WADS) (2011), LNCS 6844, 524-535.
R. Moser, D. Scheder, A Full Derandomization of Schöning's Algorithm, Proc. 43rd annual ACM symposium on Theory of computing (STOC) (2011), 245-252.
U. Wagner, Minors in Random and Expanding Hypergraphs, Proceedings of the 27th Annual Symposium on Computational Geometry (SOCG) (2011), 351-360.
T. Christ, M. Hoffmann, Wireless Localization within Orthogonal Polyhedra, Proc. 23rd Canadian Conference on Computational Geometry (CCCG) (2011), 467-472.
T. Christ, A. Mishra, Wireless Localization with Vertex Guards, Abstracts 27th European Workshop on Computational Geometry (EuroCG), Morschach, Switzerland (2011), 87-90.
H. Gebauer, A. Gundert, R. Moser, Y. Okamoto, Not All Saturated 3-Forests Are Tight (2011).
H. Nakayamka, S. Moriyama, K. Fukuda, Realizations of oriented matroids by polynomial optimization (2011).
H. Nakayamka, S. Moriyama, K. Fukuda, Three characteristic rank-4 oriented matroids (2011).
A. Razen, E. Welzl, Counting Crossing-Free Geometric Graphs with Exponential Speed-Up, Rainbow of Computer Science - Dedicated to Hermann Maurer on the Occasion of His 70th Birthday, Lecture Notes in Computer Science 6570 (2011), 36-46.
E. Welzl, The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?, Algorithms Unplugged (2011), 357-360.
Y. BRISE
"Sparse Quadratic Programming Solver",
CGAL Developer Meeting, Heraklion, Greece (Apr 13, 2011).
T. CHRIST
"Wireless Localization with Vertex Guards",
27th European Workshop on
Computational Geometry (EuroCG), Morschach, Switzerland (Mar 28,
2011).
"Wireless Localization within Orthogonal Polyhedra",
23rd Canadian Conference on Computational Geometry (CCCG 2011),
Fields Institute, Toronto, Canada (Aug 12, 2011).
"Beyond Triangulation: Covering Polygons with Triangles",
12th Algorithms and Data Structures Symposium (WADS 2011),
NYU Polytech, Brooklyn, New York, U.S.A. (Aug 15, 2011).
B. GÄRTNER
"Support Vector Machines Meet Goldfarb Cubes",
IPAM Workshop
Efficiency of the Simplex Method - Quo Vadis Hirsch Conjecture,
Institute for Pure And Applied Mathemtics, University of California in Los Angeles,
USA (Jan 19, 2011).
"Leben und Karriere - wer muss sich anpassen?"
Doktorandenkolloquium der Informatik Ruhr, Haus Nordhelle, Valbert, Germany (Oct 7, 2011)
H. GEBAUER
"The Local Lemma is Tight for SAT", 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, USA (Jan 24, 2011).
"Game Theoretic Ramsey Numbers", Pure mathematics seminar, Royal Holloway University of London, UK (Mar 1, 2011).
"Game Theoretic Ramsey Numbers", Combinatorics Study Group, Queen Mary University of London, UK (Mar 4, 2011).
"A Doubly Exponentially Crumbled Cake ", European Conference on Combinatorics, Graph Theory and Applications (EuroComb11), Rényi Institute, Budapest, Hungary (Aug 31, 2011).
"The Local Lemma is Tight For SAT", Combinatorial Geometry and Optimization Seminar, EPFL, Lausanne (Nov 3, 2011).
A. GUNDERT
"High-Dimensional 'Graph Theory'",
4th European Women in Mathematics Summer School, Lorentz Center, Leiden, The Netherlands (Jun 7, 2011).
"Expansion for 2-complexes", Noon Lecture, Department of Applied Mathematics (KAM), Charles University, Prague, Czech Republic (Oct 20, 2011).
T. HERTLI
"Improving PPSZ for 3-SAT using Crtitical Variables", 28th Symposium on Theoretical Aspects of Computer Science (STACS), TU Dortmund, Germany (Mar 10, 2011).
"3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General", China Theory Week (CTW), Department of Computer Science, Aarhus University, Denmark (Oct 10, 2011).
"3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General", 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs CA, USA (Oct 23, 2011).
M. HOFFMANN
"Counting Plane Graphs: Flippability and Its Applications",
12th Algorithms and Data Structures Symposium (WADS 2011),
NYU Polytech, Brooklyn, New York, U.S.A. (Aug 15, 2011).
"Counting Plane Graphs: Pseudo-Flippability and Applications",
Seminar of Algorithms Group, TU Eindhoven, The Netherlands (Oct 13, 2011).
R. MOSER
"A full derandomization of Schoening's k-SAT algorithm",
Combinatorics, Mathematisches Forschungsinstitut Oberwolfach, Germany (Jan 4, 2011).
"A full derandomization of Schoening's k-SAT algorithm",
Humboldt-Universität Berlin, Germany (Jan 14, 2011).
"A survey on exact algorithms for constraint satisfaction problems",
Computational Complexity of Discrete Problems, Schoss Dagstuhl, Wadern, Germany (Mar 25, 2011).
"A full derandomization of Schoening's k-SAT algorithm",
Computational Complexity of Discrete Problems, Schloss Dagstuhl, Wadern, Germany (Mar 25, 2011).
"A survey on exact algorithms for constraint satisfaction problems",
Universität Ulm, Germany (Jun 14, 2011).
"A Full Derandomization of Schöning's Algorithm",
43rd annual ACM symposium on Theory of computing (STOC), San Jose, California, USA (Jun 6, 2011).
D. SCHEDER
"A Full Derandomization of Schoening's k-SAT Algorithm",
Algorithms and Complexity Theory Seminar, Aarhus University, Denmark (Mar 2, 2011).
"A Full Derandomization of Schoening's k-SAT Algorithm",
Seminar of Algorithms Group, Warsaw University, Poland (Mar 31, 2011).
S. STICH
"Random derivative-free optimization of convex functions using a line search oracle",
5th workshop on Theory of Randomized Search Heuristics (ThRaSH 2011)
Copenhagen, Danmark (Jul 9, 2011).
"Gradient-free optimization with Random Pursuit",
CGLearning Review Meeting/Workshop Zürich, Switzerland (Dec 15, 2011).
U. WAGNER
"On Gromov's method of selecting heavily covered points",
Combinatorial Geometry Seminar, Tel-Aviv
University, Israel (Jan 2, 2011).
"Complete Minors of Hypergraphs: Random and Expanding Hypergraphs",
27th Annual Symposium on Computational Geometry,
Paris, France, (Jun 14, 2011).
"Isoperimetry, Crossing Numbers, and Multiplicities of (Equivariant) Maps",
Workshop on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach,
Germany, (Sep 7, 2011).
"Isoperimetric Inequalities in the Simplex and Multiplicities of Maps, after Gromov",
ERC Workshop High-Complexity Discrete Geometry, Freie Universität Berlin,
Germany, (Oct 25, 2011).
E. WELZL
"Zählen kreuzungsfreier Konfigurationen in der Ebene",
Fakultätskolloquium, Department of Mathematics,
Munich Technical University, Germany
(Jan 25, 2011).
"When Conflicting Constraints Can be Resolved -- the Lovász Local Lemma and Satisfiability",
Vienna ETH-day at
The Erwin Schrödinger International Institute for Mathematical Physics,
Vienna, Austria
(Mar 4, 2011).
"Kasteleyn and the Number of Crossing-Free Matchings and Cycles on a Planar Point Set",
Seminar on Computational Geometry,
Leibniz-Center for Informatics, Schloss Dagstuhl, Germany
(Mar 17, 2011).
"Counting Simple Polygonizations of Planar Point Sets",
23rd Canadian Conference on Computational Geometry (CCCG),
Toronto, Canada (Aug 12, 2011; plenary talk).
"Counting Simple Polygonizations of Planar Point Sets",
Seminar, Department of Computer Science,
Hong Kong University of Science and Technology, Hong Kong, China (Oct 28, 2011).
"Counting Simple Polygonizations of Planar Point Sets",
Friday Algorithms Seminar, University of Sydney,
Sydney, Australia (Nov 11, 2011).
Y. BRISE
Webmaster www-gremo (until Oct 25).
Teach. Assistance Informatik I (D-MAVT) (Spring 11).
Contact Assistant Informatik (D-MATH, D-PHYS) (Fall 11).
T. CHRIST
Teach. Assistance Computational Geometry (Fall 11).
A. FRANCKE
Fulbright Foreign Student Grant 2011/12.
Visiting Student Researcher at the University of Washington, Seattle WA, USA (Sept 2011 - Aug 2012).
K. FUKUDA
Editorial Board Member of
European J. Combinatorics, Computational Geometry: Theory and Applications,
Applied Mathematics Research eXpress.
B. GÄRTNER
Member of the CGAL Editorial Board.
Program committee member of
H. GEBAUER
Teach. Assistance Coordinator (until Nov 20).
Contact Assistant Graphs and Algorithms: Advanced Topics (D-INFK) (Fall 11).
A. GUNDERT
Teach. Assistanc Topological Methods in Combinatorics and Geometry (Spring 11).
T. HERTLI
Teach. Assistance Coordinator (since Nov 20).
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 11).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 11).
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Program committee chair of
M. JAGGI
Teach. Assistance Graph Drawing (Spring 11).
Teach. Assistance Informatik I (D-MATH) (Fall 11).
V. KUSTERS
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 11).
R. MOSER
Coordinator Mittagsseminar (since Jun 23).
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 11).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 11).
G. NIVASCH
Program committee member of
D. SCHEDER
Teach. Assistance Informatik (D-BIOL, D-PHARM) (Spring 11).
S. STICH
Webmaster www-gremo (since Oct 25).
Teach. Assistance Algorithms Lab (D-INFK) (Fall 11).
M. SULOVSKÝ
Coordinator Mittagsseminar (until Jun 22).
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
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.