Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar: Proposed Topics

Flipping Geometric Triangulations on Hyperbolic Surfaces

[1] Vincent Despré, Jean-Marc Schlenker, Monique Teillaud.
Flipping Geometric Triangulations on Hyperbolic Surfaces.
2019.

This paper considers geometric triangulations not in the plane as usual, but on other surfaces like flat tori and closed hyperbolic surfaces. Connectivity of the corresponding flip graphs is proved and bounds for the number of flips needed to reach the Delaunay triangulation are given.

Your talk would consist of a brief overview of the well known classic results in the plane, followed by a detailed explanation of the new proof techniques and a comparison to the classic setting.

Contact: Manuel Wettstein, manuelwe@inf.ethz.ch, CAB G 38.

An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs

[2] Alexander Choi, Marek Chrobak, Kevin Costello.
An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs.
2019.

Contact: Michael Hoffmann, hoffmann@inf.ethz.ch, CAB G 33.1.

Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

[3] Valentine Kabanets and Zhenjian Lu.
Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates.
2018.

Contact: Saeed Ilchi, saeed.ilchi@inf.ethz.ch, CAB G 32.1.

Equivalences between triangle and range query problems

[4] Lech Duraj, Krzysztof Kleiner, Adam Polak, and Virginia Vassilevska Williams.
Equivalences between triangle and range query problems.
2019.

Contact: Michael Hoffmann, hoffmann@inf.ethz.ch, CAB G 33.1.

A Combinatorial Approach to Triangulations of Products of Simplices

[5] Georg Loho and Ben Smith.
Matching Fields and Lattice Points of Simplices.
2018.

Products of simplices are important polytopes that have multiple applications to game theory, optimisation, and algebraic geometry. Their triangulations can be encoded by a collection of bipartite spanning trees, whose degree vectors are distinct. Postnikov (2009) conjectures that a triangulation can be reconstructed purely from these degree vectors. Loho and Smith (2018) give a constructive proof confirming this conjecture. Independently, Galashin, Nenashev, Postnikov (2018) also provide an affirmative answer to the conjecture. Their proof is non-constructive but holds for a more general class of polytopes.

Although the problem is motivated from geometry, due to the graphical characterisation of the triangulations, the work moves strictly to the realm of combinatorics. In the paper by Loho and Smith, the result mentioned above is presented in section 4, which will be the planned main material for the talk. However, materials from other parts (e.g. section 2) and from other papers are required to obtain background understanding. Ideally, the talk should not focus on presenting detailed proofs but an overview of the problem, important combinatorial properties of the products of simplices, their triangulations, the corresponding bipatite trees, and the key ideas and discussion of the proofs in the paper.

Contact: Hung Hoang, hung.hoang@inf.ethz.ch, CAB G 19.2.

EPTAS for Max Clique on Disks and Unit Balls

[6] Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, and Stephan Thomasse.
EPTAS for Max Clique on Disks and Unit Balls.
2018.

The problem of finding a maximum clique on a graph is NP-hard. It is a long-standing problem to know what happens when we restrict the graphs considered to be disk graphs. It is known since the 90s that the problem of maximum clique can be solved in polynomial time if all the disks have the same radius. This paper gives an efficient polynomial-time approximation scheme (EPTAS) for maximum clique on disk graphs with arbitrary radii. Their algorithm also works when considering unit ball graphs. On the contrary, they show that when considering ball graphs and unit 4-dimensional disk graphs, the problem becomes NP-hard and does not admit a PTAS.

In your talk you should present the differences on finding a maximum clique on d-dimensional disks graphs, depending on the dimension d (between 2 and 4), and depending on whether the disks are unit. You should explain what properties make the problem easy or hard.

Contact: Nicolas Grelier, nicolas.grelier@inf.ethz.ch, CAB G 19.2.