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.
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.
$\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.
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.
Le séminaire bénéficie du soutien de l'Institut Henri Poincaré.
Le comité scientifique est constitué de:
Le comité d'organisation est constitué d'Éric Colin de Verdière, Steve Oudot et Vincent Pilaud.