1st session: After introducing the basics of information theory, we will discuss how it was used for the study of two-party communication protocols, where two players, Alice with input X and Bob with input Y, wish to compute the value f(X,Y), where f is a given function.

2nd session: In distributed communication protocols, k players P_i, each with input X_i, wish to compute the value of f(X₁,...,X_k). The tools based on information theory which were developed for the study of two-party communication protocols cannot be generalized in a straightforward way to study distributed protocols. We will explain why, and present two new information measures which allow the study of distributed protocols.

Based on joint work with Iordanis Kerenidis and Adi Rosén.

On étudie le problème de l'exploration de graphes anonymes par un agent mobile. Il est bien connu que sans information initiale à propos du graphe, un agent ne peut détecter qu'il a exploré tous les sommets seulement si le graphe est un arbre.

Dans cet exposé, on considère une extension du modèle classique où l'agent est équipé de jumelles qui lui permettent de voir le graphe induit par le voisinage du sommet où il se trouve. On montre que dans ce modèle, il est possible d'explorer (en détectant la terminaison) une large famille de graphes. On caractérise les graphes explorables avec des jumelles en utilisant des notions de topologie discrète. Cette famille est bien plus large que la famille des arbres: elle contient en particulier les graphes triangulés, les triangulations planaires et les triangulations du plan projectif.

Locality of distributed computing is the study of how far information has to propagate in distributed systems. In the last few years, we have seen the emergence of a complexity theory of locality for a large class of natural problems, called locally checkable labelings. I will present some of the new lower bound techniques that have contributed to this theory. These techniques are based on simulation, providing elegant and simple proofs.

The sinkless orientation problem has played a key role a key role in this new theory. We gave a randomized lower bound of Ω(log log n) for this problem (Brandt et al., STOC 2016), establishing it as the first problem with provably "intermediate" complexity. Our lower bound was later lifted to an Ω(log n) deterministic lower bound by Chang et al. (FOCS 2016). This, along with the matching algorithms of Ghaffari and Su (SODA 2017), show that this problem exhibits an exponential separation between deterministic and randomized complexities.

I will show a simpler lower bound proof for this problem, using elements from different proofs. I will try to highlight the effectiveness of simulation as a proof technique, and try to showcase how complexity theoretic results can be used as black boxes in order to aid these proofs.

Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918 à 2015, 15 différents types de pentagones pouvant paver le plan ont été découverts. Je présente une recherche exhaustive de tous les pentagones convexes pavant le plan, qui permet de clore cette question. La preuve se sépare en deux parties: la première montre, en utilisant la compacité, qu'on peut se limiter à un ensemble de 371 familles, et la seconde est une recherche exhaustive informatisée, pour chacune des 371 familles, qui ne trouve aucun nouveau type de pentagones que les 15 types connus.