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
Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl
Institut für Theoretische Informatik
Departement Informatik
ETH Zürich
CH–8092 Zürich
| phone | +41–44–632 73 92 |
| fax | +41–44–632 10 63 |
(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.
Contact: B. Gärtner
Duration: Oct 2021 – Feb 2025.
(Financed by the Innovedum Fund at ETH Zurich).
In technical fields, we write our documents almost exclusively in TeX/LaTeX.
The goal of this project is to provide the means of integrating interactive
elements (such as multiple choice questions with automatic feedback, but also
more advanced and complex features) in TeX-documents using native syntax already
familiar to instructors, and resulting in a look and feel already familiar to students.
The three main software components of this project are as follows:
Contact: B. Gärtner, M. Wettstein
Duration: Nov 2020 – Oct 2021.
(Financed by the Swiss National Science Foundation).
The classical Falconer distance conjecture says that for any compact set
E ⊂ Rd, if the Hausdorff dimension of E is greater than d/2,
then the Lebesgue measure of the distance set Δ(E) is positive.
The recent breakthrough paper of
Guth, Iosevich, Ou, and Wang tells us that in two dimensions, for any E ⊂ R2,
if the Hausdorff dimension of E is greater than 5/4, then the distance set is
of positive Lebesgue measure. This improves the some 20 year old estimate
dimH(E)> 4/3 due to Wolff.
Let q be a prime power, and Fq be the finite field of order q.
The finite field version of this problem is known as the Erdős-Falconer
distance problem, which asks for the smallest number s such that for any
E ⊂ Fqd, if |E| >= qs, then
|Δ(E)| >= cq for some positive constant c. In even dimensions, it
is conjectured that s= d/2.
In the recent paper, Murphy, Petridis,
Pham, Rudnev, Stevens proved that in the plane over prime fields Fp2,
one has s <= 5/4. More precisely, let E be a set in Fp2,
if |E| >= p5/4, then we have |Δ(E)| >= cp. This is directly
in line with Guth et al.'s result on the Falconer distance conjecture.
The main purpose of this project is to improve the exponent 5/4 and to study related questions.
Contact: Th. Pham
Duration: Sep 2020 – Sep 2021.
(Financed by the Swiss National Science Foundation).
Arrangements and drawings are two fundamental concepts that play a
central role in discrete and computational geometry: Given a set L of
planar curves, the arrangement of L is the subdivision of the plane
into faces, edges, and vertices, each defined as a maximal connected
component contained in the intersection of 0, 1, or 2 elements in L,
respectively. Given a graph G, a planar drawing of G assigns a point
in the plane to each vertex of G and represents the edges of G by
simple Jordan arcs that connect the corresponding
endpoints.
Arrangements and drawings pop up in almost every corner of discrete
and computational geometry. For example, they can be used to encode
order relationships between points, to compute convex hulls, or to
find ham-sandwich cuts. Due to the fundamental nature and the
simplicity of the concepts, a vast number of variants, special cases,
generalizations, and abstractions have been developed. The goal of
this project is to undertake a systematic study of the different
structures and their representations, and of their relevant
combinatorial and algorithmic properties.
The project will be carried out as an international collaboration with
partners from Berlin and Graz.
Contact: M. Hoffmann
Duration: Jan 2018 – Sep 2022.
