Department of Computer Science
Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
People
Activity Report
    2012
Previous Reports
Research
Mittagsseminar
Teaching
Workshops
Social Activities
Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2012

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

Institut für Theoretische Informatik
Departement Informatik
ETH Zürichphone +41-44-632 73 92
CH-8092 Zürichfax+41-44-632 10 63


Personnel


Guests

  • Jan Foniok, Queen's University, Kingston, Ontario, Canada (Jan 05)
    Some Ramsey applications (Mittagsseminar, Jan 05, 2012)

Grants

  • Minors and Embeddability of Simplicial Complexes

    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

  • 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, M. Jaggi

  • 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, M. Jaggi

  • 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


Publications

  • Books

    B. Gärtner, J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer Verlag (2012).

  • Journals (with refereeing)

    H. Gebauer, Disproof of the Neighborhood Conjecture with Implications to SAT, Combinatorica(2012), to appear.

    H. Gebauer, On the Clique-Game, Eur. J. Comb. 33(1), (2012), 8-19.

    J. Giesen, M. Jaggi, S. Laue, Approximating Parameterized Convex Optimization Problems, ACM Transactions on Algorithms (2012), to appear.

    Jiří Matoušek, Martin Tancer, and Uli Wagner, A geometric proof of the colored Tverberg theorem, Discrete and Computational Geometry (2012), to appear.

    A. Razen, E. Welzl, On the Number of Crossing-Free Partitions, Computational Geometry - Theory and Applications (2012), to appear.

  • Conference Proceedings (with selection process)

    A. Bärtschi and S. Suri, Conflict-free Chromatic Art Gallery Coverage, Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS) (2012), to appear.

    Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner, Computing all maps into a sphere Proc. 23nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2012), 1-10.

    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), to appear.

  • Other (including submitted work)

    K. Buchin, J. Matoušek, R. Moser, D. Pálvölgyi, Vectors in a Box (2011), submitted.

    B. Bukh, G. Nivasch, Upper Bounds for Centerlines (2012), submitted.

    P. Cheilaris, S. Smorodinsky and M. Sulovský, The potential to improve the choice: list conflict-free coloring for geometric hypergraphs (2011), submitted.

    J. Foniok, B. Gärtner, L. Klaus, M. Sprecher, Counting Unique-Sink Orientations (2011), submitted.

    B. Gärtner, M. Jaggi, C. Maria, An Exponential Lower Bound on the Complexity of Regularization Paths (2011), submitted.

    B. Gärtner, C. Müller and S. Stich, Optimization of Convex Functions with Random Pursuit (2011), submitted.

    B. Gärtner, M. Sprecher, A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix Linear Complementarity Problem (2011), submitted.

    Y.-L. Hwong, V. Kusters, T. Willemse, Analysing the control software of the compact muon solenoid experiment at the large hadron collider (2011), submitted.

    J. Matoušek, U. Wagner, On Gromov's method of selecting heavily covered points (2011), submitted.

    R. Moser, D. Scheder, A Full Derandomization of Schöning's Algorithm (2011), submitted.

    H. Nakayamka, S. Moriyama, K. Fukuda, Realizations of oriented matroids by polynomial optimization (2011), submitted.

    H. Nakayamka, S. Moriyama, K. Fukuda, Three characteristic rank-4 oriented matroids (2011), submitted.

    M. Sharir, A. Sheffer, E. Welzl, Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique (2011), submitted.

    U. Wagner, Minors, Embeddability, and Extremal Problems for Hypergraphs (2011), submitted.


Lectures


Courses and Seminars

Spring 12

See also the Course Catalogue

Fall 11

See also the Course Catalogue


Organization of Workshops etc.


Dissertations


Master and Diploma Theses

  • Abel Camacho It's a Long Way to the Top (or not)?,
    Advisors: Bernd Gärtner / to be completed

Bachelor and Semester Theses / Internship Projects

  • Dominik Müller, On Cycles in Nash Equilibria of Local Connection Games,
    Advisors: Matus Mihalek, Emo Welzl / to be completed
  • Rajko Nenadov, Holes in Hypergraphs,
    Advisor: Uli Wagner / to be completed

Miscellaneous

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.
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Kursleiter "Programmieren fuer Kinder" an der Primarschule Kloten.

T. HERTLI
Teach. Assistance Coordinator.

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.

Program committee member of

R. MOSER
Coordinator Mittagsseminar.

S. STICH
Webmaster www-gremo.

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich, and member of the board of the Department of Computer Science, ETH Zurich.

Editorial Board member of

Member (chair, contact person) of selection committees for

  • Assistant Professor for Risk and Insurance Economics, Department of Management, Technology, and Economics, ETH Zurich, (chair).

Member of the

  • Scientific Board of the Computer Science Department at Ecole normale supérieure (ENS), Paris, France.

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.


Software
18-Jan-2012 / stich@inf.ethz.ch