Running Grants

• Minors and Embeddability of Simplicial Complexes

  (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

• Simultaneous Embeddings

  (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

• Computational Geometric Learning

  (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

Completed Grants

• Linear Time Kernel Methods and Matrix Factorizations

  (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

• Support Vector Machines: Geometry, Combinatorics and Algorithms

  (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

• A Fresh Look at the Complexity of Pivoting in Linear Complementarity

  (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.

  Contact: K. Fukuda, ETHZ and EPFL, J. Foniok

• Combinatorial and Computational Aspects of Embeddings

  (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

• k-Sets and Geometric Graphs

  (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

• Transversals and Colorings of Graphs

  (Financed by the Swiss National Science Foundation.) Proper coloring of graphs and the chromatic number (the smallest number of colors which allow a proper coloring) are among the most important concepts of graph theory. Numerous problems of pure mathematics and theoretical computer science require the study of proper colorings and even more real-life problems require the calculation or at least an estimation of the chromatic number. Nevertheless, there is the discouraging fact that the calculation of the chromatic number of a graph or the task of finding an optimal proper coloring are both famous intractable problems, even fast approximation is probably not possible. This is one of our motivations to study relaxations of proper coloring, because in some theoretical or practical situations a small deviation from proper is still acceptable, while the problem could become tractable. Another reason for the introduction of relaxed colorings is that in certain problems the use of the full strength of proper coloring is an ``overkill''. Often a weaker concept suffices and provides better overall results.
  In the project we study a relaxation of proper coloring, which allows the presence of some small level of conflicts in the color assignment.
  Our approach relies heavily on the theory of transversals. A set of vertices in a partitioned graph is called a transversal if it contains exactly one vertex from each class. Transversals with special properties surface in many different problems of combinatorics and theoretical computer science, when an appropriate auxiliary graph is constructed and a transversal of a certain kind is sought after. In particular independent transversals saw numerous applications in the study of list chromatic number, the satisfiability of boolean formulas, the linear arboricity of graphs and relaxed colorings of graphs. The quest for transversal results also inspired a great methodological advance in the field of combinatorics, as beautiful proofs applying combinatorial topology appeared.

  Contact: T. Szabó

• An Approach to Efficient Practical Enumeration Algorithms for Geometric and Graphic Structures from the Theory of Enumeration Methods

  (Financed by the Swiss National Science Foundation.) The main topic of this research is developing new algorithms for enumerating combinatorial objects, such as graphs and polytopes. These objects have some difficulty from the aspects of computational complexity, for example no polynomial time algorithm for checking the isomorphism of two graphs is known. However, these enumeration problems have many applications in optimizations, clustering, data mining, and machine learning, thus we need developments of efficient algorithms, in the sense of both theory and practice.

  Contact: K. Fukuda, T. Uno

• Non-linear Manifold Learning

  (Financed by the Swiss National Science Foundation.) Manifold learning is the problem of computing a model of a k-dimensional manifold embedded non-linearly in d-dimensional Euclidean space only from a finite set of sample points. Typically k is very small compared to d. The importance of the problem can be stressed by its many applications, e.g. in speech recognition, weather forecasting and economic prediction.
  Special cases of the manifold learning problem in low dimensions received a lot of attention in recent years. Most prominent is the surface reconstruction problem where a two-dimensional manifold embedded in three-dimensional space has to be learned. Some of the proposed algorithms for surface reconstruction come with the guarantee that the computed model is a manifold homeomorphic and geometrically close to the unknown manifold provided some sampling condition is fulfilled. Almost all known provable algorithms for surface reconstruction use the Delaunay triangulation of the sample points as basic data structure. Unfortunately the time to compute the Delaunay triangulation is prohibitive in higher dimensions.
  In this project we plan to investigate provable methods for manifold learning in high dimensions. Starting point should be a sampling condition similar to the one used in the proofs for surface reconstruction. The most important task in extending theoretical guarantees known from surface reconstruction to higher dimensions is to replace the Delaunay triangulation with other proximity data structures.

  Contact: J. Giesen

• Combinatorial Models for Geometric Optimization Problems

  (Financed by the Swiss National Science Foundation.) Linear programming, as well as several other geometric optimization problems do have polynomial-time algorithms in the bit model, i.e. when the input size is measured by the bit complexity of the actual numbers in the data. It is not known, however, whether there are strongly polynomial algorithms, whose performance is quantified in terms of arithmetic operations on input numbers, independently from their bit complexity. The goal of the project is to find, study, and algorithmically exploit combinatorial models for certain discrete geometric optimization problems. Our main motivation is to enhance our understanding of the combinatorics behind linear programming and related - mostly geometric - optimization problems, improve on the performance guarantees of existing algorithms, and possibly discover novel, more efficient approaches. Classical such models are matroids, oriented matroids and submodular functions.
  Within the last ten years, the concept of LP-type problems has become a recognized combinatorial model for linear programming and many other important geometric optimization problems. For many problems in the class, the currently best (or even optimal) combinatorial algorithm is an algorithm for general LP-type problems.
  In the last couple of years new exciting combinatorial models for geometric optimization problems have emerged, such as unique-sink orientations of cubes and strong LP-type problems. Just like LP-type problems ten years ago, these new combinatorial abstractions had immediate consequences; they provide the only available algorithms for certain linear complementarity problems with nontrivial running time guarantees.
  Within this new project, we plan to explore unique-sink orientations, strong LP-type problems, their relations to each other and to other known combinatorial models, as well as algorithms for problems fitting into the respective models.

  Contact: B. Gärtner, T. Szabó

• Effective Computational Geometry for Curves and Surfaces (ECG)

  (European Project.) The project intends to revisit the field of computational geometry in order to understand how structures that are well-known for linear objects behave when defined on curves and surfaces. We will consider the main geometric structures like Voroni diagrams, arrangements and Minkowski sums, study their mathematical properties, and design algorithms to construct such structures. To ensure the effectiveness of our algorithms, we will precisely specify what are the basic numerical primitives that need to be performed, and consider tradeoffs between the complexity of the algorithms (i.e. the number of primitive calls) and the complexity of the primitives and their numerical stability. Working out carefully the algebraic and robustness issues are two central objectives of the project. Another major objective is to integrate the various techniques developed in the project (e.g. algebra, arithmetics), to compare experimentally various approaches (e.g. exact versus approximate), and to provide complete solutions for some fundamental problems.
  At site Zurich we focus on surface reconstruction and several aspects of optimization within the project.
  (Coordinator: J. Giesen)

• Berlin-Zurich Graduate Program Combinatorics, Geometry, and Computation (CGC)

  (Financed by ETH Zurich and German Research Society, DFG. Starting January 1, 2003, at ETH only running scholarships are funded up to the end of the originally planed time span, but no other activities.) Successful scientific interaction between discrete mathematics, algorithms, and application areas in computer science is increasing. In particular, combinatorics and discrete geometry provide the foundations for algorithms in general, and for combinatorial optimization and computational geometry in particular. These fields, in turn, either have direct applications or provide algorithmic concepts for many application areas such as optimization, computer graphics and vision, geographic information systems, robotics, molecular modeling and computer aided design. This initiative focuses on educating graduate students in the area where these fields interact. The Pre-Doc Program constitutes a one-semester exposure to an active research environment with dedicated research-oriented courses. The Graduate Program is a joint initiative of the departments Computer Science, Mathematics and Electrical Engineering at ETH Zurich with the three universities in Berlin (and a number of other partner institutions). The goal is to establish international contacts in both research and education, and to create a focused program with completion of a Ph.D. thesis within two and a half years.
  (Contact: H. Alt, Berlin, and E. Welzl, ETHZ.)

• Geometric Algorithms for Industrial Application (GALIA)

  Finanziert durch die Europäische Gemeinschaft bzw. das Bundesamt für Bildung und Wissenschaft im Rahmen des ESPRIT IV Long Term Research Program 28155 (an der ETH mit der Arbeitsgruppe von Prof. P. Widmayer).
  Förderungszeitraum: 15. November 1998 - 14. Mai 2000
  Projektleiter: E. Welzl; Mitarbeiter: M. Hoffmann.
  Ziel des Projekts ist der weiter Aufbau einer Geometrie-Bibliothek (von Algorithmen), die Implementierung von geometrischen Algorithmen, sowie allgemeine Untersuchungen solcher Implementierungen. Der Schweizer Projektteil befasst sich vor allem mit Algorithmen zur geometrischen Optimierung (B-3) und geometrischen Suchstruckturen (B-4).
  

• Kombinatorische Schranken für geometrische und abstrakte Optimierungsprobleme

  Finanziert durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.
  Förderungszeitraum: 2 Jahre, ab 1. Oktober 1997.
  Projektleiter: B. Gärtner. Mitarbeiter: N.N.
  Das Projekt beschäftigt sich mit beweisbar effizienten Algorithmen für das Problem der linearen Programmierung und anderer, verwandter Optimierungsprobleme. In der algorithmischen Geometrie treten eine Reihe solcher Probleme auf (z.B. kleinste Kugel um eine gegebene Punktmenge, Abstand zweier Polytope). Diese Probleme können in einem abstrakten Rahmen formuliert und gelöst werden, wobei die resultierenden Algorithmen ähnlich funktionieren wie der Simplex- Algorithmus für die lineare Programmierung.
  Die theoretischen Fragen, die sich stellen, betreffen insbesondere die Komplexität simplexartiger Verfahren. Offen ist, ob es polynomielle Schranken gibt. Die besten bekannten Resultate geben immerhin subexponentielle Laufzeiten für eine randomisierte Variante an. Andere natürliche randomisierte Varianten konnten bisher nicht analysiert werden. Ziel des Projekts ist es, einerseits die bekannten Schranken zu verbesseren, andererseits aber auch neue obere und untere Schranken für die Laufzeit verschiedener randomisierter Verfahren zu finden.

• Priority Encoding Transmission - Codes and mulitmedia applications

  Finanziert durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.
  Förderungszeitraum: 1. April 1997 - 31. März 1999.
  Projektleiter: J. Blömer; Mitarbeiter: B. Trachsler.
  Im Projekt wird das Problem betrachtet, hierarchisch codierte Nachrichten über Netzwerke zu senden. Hierbei wird angenommen, dass die Netze beliebige Teile der Nachricht verlieren können. Dies ist z.B. beim Internet der Fall. Priority Encoding Transmission (PET) erlaubt es dem Benutzer, verschiedene Prioritäten den Teilen einer hierarchisch codierten Nachricht zu geben. Bei einer mit PET codierten Nachricht können die Teile der Nachricht stets in Reihenfolge ihrer Priorität decodiert werden. Eine erste Implementierung von PET wurde in ein Videokonferenztool integriert, das den Videokompressionsstandard MPEG benutzt. Die verschiedenen Prioritäten werden hierbei gemäss den verschiedenen Frametypen von MPEG zugeordnet. Da MPEG die diskrete Kosinustransformation benutzt, existieren in MPEG allerdings auch intraframe Abhängigkeiten. Im Projekt soll untersucht werden, wie diese Abhängigkeiten bei der Vergabe von Prioritäten ausgenutzt werden können.
  Die wichtigsten Hilfsmittel bei PET sind sogenannte ausfalltolerante Codes. Das zweite Ziel des Projektes ist es, effiziente ausfalltolerante Codes zu entwerfen. Im günstigsten Fall sind dies Codes, die in linearer Zeit codiert und decodiert werden können.

• Constructing a Geometric Algorithms Library (CGAL)

  Finanziert durch die Europäische Gemeinschaft bzw. das Bundesamt für Bildung und Wissenschaft im Rahmen des ESPRIT IV Long Term Research Program 21957 (an der ETH mit den Arbeitsgruppen von Prof. J. Nievergelt und Prof. P. Widmayer).
  Förderungszeitraum: 1. Oktober 1996 - 31. März 1998.
  Projektleiter: E. Welzl; Mitarbeiter: M. Hoffmann.
  Ziel des Projekts ist der Aufbau einer Geometrie-Bibliothek (von Algorithmen), die Implementierung von geometrischen Algorithmen, sowie allgemeine Untersuchungen solcher Implementierungen. Der Schweizer Projektteil befasst sich vor allem mit Algorithmen für Geographische Informationssysteme (GIS), geometrische Suchstrukturen, sowie Visualisierung und Oberflächenrekonstruktion.