13:30-13:40 Ouverture des journées : présentation du GT
13:45-14:45 - Exposé invité n°1 : Claire MATHIEU (LIENS)
[Vidéo]
[Slides]
Bornes inférieures par dualité pour l'analyse d'algorithmes
14:50-15:05 - Christian KONRAD (LIAFA)
Budget Error-Correcting under Earth-Mover Distance [ PDF ]
Joint work with: Wei Yu, Qin Zhang
15:10-15:25 - Nathanaël FRANÇOIS (LIAFA)
Streaming Complexity of Checking Priority Queues [ PDF ]
Joint work with Frédéric Magniez
15:25-15:50 Pause café
15:50-16:50 - Exposé invité n°2 : Dieter KRATSCH (LITA)
[Vidéo]
[Slides]
Lower bounds in parameterized complexity
16:55-17:10 - Rémi WATRIGANT (LIRMM)
On Finding a Sparse Subgraph in Subclasses of Perfect Graphs [ PDF ]
Joint work with: M. Bougeret, R. Giroudeau
17:15-17:30 - Mamadou Moustapha KANTÉ (LIMOS)
Linear Rank-Width of Trees [ PDF ]
Joint work with: Isolde Adler
17:35-17:50 - Johan THAPPER (LRI)
The complexity of finite-valued CSPs [ PDF ]
17:50-18:30 - Discussions libres sur le fonctionnement du GT CoA
9:00-10:00 - Exposé invité n°3 : David ILCINKAS (LaBRI)
[Vidéo]
[Slides]
Connaissance initiale et résultats d'impossibilité en algorithmique distribuée
(Initial knowledge and impossibility results in distributed computing)
Résumé (Fr). Dans le cadre de l'algorithmique distribuée, un processus ne connaît généralement pas exactement l'instance du problème lorsqu'il démarre son exécution. Ainsi de nombreux algorithmes distribuées supposent que chaque processus dispose initialement d'une certaine connaissance sur l'instance, par exemple une borne supérieure sur la taille du réseau. Pour certains problèmes, il semble que l'absence d'un certain type de connaissance initiale rende le problème impossible à résoudre. Nous nous intéresserons dans cet exposé à des formalisations possibles du concept de connaissance initiale qui permettraient de pouvoir prouver de tels résultats d'impossibilité.
Abstract (EN). In the distributed computing framework, a process does not generally know the whole instance of the problem when it starts its execution. Numerous distributed algorithms so assume that each process is initially provided with some piece of knowledge about the instance, like an upper bound on the total number of processes. For some problems, it seems that the lack of some kind of initial knowledge makes the problem impossible to solve. In this talk, we will be interested in how to formalize the concept of initial knowledge such that it would allow to formally prove such impossibility results.
10:05-10:20 - Arnaud LABOUREL (LIF)
Collecting information by power-aware mobile agents [ PDF ]
joint work with: Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Andrzej Pelc, Yann Vaxès
10:20-10:45 - Pause café
10:45-11:45 - Exposé invité n°4 : Sophie LAPLANTE (LIAFA)
[Slides]
Introduction à la complexité de la communication
(Introduction to Communication Complexity)
[pas de vidéo pour cet exposé, opposition de l'orateur-rice]
11:50-12:05 - Bruno GRENET (LIP)
τ-conjecture réelle et bornes inférieures pour le permanent [ PDF ]
Joint work with: Pascal Koiran, Natacha Portier, Yann Strozecki
12:10-12:25 - Sébastien TAVENAS (LIP)
Approche de la τ-conjecture réelle à l'aide du Wronskien [ PDF ]
Joint work with: Pascal Koiran, Natacha Portier
12:25 - Fin des premières journées du GT CoA