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 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 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). Understanding and removing redundancy in a given data to improve computational efficiency or discover its fundamental structure is a universal problem in science and engineering, as the data or the mathematical model to be analyzed in any realistic situation often contains redundant information that is implied by the rest. This research project has two intertwined goals, one of them theoretical, the other one driven by a concrete application. On the theoretical level, we want to understand the structure of redundancy and the complexity of redundancy removal in explicitly or implicitly given linear and more abstract systems. Here we strongly build on our expertise in computational geometry as well as combinatorial optimization. On the application side, we want to compute redundancy and assess the role of redundancy in neuromuscular control, a field that is trying to understand how the nervous system is selecting and implementing specific muscle commands that meet the constraints of specific tasks. This part of the project will be performed in close collaboration with Francisco Valero-Cuevas. He pioneered in modeling the interplay of various muscles in terms of zonotopes whose internal structure determines the possible tasks that the muscles under consideration can achieve together.
Contact: B. Gärtner, K. Fukuda
(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
P. K. Agarwal, J. Matoušek, M. Sharir, On range searching with semialgebraic sets II, SIAM Journal of Computing 42:6 (2013), 2039-2062.
O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, B. Vogtenhuber, Maximizing maximal angles for plane straight-line graphs, Computational Geometry: Theory and Applications 46:1 (2013), 17-28.
C. Ambühl, B. Gärtner, B. von Stengel, Optimal lower bounds for projective list update algorithms, ACM Transactions on Algorithms, 9:4 (2013), 31:1-31:18.
D. Chen, P. Morin, U. Wagner, Absolute approximation of Tukey depth: Theory and experiments, Computational Geometry - Theory and Applications 46:5 (2013), 566-573.
M. Eliáš, J. Matoušek, Higher-order Erdős-Szekeres theorems, Advances in Mathematics 244 (2013), 1-15.
K. Fukuda, H. Miyata, S. Moriyama, Complete enumeration of small realizable oriented matroids, Discrete and Computational Geometry 49 (2013), 359–381.
B. Gärtner, C. Müller, S. Stich, Optimization of Convex Functions with Random Pursuit, SIAM Journal on Optimization 23:2 (2013), 1284-1309.
H. Gebauer, On the Construction of 3-Chromatic Hypergraphs with Few Edges, Journal of Combinatorial Theory Series A 120:7 (2013), 1483-1490.
H. Gebauer, Size Ramsey Number of Bounded Degree Graphs for Games, Combinatorics, Probability and Computing 22:4 (2013), 499--516.
Y.-L. Hwong, J. Keiren, V. Kusters, S. Leemans, T. Willemse, Formalising and analysing the control software of the Compact Muon Solenoid Experiment at the Large Hadron Collider, Science of Computer Programming 78:12 (2013), 2435-2452.
M. Krèál, J. Matoušek, F. Sergeraert, Polynomial-time homology for simplicial Eilenberg-MacLane spaces, Journal of Foundations of Computational Mathematics 13:6 (2013), 935-963.
J. Matoušek, The determinant bound for discrepancy is almost tight, Proceedings of the American Mathematical Society 141 (2013), 451-460.
A. Razen, E. Welzl, On the Number of Crossing-Free Partitions, Computational Geometry - Theory and Applications 46:7 (2013), 879-893.
H. Tyagi, E. Vural, P. Frossard, Tangent space estimation for smooth embeddings of Riemannian manifolds, Information and Inference 2:1 (2013), 69-114.
M. Sharir, A. Sheffer, E. Welzl, Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique, Journal of Combinatorial Theory, Series A 120:4 (2013), 777-794.
A. Asinowski, J. Cardinal, N. Cohen, S. Collette, T. Hackl, M. Hoffmann, K. Knauer, S. Langerman, M. Lason, P. Micek, G. Rote and T. Ueckerdt, Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles, Proc. 13th Algorithms and Data Structures Symposium (WADS) (2013), LNCS 8037, 73-84.
M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner, Extending continuous maps: polynomiality and undecidability (extended abstract), Proc. 45rd Annual ACM Symposium on Theory of Computing (STOC) (2013), 595-604.
J. Cardinal, M. Hoffmann, V. Kusters, On Universal Point Sets for Planar Graphs, Proc. Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG) (2013), LNCS 8296, 30-41.
M. Geyer, M. Hoffmann, M. Kaufmann, V. Kusters, Cs. D. Tóth, Planar Packing of Binary Trees, Proc. 13th Algorithms and Data Structures Symposium (WADS) (2013), LNCS 8037, 353-364.
X. Goaoc, J. Matoušek, P. Paták, Z. Safernová, Simplifying inclusion-exclusion formulas, European Conference on Combinatorics, Graph Theory and Applications (Eurocomb) (2013), 559-565.
J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Untangling two systems of noncrossing curves, 21st International Symposium on Graph Drawing (2013), LNCS 8242, 472-483.
A. Thomas, J. van Leeuwen, Treewidth and Pure Nash Equilibria, 8th International Symposium on Parameterized and Exact Computation (IPEC 2013) (2013), LNCS 8246, 348-360.
H. Tyagi, E. Vural, P. Frossard, Tangent space estimation bounds for smooth manifolds, 10th International Conference on Sampling Theory and Applications (SAMPTA) (2013), to appear.
O. Aichholzer, G. Aloupis, E. Demaine, M. Demaine, S. Fekete, M. Hoffmann, A. Lubiw, J. Snoeyink, and A. Winslow, Covering Folded Shapes, Proc. 25th Canadian Conference on Computational Geometry (CCCG) (2013), 73-78.
O. Aichholzer, J. Cardinal, Th. Hackl, F. Hurtado, M. Korman, A. Pilz, R. Silveira, R. Uehara, B. Vogtenhuber, E. Welzl, Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane, Proc. 25th Canadian Conference on Computational Geometry (CCCG) (2013), 169-174.
I. Emiris, V. Fisikopoulos and B. Gärtner, Efficient Volume and Edge-Skeleton Computation for Polytopes Given by Oracles, Abstracts of the 29th European Workshop on Computational Geometry (EuroCG), Braunschweig, Germany, (2013), 111-114.
B. Gärtner, C. Helbling, Y. Ota, T. Takahashi, Large Shadows from Sparse Inequalities, (2013).
A. Gundert, U. Wagner, On the Subdivision Containment Problem for Random 2-Complexes, Computational Geometry Week: Young Researchers Forum 2013, Rio de Janeiro, Brazil, (2013).
M. Hoffmann, V. Kusters, G. Rote, M. Saumell, and R. Silveira, Convex Hull Alignment through Translation, Proc. 25th Canadian Conference on Computational Geometry (CCCG) (2013), 295-300.
H. Tyagi, S. Stich, B. Gärtner, Stochastic continuum armed bandit problem of few linear parameters in high dimensions, (2013).
B. GÄRTNER
"Computational Geometry: Linear Programming", Mini-Course, IMPA Summer Program, Rio de Janeiro, Brazil (Jan 21-25, 2013).
"The Linear Complementarity Problem: An Advertisement", Graduiertenkolleg "Methods for Discrete Structures", FU Berlin, Germany (May 6, 2013).
A. GUNDERT
"Expansion for graphs and two ways to generalize this to simplicial complexes", Mathematical PhD Colloquium, DIAM, Delft University of Technology (Feb 26, 2013).
"Short Talk: Taking Graph Theory to Higher Dimensions", Young Women in Discrete Mathematics, Research Institute for Discrete Mathematics, Bonn (Jun 7, 2013).
"On the Subdivision Containment Problem for Random 2-Complexes", Computational Geometry Week: Young Researchers Forum 2013, Rio de Janeiro, Brazil (Jun 18, 2013).
T. HERTLI
"A Faster Algorithm For Unique 3-SAT", Exponential Algorithms:
Algorithms and Complexity Beyond Polynomial Time, Schoss Dagstuhl,
Wadern, Germany (Aug 13, 2013).
M. HOFFMANN
"On Universal Point Sets and Simultaneous Geometric Embeddings", CSASC 2013, Koper, Slovenia (Jun 10, 2013).
"Planar Packing of Binary Trees", EPF, Lausanne, Switzerland (Jul 16, 2013).
V. KUSTERS
"On Universal Point Sets for Planar Graphs",
Noon seminar at Technische Universiteit Eindhoven, Netherlands (Jan 8, 2013).
"Convex hull alignment through translation",
Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Onatrio, Canada (Aug 10, 2013).
"Planar Packing of Binary Trees", Algorithms and Data Structures Symposium (WADS 2013), London, Ontario, Canada (Aug 14, 2013).
J. MATOUŠEK
"Algorithmic aspects of embedding simplicial complexes in R^{d}", Dresdner Math. Seminar, TU Dresden, Germany (Nov 13, 2013).
S. STICH
"Optimization and Learning with Random Pursuit", CG Learning Review Meeting, Athens, Greece (Oct 2, 2013).
A. THOMAS
"Treewidth and Pure Nash Equilibria", International Symposium on Parameterized and Exact Computation (IPEC 2013), Sophia-Antipolis, France (Sep 4, 2013).
H. TYAGI
"Continuum armed bandit problem of few variables in high dimensions", Workshop on Approximation and Online Algorithms (WAOA 2013), Sophia-Antipolis, France (Sep 5, 2013).
E. WELZL
"The Counting of Crossing-Free Configurations in the Plane",
CS-Colloquium, Fakultät für Informatik, Universität Wien, Austria (Mar 20, 2013).
"Computational Geometry - Randomized Algorithms",
seven lectures at the Summer School on Random Structures and Algorithms,
Vietnam Institute for Advanced Study in Mathematics (VIASM), Hanoi, Vietnam
(Jul 8-11, 15-17, 2013).
"The Counting of Crossing-Free Geometric Graphs - Algorithms and Combinatorics",
21st Int. Symp. on Graph Drawing (GD 2013),
Bordeaux (Talence), France (Sep 24, 2013; invited talk).
A. FRANCKE
Teach. Assistance Informatics (for Biology and Pharmacy) (D-BIOL, D-PHARM) (Spring 13).
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 (until May 31, 2013).
Program committee member of
A. GUNDERT
Contact Assistant Computational Geometry (D-INFK) (Fall 13).
T. HERTLI
Teach. Assistance Coordinator.
Teach. Assistance Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 13).
Teach. Assistance Algorithms, Probability, and Computing (honours part) (D-INFK) (Fall 13).
M. HOFFMANN
Informatik Koordinator.
Teach. Assistance Algorithms Lab (D-INFK) (Fall 13).
Member of the CGAL Editorial Board.
Coreferee for master thesis of
Program committee member of
V. KUSTERS
Coordinator Mittagsseminar.
Research visit with Bettina Speckmann at Technische Universiteit Eindhoven, Netherlands (Jan 7-11, 2013).
Teach. Assistance Geometric Graphs: Combinatorics and Algorithms (D-INFK) (Spring 13).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 13).
J. MATOUŠEK
Elected member of the
Editorial Board member of
S. STICH
Webmaster www-gremo.
Research visit with Christian Müller and Jonathan Goodman, Courant Institute of Mathematical Sciences, New York University, USA (Apr 6 - Mai 8, 2013).
Dagstuhl Seminar "Theory of Evolutionary Algorithms", Wadern, Germany (Jul 1-5, 2013).
Contact Assistant Informatics (D-MATH, D-PHYS) (Fall 13).
Teach. Assistance Algorithms Lab (D-INFK) (Fall 13).
A. THOMAS
Teach. Assistance Informatics (D-MATH, D-PHYS) (Fall 13).
H. TYAGI
Teach. Assistance Informatics II (D-BAUG) (Spring 13).
Teach. Assistance Machine Learning (Fall 13).
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
Reviewer for the habilitation of
Editorial/Advisory Board member of
Member (chair, contact person) of selection committees for
Member of the
Program committee member of
Member of ETH Quality Audit Preparation Chapter Review Group "Personal".
Delegierter für Professorenwahlen an der ETH Zürich.
Mitglied der Unterrichtskommission des Departements Informatik der ETH Zürich (until March 2013).
M. WETTSTEIN
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 13).