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, Software |
(Financed by the Swiss National Science Foundation).
The goal of this project is to study higher dimensional analogues of graph
planarity (embeddings of simplicial complexes into Euclidean spaces) both
from an algorithmic and from a combinatorial point of view.
Embeddings of simplicical complexes into Euclidean spaces are a classical
topic in geometric topology (closely related to the classification of
embeddings up to ambient isotopy, the most famous special case of which is
classical know theory). The most basic case of the embeddability problem,
graph planarity, is also a fundamental topic in graph theory, discrete
geometry, and theoretical computer science and has been studied intensively
both from a structural and from an algorithmic point of view (including
close connections to the theory of graph minors and (linear time) algorithms
for planarity testing, to mention just two aspects most relevant to this
project). Equally important in discrete geometry is the study of the
quantitative failure of planarity, i.e., crossing numbers,
and relations to graph parameters such as edge expansion and bisection width.
In this project, we investigate higher-dimensional analogues of these notions
and problems. Typical questions include: For which dimensions k and d is
there an algorithm that decides if a given k-dimensional complex embeds
into d-dimensional Euclidean space? When is the problem computationally
intractable or even undecidable?
What is the maximum complexity (number of simplices, in terms of the
number of vertices, say) of
a simplicial complex that embeds into d-space? What are the connections
between the eigenvalues of the Laplacian of a simplicial complex and its
embeddability properties?
Contact: U. Wagner
(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
(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
(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.
B. Gärtner, J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer Verlag (2012).
P. Adamaszek, B. Gärtner, I. Meili, J. Müllener, J. Spühler, B. Zwahlen, Schau genau - schau wie schlau! Sprache und Technik Hand in Hand, Pro Juventute (2012).
H. Ahn, O. Cheong, J. Matoušek, A. Vigneron, Reachability by paths of bounded curvature in convex polygons, Computational Geometry: Theory and Applications 45:1-2 (2012), 21-32.
M. Bodlaender, C. Hurkens, V. Kusters, F. Staals, G. Woeginger, H Zantema, Cinderella versus the Wicked Stepmother, Theoretical Computer Science, Lecture Notes in Computer Science 7604 (2012), 57-71.
K. Buchin, J. Matoušek, R. Moser, and D. Pálvölgyi: Vectors in a box, Mathematical Programming Ser. A, 135:1-2 (2012), 323-335.
B. Bukh, G. Nivasch, Upper Bounds for Centerlines, Journal of Computational Geometry 3 (2012), 20-30.
T. Christ, D. Pálvölgyi, M. Stojaković, Consistent Digital Line Segments, Discrete and Computational Geometry 47:4 (2012), 691-710.
B. Gärtner, M. Jaggi, C. Maria, An Exponential Lower Bound on the Complexity of Regularization Paths, Journal of Computational Geometry 3:1 (2012), 168-195.
B. Gärtner, M. Sprecher, A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix Linear Complementarity Problem, Operations Research Letters 40:6 (2012), 484-486.
H. Gebauer, Disproof of the Neighborhood Conjecture with Implications to SAT, Combinatorica 32:5 (2012), 573-587.
H. Gebauer, On the Clique-Game, European Journal of Combinatorics 33:1 (2012), 8-19.
J. Giesen, M. Jaggi, S. Laue, Approximating Parameterized Convex Optimization Problems, ACM Transactions on Algorithms 9:1 (2012), #10.
M. Hoffmann, J. Matoušek, Y. Okamoto, P. Zumstein, Maximum and Minimum against k lies, Chicago Journal Theoretical Computer Science (2012), #2.
A. Kawamura, J. Matoušek, T. Tokuyama, Zone diagrams in Euclidean spaces and in other normed spaces, Mathematische Annalen 354:4 (2012), 1201-1221.
H. Kaplan, J. Matoušek, Z. Safernová, M. Sharir: Unit distances in three dimensions, Combinatorics, Probability and Computing, 21:4 (2012) 597-610.
H. Kaplan, J. Matoušek, M. Sharir: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, Discrete and Computational Geometry 48: 3(2012), 499-517.
J. Matoušek, M. Tancer, U. Wagner, A geometric proof of the colored Tverberg theorem, Discrete and Computational Geometry 47:2 (2012), 245-265.
U. Wagner, Minors, Embeddability, and Extremal Problems for Hypergraphs, Thirty Essays on Geometric Graph Theory, ed. J. Pach, (2012), 569-607.
P. K. Agarwal, J. Matoušek, M. Sharir, On range searching with semialgebraic sets II, Proc. IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS) (2012), 420-429.
A. Bärtschi, S. Suri, Conflict-free Chromatic Art Gallery Coverage, Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS) (2012), 160-171.
V. Cevher, H. Tyagi, Learning ridge functions with randomized sampling in high dimensions, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2012), 2025-2028.
V. Cevher, H. Tyagi, Active Learning of Multi-Index Function Models, Advances in Neural Information Processing Systems (NIPS) (2012), 1475--1483.
M. Čadek, M. Krčál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, Computing all maps into a sphere, Proc. 23nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2012), 1-10.
M. Eliáš, J. Matoušek, Higher-order Erdős-Szekeres theorems, Proc. 28th Annual Symposium on Computational Geometry (SoCG) (2012), 81-90.
F. Frati, J. Gudmundsson, E. Welzl, On the Number of Upward Planar Orientations of Maximal Planar Graphs, Proc. 23rd Int. Symp. on Algorithms and Computation (ISAAC) (2012), Lecture Notes in Computer Science 7676 (2012), 413-422.
J. Giesen, M. Jaggi, S. Laue, Regularization Paths with Guarantees for Convex Semidefinite Optimization, Proceedings of 15th International Conference on Artificial Intelligence and Statistics (AISTATS) (2012), 432-439.
A. Gundert, U.Wagner, On Laplacians of Random Complexes, Proc. 28th Annual ACM Symposium on Computational Geometry (SoCG) (2012), 151-160.
Y.-L. Hwong, V. Kusters, T. Willemse, Analysing the Control Software of the Compact Muon Solenoid Experiment at the Large Hadron Collider, Fundamentals of Software Engineering, Lecture Notes in Computer Science 7141 (2012), 174-189.
C. Müller, S. Stich, On spectral invariance of Randomized Hessian and Covariance Matrix Adaptation schemes, 12th International Conference on Parallel Problem Solving From Nature (PPSN) (2012), 448-457.
M. Sharir, A. Sheffer, E. Welzl, Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique, Proc. 26th Annual Symposium on Computational Geometry (SoCG) (2012), 189-198.
J. Cardinal, N. Cohen, S. Collette, M. Hoffmann, S. Langerman, G. Rote, Coloring Dynamic Point Sets on a Line, Abstracts 28th European Workshop on Computational Geometry (EuroCG), Assisi, Italy, (2012), 209-212.
A. FRANCKE
"A Metric Embedding: Ulam's Metric into l1",
Theory Lunch CSE Departement,
University of Washington, USA (Apr 6, 2012).
B. GÄRTNER
"Support Vector Machines meet Goldfarb Cubes",
The First ETH-Japan Workshop on Science and Computing,
Engelberg, Switzerland (Mar 13, 2012).
"The Many Facets of Smallest Enclosing Balls",
Mini-Symposium on Geometric Algorithms: Theory and Practice,
Tel Aviv University, Israel (May 23, 2012).
"Abstract optimization problems revisited",
21st International Symposium on Mathematical Programming (ISMP 2012),
TU Berlin, Germany (Aug 22, 2012).
A. GUNDERT
"On Laplacians of Random Complexes",
ACM SoCG - Symposium on Computational Geometry 2012,
University of North Carolina, Chapel Hill, USA (Jun 18, 2012).
"Higher-dimensional 'Graph Theory'", Rump Session (5 minutes),
Women in Theory 2012,
Princeton University, USA, Jun 23 - 27, 2012.
"Expansion Properties for Simplicial Complexes",
Oberseminar, Institute for Algebra, Geometry, Topology and their applications,
University of Bremen, Germany, (Dec 4, 2012).
T. HERTLI
"Exact Algorithms for SAT Problems (Part I)",
The First ETH-Japan Workshop on Science and Computing,
Engelberg, Switzerland (Mar 13, 2012).
"3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General",
School of Informatics, Kyoto University, Japan (Jun 22, 2012).
"An Introduction to the PPZ Algorithm",
Kyoto University, Japan (Jul 12, 2012).
M. HOFFMANN
"Counting Plane Graphs: Pseudo-Flippability and Applications",
Combinatorics and Discrete Geometry Seminar, University of Calgary, Canada (Jan 20, 2012).
"Counting Plane Graphs",
The First ETH-Japan Workshop on Science and Computing,
Engelberg, Switzerland (Mar 14, 2012).
"On Universal Point Sets for Planar Graphs",
Mittagsseminar, TU Graz, Austria (Nov 20, 2012).
V. KUSTERS
"Simultaneous embeddings",
The First ETH-Japan Workshop on Science and Computing,
Engelberg, Switzerland (Mar 12, 2012).
"WP3: simultaneous embeddings", GraDr Midterm meeting, TU Berlin, Germany (Oct 3, 2012).
"On Universal Point Sets for Planar Graphs",
Thailand-Japan Joint Conference on Computational Geometry and Graphs 2012,
Srinakharinwirot University, Bangkok, Thailand (Dec 8, 2012).
J. MATOUŠEK
"Higher-order Erdős-Szekeres theorems", EPFL Lausanne, Switzerland (Mar 2012).
"Discrepancy, Bansal's algorithm, and the determinant bound",
Graphs@GeorgiaTech,
Georgia Inst. of Technology, Atlanta, USA (May 7, 2012).
"Discrepancy, Bansal's algorithm, and the determinant bound",
ESF Mathematics Conference "Perspectives in Discrete Mathematics",
Bellaterra, Spain (Jun 25, 2012).
R. MOSER
"Exact Algorithms for SAT Problems (Part II)",
The First ETH-Japan Workshop on Science and Computing,
Engelberg, Switzerland (Mar 13, 2012).
S. STICH
"Advertising Randomized derivative-free optimization",
The First ETH-Japan Workshop on Science and Computing,
Engelberg, Switzerland (Mar 12, 2012).
"Convergence of Local Search",
6th workshop on Theory of Randomized Search Heuristics (ThRaSH 2012)
Lille/Villeneuve d'Ascq, France (May 3, 2012).
"Convergence of Local Serach",
21st International Symposium on Mathematical Programming (ISMP 2012),
TU Berlin, Germany (Aug 22, 2012).
"Variable Metric Random Pursuit",
CGLearning Review Meeting,
Berlin, Germany (Dec 14, 2012).
U. WAGNER
"Eigenvalues of Random Complexes",
Bernoulli Reunion Conference on Discrete and Computational Geometry,
EPF Lausanne, Switzerland (Mar 2, 2012).
"A Primer on Higher-Dimensional Expansion",
First ETH-Japan Symposium for the Promotion of Academic Exchanges,
ETH Zürich, Switzerland (Mar 8, 2012).
"A Primer on Higher-Dimensional Expansion Properties",
48th Netherlands Mathematical Congress (Geometry Section),
TU Eindhoven, The Netherlands (Apr 12, 2012).
"Discrete Isoperimetry, Higher-Dimensional Expanders, and Geometric Applications" (tutorial),
Journées de Géometrie Algorithmique,
Centre Arts et Métiers Paris Tech, Cluny, Saône-et-Loire, France (Apr 5-6, 2012).
E. WELZL
"A Combinatorial View of SAT",
First ETH-Japan Symposium for the Promotion of Academic Exchanges,
ETH Zürich, Switzerland (Mar 8, 2012).
A. FRANCKE
Fulbright Foreign Student Grant 2011/12.
Visiting Student Researcher at the University of Washington, Seattle WA, USA (Sep 2011 - Aug 2012).
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 12).
K. FUKUDA
Editorial Board Member of
European J. Combinatorics, Computational Geometry: Theory and Applications,
Applied Mathematics Research eXpress.
Program committee member of
B. GÄRTNER
Member of the CGAL Editorial Board.
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Mobilitätsberater des Departements Informatik
Coreferee for dissertations of
A. GUNDERT
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 12).
Teach. Assistance Computational Geometry (D-INFK) (Fall 12).
T. HERTLI
Teach. Assistance Coordinator.
Research visit with Prof. Kazuo Iwama at School of Informatics, Kyoto University, Japan (Jun 18 - Jul 13, 2012).
Workshop on Satisfiability (WSAT 2012), Aarhus University, Danmark (Aug 19 - 23, 2012).
Dagstuhl Seminar SAT Interactions, Wadern, Germany (Nov 18 - 23, 2012).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 12).
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Program committee member of
V. KUSTERS
Coordinator Mittagsseminar (since 7 Nov).
Teach. Assistance Geometric Graphs: Combinatorics and Algorithms (D-INFK) (Spring 12).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 12).
J. MATOUŠEK
Elected member of the
R. MOSER
Coordinator Mittagsseminar (until 6 Nov).
Teach. Assistance Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 12).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 12).
Teach. Assistance Algorithms, Probability, and Computing (honours parts) (D-INFK) (Fall 12).
S. STICH
Webmaster www-gremo.
Teach. Assistance Approximation Algorithms and Semidefinite Programming (D-INFK) (Spring 12).
Teach. Assistance Algorithms Lab (D-INFK) (Fall 12).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 12).
E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich,
and member of the board of the Department of Computer Science, ETH Zurich.
Coreferee for dissertations of
Editorial/Advisory 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.
