Mini-cours

Nicolas Bonichon (Univ. de Bordeaux): Quelques résultats sur les spanners géométriques

Un graphe géométrique est un graphe défini à partir d'un nuage de points (par exemple dans le plan). L'étirement d'un graphe géométrique est le pire rapport entre la distance dans le graphe et la  distance Euclidienne, pour toute paire de points du graphe. Un t-spanner est un graphe (ou une famille de graphes) dont l'étirement est borné par  t.

Dans cet exposé je présenterai quelques résultats relatifs à certains spanners : triangulations de Delaunay, Theta-graphs, spanners de degré borné, routage dans les triangulations de Delaunay...

Jean Cardinal (ULB, Bruxelles): The geometry of 3SUM, k-SUM, and related problems

We consider the 3SUM and k-SUM problems, defined as fixed-parameter versions of the Subset Sum Problem: Given a set of n numbers, does there exist a subset of k of them whose sum is 0? The 3SUM problem was first considered by computational geometers as a way to argue of quadratic lower bounds for some natural geometric problems. It has since become a cornerstone of the so-called fine-grained complexity theory, dealing with the computational complexity of problems in P. We will review the notion of 3SUM-hardness and the relation between k-SUM and other problems. Then we will consider recent attempts to beat the quadratic barrier for 3SUM-hard problems. Finally, we will consider the design of efficient linear decision trees for k-SUM. All these topics heavily rely on geometric notions, such as dominance detection and hyperplane arrangements.

Günter Rote (Freie Universität Berlin): The Computational Geometry of Congruence Testing (abstract: detailed version)

Testing two geometric objects for congruence, i.e., whether they are the same up to translations and rotations (and possibly reflections) is a fundamental question of geometry.
In the first part, I will survey the various algorithmic techniques that have been used since the 1970s to solve the problem in two and three dimensions in O(n log n) time for two n-point sets, such as string matching, planar graph isomorphism (Sugihara), and the reduction technique of Atkinson.

In the second part, I will introduce our recent algorithm for solving the 4-dimensional problem in O(n log n) time (joint work with Heuna Kim). This algorithm will require the study of four-dimensional geometry, in particular the structure of four-dimensional rotations, Hopf fibrations, and the regular polytopes.

Louis Theran (University of St Andrews): Global rigidity and graph realization

The global rigidity problem asks whether, given a configuration of n points in d-dimensional Euclidean space and a set of m pairs of points, there is another non-congruent configuration where the distances between the m specified pairs are the same.

The graph realization problem asks whether, given a graph G with n vertices and a desired edge length for each of its m edges, there is a configuration of n points in d-dimensional Euclidean space so that the distances between the endpoints of each edge are the desired ones.

Each of these problems is NP-hard, but under certain genericity assumptions they become tractable.  This mini-course will introduce the topic and cover recent progress on both problems.

Irene Waldspurger (Univ. Paris Dauphine): Algorithms for phase retrieval problems

A phase retrieval problem consists in recovering an unknown element in some complex vector space from the modulus of linear measurements. Such problems naturally arise in particular in molecular imaging and audio processing. The goal of this mini-course is to give an overview of some algorithms that have been designed to solve them, with a focus on the ones for which rigorous correctness guarantees exist.

First part : we will introduce phase retrieval problems and their applications. We will describe conditions under which these problems can be expected to be well-posed.

Second part : the non-convexity of phase retrieval problems makes them hard to solve. This issue can be partially overcome with convexification techniques. We will present two algorithms that use these techniques in different ways: PhaseLift and PhaseMax.

Third part : more recently, it has been noticed that, in some settings, phase retrieval problems can also be solved with simpler, non-convex, heuristics. We will describe a few of these heuristics, and explain how to derive correctness guarantees for them.