Séminaire de Géométrie Algorithmique et Combinatoire

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.

Il se tient un jeudi par mois, de 14h à 17h, à l'Institut Henri Poincaré à Paris (plan d'accès), en salle 201.

Contact: seminaire gac ens fr. Pour recevoir les annonces de ce séminaire, envoyer un message à cette adresse avec [inscription] dans le titre.

La liste des exposés passés est disponible ici.

23 févr. 2017
14h Sergio Rajsbaum Universidad Nacional Autonoma de Mexico, Mexique — professeur invité au LIX à l'École Polytechnique
Introduction to distributed computing analysis using combinatorial topology
[transparents]
The equivalence between single-tape and multi-tape Turing machines is often interpreted as implying that the use of one computing machine versus the use of several machines may differ in questions of efficiency, but not computability. It has been clear from early on that the addition of parallelism to Turing machines does not change the fundamental notion of Turing-computability. In the theory of distributed computing, we study computability in the presence of failures and timing uncertainties.

Task computability is very sensitive to the details of the model: failures (type and number of process and communication failures), communication (various forms of message passing and shared memory), and timing (relative process speeds and communication delays). However, the many possible distributed computing models can be understood through a common framework: There is an intimate relation between distributed computability and topology. Roughly speaking, the question whether a task is computable (and how fast) in a given model can be reduced to the question whether an associated geometric structure, called a simplicial complex has "holes" of certain dimensions. There are various implications of these insights. In particular, Turing computability is orthogonal to distributed computability. In distributed computing we allow for individual processes to have an infinite number of states, thus each one individually can solve the Halting problem, however, there are simple Turing-computable tasks that are not computable even in the presence of a single process crash. This talk presents an introduction to the fascinating topological perspective of distributed computing.

15h30 Jérémie Chalopin CNRS, LIF, Marseille
Cop and robber game and hyperbolicity
[transparents]
In this talk, we consider a variant of the cop and rober game where the cop and the robber move at different speed. The difference with the classical cop and robber game is that at each step, the cop can move along a path of length at most $s'$, and the robber can move along a path of length at most $s$ (without going through the position of the cop). A graph is $(s,s')$-copwin if the cop with speed $s'$ has a strategy to capture any robber moving at speed $s$.

$\delta$-hyperbolic graphs are graphs that are close to trees from a metric point of view; we will present a few (of the many) definitions of hyperbolicity.

We will present some results relating the cop and robber game and the hyperbolicity of a graph. We show that if a graph is $\delta$-hyperbolic, then it is $(2r,r+2\delta)$-copwin for any $r$. Conversely, we show that a $(s,s')$-copwin graph (with $s>s'$) is $O(s^2)$-hyperbolic. From our approach, we deduce an $O(n^2)$ algorithm to approximate the hyperbolicity of a graph when we are given its distance matrix.

23 mars 2017
Raphaëlle Chaine LIRIS, Université Claude Bernard Lyon 1
Louis Esperet CNRS, G-SCOP, Grenoble
Box representations of embedded graphs
A box in $\RR^d$ is the cartesian product of $d$ intervals of $\RR$. For instance, a box in $\RR$ is an interval and a box in $\RR^2$ is an axis-parallel rectangle. Representing graphs as intersection graphs of low dimensional boxes (i.e. each vertex corresponds to a box of $\RR^d$ and two vertices are adjacent if and only if their boxes intersect) is an important problem with applications in the study of ecological and sociological networks. In this talk, I will give a gentle introduction to low dimensional box representations of graphs, and in particular explain an interesting connection with the notion of dimension of a partially ordered set. A classical result of Thomassen (1986) states that every planar graph can be represented as intersection graph of boxes in $\RR^3$. I will explain how this result can be extended to graphs embedded in any fixed surface: I will show that every graph of genus $g$ can be represented as the intersection graph of boxes in dimension $\sqrt{g}\log g$, while random graphs provide a lower bound of order $\sqrt{g\log g}$. I will also show that if a graph is embedded in a fixed surface and has no short non-contractible cycles, then it can be represented as the intersection graph of boxes in $\RR^5$.
20 avr. 2017
Pierre-Guy Plamondon Université Paris-Sud
Combinatoire des triangulations de surfaces
Lionel Pournin LIPN, Université Paris 13
11 mai 2017
Guilherme Dias da Fonseca Université Clermont Auvergne
Geometric Approximation Using a Hierarchy of Macbeath Regions
This talk is divided in two parts, presenting two papers written with Sunil Arya and David M. Mount (SODA 2017 and SoCG 2017). Both papers are based on a new hierarchy of Macbeath regions that approximates a convex body $K$ in $d$-dimensional space up to an error $\epsilon > 0$. For the purpose of the complexity analysis, we assume that $d$ is a constant, but that $\epsilon$ is an asymptotic variable approaching $0$. Out goal is to minimize dependencies on $\epsilon$, for example from $1/\epsilon^d$ to $1/\epsilon^{d/2}$.

In the first part of the talk, we present an optimal data structure to approximately answer if a query point $q$ is inside or outside of $K$. We attain logarithmic query time with storage of only $O(1/\epsilon^{(d-1)/2})$, which matches the worst-case lower bound on the complexity of any $\epsilon$-approximating polytope. Using known reductions, we obtain major improvements to approximate nearest neighbor searching.

In the second part, we show how the hierarchy can be used to construct an $\epsilon$-kernel in near-optimal time. Kernels provide an approximation to the convex hull, and therefore are on the basis of several geometric algorithms. We obtain major improvements to the complexity of other fundamental problems, such as approximate diameter, approximate bichromatic closest pair, and approximate Euclidean minimun bottleneck tree, as well as near-optimal preprocessing times to multiple data structures.

Pierre Alliez (sous réserve) Inria Sophia-Antipolis — Méditerranée
22 juin 2017
Boris Bukh Carnegie Mellon University
Jean-François Marckert CNRS, LaBRI, Université Bordeaux 1

Le séminaire bénéficie du soutien de l'Institut Henri Poincaré.

Le comité scientifique est constitué de:

• Éric Colin de Verdière (CNRS, LIGM, U. Paris-Est Marne-la-Vallée),
• Xavier Goaoc (LIGM, U. Paris-Est Marne-la-Vallée),
• Nabil Mustafa (LIGM, U. Paris-Est Marne-la-Vallée, ESIEE),
• Steve Oudot (Geometrica, Inria Saclay),
• Vincent Pilaud (CNRS, LIX, École Polytechnique),
• Michel Pocchiola (IMJ-PRG, Université Pierre et Marie Curie).

Le comité d'organisation est constitué d'Éric Colin de Verdière, Steve Oudot et Vincent Pilaud.