## Theory of Combinatorial Algorithms

This page describes the third-party-fund projects I am (or have been) involved in.
• # Unique Sink Orientations (2021-2025)

(Financed by the Swiss National Science Foundation). A unique sink orientation (USO) is an orientation of the n-dimensional hypercube graph, with the property that every face (subcube) has a unique sink. In particular, there is a unique global sink. The algorithmic problem associated with a USO is that of finding the global sink. A vertex evaluation oracle can be asked for the orientations of all n edges incident to a given vertex. The complexity of a (randomized) sink-finding algorithm is the (expected) number of oracle queries it needs in the worst case to find the global sink of an n-dimensional USO. It is unknown whether the sink can be found with polynomially (in n) many oracle queries, but there are also no hardness results. USOs have been introduced in the context of linear complementarity problems by Stickney and Watson, and later as combinatorial objects by Szabó and Welzl. Other optimization problems have also been shown to give rise to USOs ,most notably linear programming (LP), but also quadratic programming and more general convex optimization problems such as finding the smallest enclosing ball of a set of points, or a set of balls. Being able to find the sink in polynomial time would answer two major open questions in optimization theory: (i) is there a strongly polynomial-time algorithm for linear programming? This question is on Smale's 1998 list of mathematical problems for the next century; (ii) is there a polynomial-time algorithm for P-matrix linear complementarity problems? These problems are well-studied and known to fall into a number of (recent) complexity classes, but hardness results are not known, either. The fact that the aforementioned open questions are long-standing indicates that the goal of polynomial-time sink-finding in USOs is not very realistic. Despite this, USOs have been studied by many researchers (including the applicant) over the past twenty years, since they provide a clean and simple combinatorial framework in which many other relevant questions can be asked (and actually answered). These questions often impact or relate to concrete questions in optimization theory. For example, the currently best deterministic algorithm for P-matrix linear complementarity problems is USO-based. Notwithstanding the research interest in sink-finding in USOs, most of the initial algorithmic results of Szabó and Welzl have still not been improved significantly. Over the last three years, many new but somewhat "isolated" insights on USOs have been obtained, although with some surprising connections showing up here and there. Much of this work was done in joint research of the applicant with students, in the context of Bachelor's, Master's and PhD theses. The goal of this project is to unify and extend this research, systematically explore promising directions that have so far only been touched, and eventually make progress also on the algorithmic problem. As Szabó and Welzl (lightheartedly, in hindsight) put it in 2001, "there is ample space for improvement". During the project, we want to explore this space.

# Programmieren von klein auf in der Schweiz (2017-2020)

A three year project, funded by the Department of Computer Science, ETH Zürich, and the Haslerstiftung. The goal of this project is to assess and improve the effectiveness of computer science teaching material that has been developed in a pilot project at D-INFK and Kinderlabor. The material is targeted at teachers with no prior exposure to computer science; it allows them to teach basic programming concepts to children of ages 4-8, with the use of a simple programmable floor robot. During the project, we will monitor the use of the material in selected schools and evaluate its effects on the skills of the children. An important part of the project is the development of measurable (short-term and long-term) success criteria, according to the methodologies of teaching and learning research. Project Partners: Prof. Elsbeth Stern (D-GESS), Petra Adamaszek (Kinderlabor.ch)
• # Programmieren von klein auf an der ETH Zürich (2015-2016)

A two year project, funded by the Department of Computer Science, ETH Zürich, Haslerstiftung , Akademien der Wissenschaften der Schweiz. Zusammen mit dem Departement für Informatik der ETH Zurich errichtet das Kinderlabor ein hochqualitatives und gleichzeitig allgemein zugänglichen Weiterbildungsangebot in Informatik. Zielgruppe sind Lehrpersonen in Kindergarten und Unterstufe der Primarschule (1. / 2. Klasse), auch ohne Informatik-Vorkenntnisse. In den Kursen lernen die Teilnehmenden die sogenannten Bee-Bots kennen. Das sind kindlich gestaltete Bodenroboter in Bienenform. Sie können mit vier Richtungstasten so programmiert werden, dass sie vorgegebene Wege laufen können. Zusammen mit den Bee-Bots werden passende Unterrichtsmaterialien vorgestellt und eingesetzt. Nach dem Kurs können Lehrpersonen eine „Bee-Bot-Kiste“ für die Dauer von 2 – 4 Wochen ausleihen. Auf Wunsch kommt ein Studierender der Informatik der ETH Zürich in die Klasse, um die Lehrperson beim Einsatz zu unterstützen und zu coachen.
• # Redundancy in Linear and Neuromuscular Systems (SNF Project 200021_150055 / 1) (2013-2016)

A three year project, funded by the Swiss National Science Foundation (SNF). 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.
• # Computational Geometric Learning (STREP Project No. 255827)

I was the site coordinator for ETH in this multinational project.

### Project Outline:

A three-year project, funded by the 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.
• # Linear Time Kernel Methods and Matrix Factorizations

A project funded by a Google Research Award (supported student: Martin Jaggi). 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.
• # Support Vector Machines: Geometry, Combinatorics and Algorithms (SNF Project 20PA21-121957)

A two-year project funded by the Swiss National Science Foundation (SNF). 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 (Bernd Gärtner, Martin Jaggi, ETH Zürich), and one partner from Germany (Joachim Giesen, Friedrich-Schiller-Universität Jena).
• # Games and Geometric Unique Sink Orientations (SNF project 200020-112068/1)

A two-year project, funded by the Swiss Science Foundation (SNF). Co-workers in this project are Tibor Szabo, Emo Welzl and Leo Rüst.

### Project Outline

