CNRS GdR IM CoA

6ème journées du GT CoA
Théorie de l'information & Bornes inférieures

[ Programme | Participants | Résumé des présentations ]

Les sixièmes journées du GT CoA se dérouleront les lundi 27 (à partir de 12h00) et mardi 28 novembre (jusqu'à 14h30) dans la Salle Condorcet (1 place de l'école) à l'ÉNS Lyon et auront pour exposés et cours invités:

Organisateurs: Cyril Gavoille et Nicolas Schabanel

Informations pratiques: [ Se rendre au LIP, Hébergements à Lyon, etc. ]

La salle Condorcet « Place de l'école » :

Programme

Lundi 27 novembre, 13:30-19:00
12:00-13:00 Repas: Buffet
13:00-13:55 Cours 1/2: Information Theory and Communication Protocols
Florent URRUTIA (IRIF, U. Paris Diderot)
14:00-14:25 Applications and Constructions of cut-covering decompositions for connectivity problems
Alantha NEWMAN (G-SCOP, U. Grenoble)
14:30-14:55 Lempel-Ziv: a “one-bit catastrophe” but not a tragedy
Guillaume LAGARDE (IRIF, U. Paris Diderot)
15:00-15:25 Étude de l'algorithme glouton pour résoudre le problème du stable maximum
Mathieu MARI (Talgo, ENS Paris)
15:30-16:00 Pause café
16:00-16:55 Exposé invité: Recherche exhaustive des pentagones convexes pavant le plan
Michaël RAO (LIP, ÉNS Lyon)
17:00-17:25 On tree search and equivalent problems
Mengchuan ZOU (IRIF, Inria & U. Paris Diderot)
17:30-17:55 The firing squad problem revisited
Bernadette CHARRON-BOST (LIX, École Polytechnique)
18:00-18:30 Discussions, Avenir du GT, Changement de direction
20:00 Restaurant Pourquoi Pas? [ Site web | Plan ]
71, rue Pierre Corneille, Lyon 6 - Tél. 04 28 31 71 03

Mardi 28 novembre, 9:30-14:00
9:00-9:30 Petit déjeuner
9:30-10:25 Cours 2/2: Information Theory and Communication Protocols
Florent URRUTIA (IRIF, U. Paris Diderot)
10:30-10:55 Error-Sensitive Proof-Labeling Schemes
Laurent FEUILLOLEY (IRIF, U. Paris Diderot)
11:00-11:55 Exposé invité: Proving bounds on locality of distributed computing
Juho HIRVONEN (IRIF, U. Paris Diderot)
12:00-13:00 Repas: Buffet
13:00-13:55 Exposé invité: Explorer des graphes anonymes avec des jumelles
Jérémie CHALOPIN (LIF, U. Aix*Marseille)

Participants

PrénomNOMAffiliation27 (33)28 (31)Dîner (15)
1. PascalKOIRANENS Lyon++-
2. MathieuMARI Equipe Talgo (DIENS) + + +
3.NatachaPORTIERLIP++-
4.BinHANInstitut Camille Jordan++-
5.FranckPETITLIP6/UPMC+++
6.SébastienTAVENASLAMA, Université Savoie Mont-Blanc++
7.ÉricRÉMILAGATE Lyon St-Etienne +++
8.CyrilGAVOILLELaBRI, Université de Bordeaux++-
9.PierreFRAIGNIAUDIRIF, CNRS et Université Paris Diderot+--
10.LaurentFEUILLOLEYIRIF, Université Paris Diderot+++
11.ChristopheCRESPELLEUniversité Claude Bernard Lyon 1++-
12.BernadetteCHARRON-BOST +++
13.NicolasBOUSQUETG-SCOP, Grenoble ++-
14. PierreGUILLON Institut de Mathématiques de Marseille + + +
15.Nicolas SCHABANEL CNRS, U. Paris Diderot (IRIF) + + +
16.David ILCINKAS LaBRI, CNRS, Bordeaux ++ -
17. Patrick LAMBEIN LIX + + +
18. Karine ALTISEN Grenoble INP / Verimag + + +
19. Guillaume LAGARDE IRIF + + -
20. Michaël RAO LIP + + +
21. Jérémie CHALOPIN LIF + + +
22. Juho HIRVONEN IRIF + + +
23. Florent URRUTIA IRIF + + -
24. Rémi WATRIGANT UCBL, LIP + + -
25. Christian LAFOREST LIMOS, Université Clermont-Auvergne + + -
26. Louis ESPERET G-SCOP, Grenoble + - -
27. Basile COUËTOUX LIF Université d'Aix-Marseille + + +
28. Guillaume MALOD IMJ-PRG + + -
29. Etienne MOUTOT LIP, ENS Lyon + + +
30. Mengchuan ZOU Inria et IRIF + + -
31. Alantha NEWMAN G-SCOP Grenoble + + +
32. Andrei ROMASHCHENKO LIRMM + + -
33. Antonin LENTZ LaBRI, Bordeaux + + -
...

Résumés des talks invités

Information Theory and Communication Protocols, Florent Urrutia (IRIF, U. Paris Diderot)

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 Pi, each with input Xi, wish to compute the value of f(X1,...,Xk). 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.

Explorer des graphes anonymes avec des jumelles, Jérémie Chalopin (CNRS, LIF)

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.

Proving bounds on locality of distributed computing, Juho HIRVONEN (IRIF, U. Paris Diderot)

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.

Recherche exhaustive des pentagones convexes pavant le plan, Michaël Rao (CNRS, LIP)

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.