**Title: Progress and challenges for labeling schemes** (__slides in PDF__)

Cyril Gavoille (University of Bordeaux, France)

http://dept-info.labri.fr/~gavoille/

**Abstract:** A fundamental question in Distributed Computing is to understand how
localized and how much information are required to solve a task on a
network. Typically, if the distance between any pair x,y of nodes in a
network is asked, we would like to know which minimal information
about x and y in the network are needed. The goal in labeling schemes
is precisely to understand how much information must be attached to
the nodes (formalized as labels) to solve a graph problem assuming the
answer can be determined solely on the basis of the labels of the
nodes invoked in the query. In this talk, I give a survey on labeling
schemes, present some recent results with their techniques, and
highlight new challenges.