In the first part of the project, we will be dealing with combinatorial structure in games and matrix classes. This is motivated by the recent research that links certain well-studied classes of games to exactly the abstract combinatorial models we were studying in the project Combinatorial Models for Geometric Optimization. This research concerns the classes of simple stochastic games, mean payoff games and parity games. The second part of the project deals with specific unique sink orientations (USO) arising from geometric applications. Within the former project Combinatorial Models for Geometric Optimization, we have shown that a USO is hidden behind any linear program (LP), and that this USO has a special property: it satisfies the Holt-Klee condition, a combinatorial condition concerned with directed paths in the USO. We call such a USO geometric.
• # Algorithms for Complex Shapes with Certified Numerics and Topology (ACS) (STREP project No. FP6-006413-2, funded by the EU)

I was the site coordinator for ETH in this multinational project.

### Project Outline:

Increasingly demanding applications of geometric computing, for example in CAD/CAM, computer aided surgery, realistic virtual environments, robotics, and molecular modeling in drug design and structural biology, require efficient and robust methods for computing with complex shapes. This project aims at advancing the state of the art in this field. Current technology can cope well with curves in the plane and smooth surfaces in three-dimensional space. We want to deal with a larger class of shapes, including piecewise smooth and singular surfaces. Topics that we address are shape approximation (including meshing and simplification), shape learning (including reconstruction and feature extraction), as well as robust modeling (including boolean operations). Our work on these topics will be closely intertwined with basic research on shape representations, certified geometric calculus and algorithms producing output with guaranteed topology. A distinctive feature is the design and implementation of novel algorithmic solutions with certified topology and numerics as an alternative for heuristics and ad hoc methods, and the development of an experimental geometry kernel for modeling and computing with complex shapes as a proof-of-concept justifying our approach. The results of this project should be directly useful to the application areas mentioned above. We intend to disseminate our work by publication in the appropriate applied research forums, by organizing multidisciplinary workshops aimed at exchange of knowledge and discussion of our work. Moreover, we aim at transferring our new technology by producing high quality software, demonstrating the feasibility of our techniques in practice. Cooperation with our industrial partner includes the assessment, trial, validation and packaging of the software developed in the project, thus guaranteeing a smooth transfer of new technology to application areas. At ETH, we focus on new geometric data structures and optimization-based primitives to deal with shapes, and we provide according software components, building on our experience with reconstruction and optimization software for various tasks.
• # Combinatorial Models for Geometric Optimization Problems (SNF project 200021-100316/1)

A two-year project, funded by the Swiss Science Foundation (SNF). Co-workers in this project are Tibor Szabo, Emo Welzl and a PhD student to be appointed.

### Project Outline

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 does not depend on the bit complexity of the input.

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

• # ECG - Effective Computational Geometry (Shared-cost RTD (FET Open) Project No IST-2000-26473)

This is a three-year multinational project, funded by the European Union, that started in 2001. The project deals with the efficient handling of curved objects in computational geometry. My part deals with geometric optimization problems involving curved objects, like computing the smallest enclosing ball of a set of balls, or the smallest enclosing ellipsoid of a set of points. I am working on these topics together with my PhD student Kaspar Fischer.

• # Combinatorial Bounds for Geometric and Abstract Optimization Problems (SNF project 21.50617/97)

I was leading this two-year project, funded by the Swiss Science Foundation (SNF) between 1998 and 2000. Co-workers in this project were Emo Welzl and Falk Tschirschnitz as PhD student under my supervision. Building on results obtained during this project and after its completion, Falk Taschirschnitz will finish his PhD in 2003.

### Project Outline

The study of abstract optimization, its complexity, and its interplay with concrete (geometric) optimization problems has emerged from two lines of research that independently led to almost the same results in 1992. One line was concerned with bounds for the diameter of polytope and polyhedra graphs, the second one dealt with efficient combinatorial algorithms for Linear Programming. These are algorithms whose runtime only depends on the combinatorial structure of the linear program (like the simplex method) but not on the size of its coordinates (like the ellipsoid method).

These independent developments share an important feature: they do not only apply to polytopes and Linear Programming but to a more general, `abstract' setting - the setting of LP-type problems. This success, made possible by taking an `abstract look' that goes beyond the concrete problem, subsequently led to many work on LP-type problems and other related frameworks.

The proposed project aims at deepening the understanding of these frameworks and its interplay with concrete problems. Here, the abstraction is not a goal in itself but a means to understand which properties of optimization problems are crucial for an efficient treatment, and which role randomization plays in the algorithms. The idea is to treat combinatorial questions on a combinatorial level, abstracting from actual coordinates and other representation issues. The ultimate goal is to turn the insights obtained into new upper and lower bounds for the combinatorial complexity of concrete optimization problems like Linear Programming.

• # GALIA - Geometric Algorithms for Industrial Applications (ESPRIT IV Long Term Research Program 28155)

This 18 months multinational project, funded by the European Union, started in 1998. Its goal was to make computational geometry algorithms available for industrial applications. Building on the body of software already available in the CGAL library, the project added a large number of new algorithms, with particular focus on industrial strength code. As a result of the GALIA project, a company was founded that now sells software based on the CGAL library.

My part of the project, carried out together with my PhD student Sven Schönherr dealt with geometric optimization software. The major deliverable is a quadratic programming solver tuned for applications in computational geometry, see the PhD thesis of Sven Schönherr.

• # CGAL - Constructing a Geometric Algorithms Library (Esprit Project 21957)

This 21 months multinational project which started in 1996 laid the grounds for the CGAL library, by now a standard library for computational geometry software. The goal was to show that the large body of theory available in the computational geoemtry community could actually be turned into efficient implementations. My part of the project, carried out together with my PhD student Sven Schönherr dealt with geometric optimization software.