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 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.
K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama (Eds.), Mathematical Software - ICMS 2010, LNCS6327, Springer-Verlag (2010).
R. Berke, D. Mitsche, Colorings at Minimum Cost, Discrete Mathematics 310:3 (2010), 561-569.
T. Christ, M. Hoffmann, Y. Okamoto, T. Uno, Improved Bounds for Wireless Localization, Algorithmica 57:3 (2010), 499-516.
K. Fukuda, C. Weibel, A linear equation for minkowski sums of polytopes relatively in general position, European J. Combinatorics 31 (2010), 565-573.
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 2 (2010) Art. 11, 15pp.
T. Szabó, P. Zumstein, S Zürcher, On the Minimum Degree of Minimal Ramsey Graphs, Journal of Graph Theory 64:2 (2010), 150-164.
T. Christ, D. Pálvölgyi, M. Stojaković, Consistent digital line segments, Symposium of Computational Geometry (SoCG) (2010), 11-18.
J. Giesen, M. Jaggi, S. Laue, Approximating Parameterized Convex Optimization Problems, Proc. 8th Annual European Symposium on Algorithms (ESA), (2010), LNCS 6346, 524-535.
M. Hoffmann, J. Matoušek, Y. Okamoto, P. Zumstein, Minimum and Maximum Against k Lies, Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) (2010), LNCS 6139, 139-149.
M. Jaggi, M. Sulovský, A Simple Algorithm for Nuclear Norm Regularized Problems, Proc. 27th International Conference on Machine Learning (ICML) (2010), 471-478.
A. Kawamura, J. Matoušek, T. Tokuyama, Zone diagrams in Euclidean spaces and in other normed spaces, Proc. 26th ACM Symposium Comput. Geom. (SoCG) (2010), 216-221.
M. Sharir, A. Sheffer, E. Welzl, On Degrees in Random Triangulations of Point Sets, Proc. 26th Annual Symposium on Computational Geometry (SoCG) (2010), 297-306.
A. Gundert, E. D. Kim, D. Schymura, Lattice Paths and Lagrangian Matroids, DocCourse Combinatorics and Geometry 2009, Part III: Research Reports, CRM Documents Vol. 5 (2010), 63-82.
H. Miyata, S. Moriyama, and K. Fukuda, Complete enumeration of small realizable oriented matroids, Proceedings of Canadian Conference on Computational Geometry (CCCG) (2010), 143-146.
M. Sulovský, U. Wagner, k-Sets and Continuous Motion in R3, Proceedings of Canadian Conference on Computational Geometry (CCCG) (2010), 47-50.
Y. BRISE
"Sparse Quadratic Programming Solver",
CGAL Developer Meeting, Sophia-Antipolis, France (Jun 2, 2010).
T. CHRIST
"Consistent digital line segments",
26th SoCG, Snowbird, Utah, USA (Jun 14, 2010).
K. FUKUDA
"On the complexity of Minkowski sums of polytopes",
plenary talk, Workshop on Combinatorial Geometry and Algorithms,
Tokyo Institute of Technology, Japan (Sep 21 2010).
"Recent advances in oriented matroids: Interplay between linearity and combinatorics",
invited talk, Bernoulli Conference on Discrete and Computational Geometry,
EPF Lausanne (Aug 30 - Sep 3 2010).
B. GÄRTNER
"Abstract Optimization - The German and the Swiss Approach",
Informatik-Kolloquium, Universität Paderborn, Germany (Jun 22, 2010).
"Geometric Unique Sink Orientations", Conference on Geometric Graph Theory,
EPF Lausanne, Switzerland (Sep 30, 2010).
H. GEBAUER
"Game Theoretic Ramsey Numbers",
Mittagsseminar Diskrete Mathemtik, FU Berlin, Germany (Feb 23, 2010).
"Game Theoretic Ramsey Numbers",
Workshop on Extremal and Probabilistic Combinatorics,
Frauenchiemsee, Germany (Aug 25, 2010).
A. GUNDERT
"Introduction to Random Graphs",
Arbeitsgemeinschaft on Topological Robotics,
Math. Forschungsinstitut Oberwolfach, Germany (Oct 10, 2010).
M. HOFFMANN
"Plane Graphs with Parity Constraints",
Noon Seminar, TU Eindhoven, Netherlands (Jan 18, 2010).
"Minimum and Maximum Against k Lies",
12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT),
Bergen, Norway (Jun 22, 2010).
R. MOSER
"Schöning's Walk-SAT Algorithm - Progress and Barriers",
Random Graals 2010, The 5th Bertinoro Workshop on Randomized
Algorithms and Graphs,
Bertinoro (Forlì-Cesena), Italy (Jun 2, 2010).
"A Constructive Proof of The Lovász Local Lemma",
The 24th European Conference on Operational Research (EURO XXIV),
Lisbon, Portugal
(Jul 13, 2010).
"A Constructive Proof of The Lovász Local Lemma",
China Theory Week (CTW),
Institute for Theoretical Computer Science,
Tsinghua University,
Beijing, China (Sep 12, 2010).
D. SCHEDER
"Unsatisfiable Linear CNF Formulas Are Large and Complex",
27th International Symposium on Theoretical Aspects of Computer Science (STACS '10),
Nancy, France (Mar 4, 2010).
"Using a Skewed Hamming Distance to Speed Up Deterministic Local Search",
Mitarbeiterseminar Logik in der Informatik, Humboldt-Universität Berlin
(Apr 6, 2010).
"Using a Skewed Hamming Distance to Speed Up Deterministic Local Search",
DMI, University of Novi Sad, Novi Sad, Serbia (Jun 9, 2010).
"A Full Derandomization of Schoening's k-SAT Algorithm",
Seminar Talk, Max-Planck-Institut Saarbrücken, Germany (Oct 5, 2010).
M. SULOVSKÝ
"k-sets and continuous motion in R3", CCCG 2010, Winnipeg, Canada, (Aug 9, 2010).
"Crossing identities of k-edges and k-facets",
Discrete and Computational Geometry Seminar,
Ben-Gurion University of Negev, Be'er Sheva, Israel
(Oct 26, 2010).
"k-facet crossing identities",
Combinatorics Seminar, Technion and University of Haifa (joint seminar), Haifa, Israel (Nov 3, 2010).
"Conflict-free coloring geometric hypergraphs revisited",
Culminating Workshop of the Semester on Discrete Geometry, EPF Lausanne,
(Dec 2, 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).
"Minors in Hypergraphs and Embeddability",
Conference on Geometric Graph Theory, EPF Lausanne
(Oct 1, 2010).
"Expansion and Minors in Hypergraphs",
Culminating Workshop of the Semester on Discrete Geometry,
EPF Lausanne, (Nov 30, 2010).
"On Gromov's method of selecting heavily covered points",
Combinatorics Seminar, The Hebrew University
of Jerusalem, Israel (Dec 28, 2010).
E. WELZL
"When Conflicting Constraints Can be Resolved - the Local Lemma and Satisfiability",
Rejewski-Rózycki-Zygalski Lecture in Computer Science,
Adam Mickiewicz University,
Poznan, Poland (May 28, 2010).
"When Conflicting Constraints Can be Resolved - the Local Lemma and Satisfiability",
Festkolloqium zu Ehren von Sabine Koppelberg, Martin Aigner, Ralph-Hardo Schulz, und Elmar Vogt,
Berlin Free University, Berlin, Germany (Jul 10, 2010).
Y. BRISE
Webmaster www-gremo.
Teach. Assistance Informatik I (D-MAVT) (Spring 10).
Contact Assitant Informatik (D-MATH, D-PHYS) (Fall 10).
T. CHRIST
Contact Assistant Computational Geometry (D-INFK) (Fall 10).
A. FRANCKE
Recipient of the Google Anita Borg Scholarship EMEA 2010
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 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 (until April 30).
Program committee member of
H. GEBAUER
Teach. Assistance Coordinator.
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 10).
Contact Assitant Graphs and Algorithms: Advanced Topics (D-INFK) (Fall 10).
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 10).
A. GUNDERT
Contact Assistant Graphs and Algorithms (D-INFK) (Spring 10).
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
M. JAGGI
Software Engineer Internship at Google Zurich (Feb - June 2010).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 10).
R. MOSER
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 10).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 10).
G. NIVASCH
Contact Assistant Metric Embeddings (D-INFK) (Spring 10).
D. SCHEDER
Contact Assistant Satisfiability of Boolean Formulas (D-INFK) (Fall 10).
M. SULOVSKÝ
Coordinator Mittagsseminar.
Contact Assistant Graph Drawing (D-INFK) (Spring 10).
Contact Assistant Algorithms Lab (D-INFK) (Fall 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
Coreferee for dissertations of
Chair of the EATCS Award committee (with Eugenio Moggi and Pavlos Spirakis).
Member of the 2010 Rolf Nevanlinna Prize committee (with Ravindran Kannan (chair), Stanley Osher, Olivier Pironneau, Madhu Sudan).
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.