Ces journées sont organisées en coopération avec le laboratoire FILOFOCS (French Israeli Laboratory on Foundations of Computer Science)
Liste des [ inscrit-e-s ]
12:30-13:35 Buffet repas chaud et froid
13:35-13:40 Ouverture des journées
13:45-14:45 - Exposé invité n°1 : Frédéric MAGNIEZ (LIAFA)
Introduction to streaming algorithms [ Video | Slides ]
We will review some of the main streaming algorithms in the area of statistics, strings and graphs. The talk will be self contained.
15:00-15:20 - Arnaud DE MESMAY (LIENS)
Testing Graph Isotopy on Surfaces
[ Slides (Acroread required) ]
Travail réalisé en collaboration avec: Éric Colin de Verdière (LIENS)
15:25-15:45 - Ioan TODINCA (LIFO)
Large induced subgraphs via triangulations and CMSO [ PDF ]
Travail réalisé en collaboration avec: Fedor V. Fomin et Yngve Villanger (U. Bergen)
15:45-16:15 Café
16:15-16:35 - Christian GLACET (LaBRI)
Complexité de communication du routage compact
[ Slides ]
Travail réalisé en collaboration avec: Cyril Gavoille, Nicolas Hanusse and David Ilcinkas
16:40-17:00 - Bruno GRENET (LIX)
Algorithmes élémentaires pour la factorisation des polynômes lacunaires [ Slides ]
Travail réalisé en collaboration avec: Arkadev Chattopdhyay, Pascal Koiran, Natacha Portier et Yann Strozecki
17:05-18:30 - Blitz présentations des participants
18:30-18:45 - Discussions libres sur le fonctionnement du GT CoA
9:00-9:20 - Nicolas SCHABANEL (LIAFA)
Facility Location in Evolving Metrics [ Slides ]
Travail réalisé en collaboration avec: David Eisenstat (U. Brown) et Claire Mathieu (LIENS)
9:25-10:25 - Exposé invité n°2 : Uri ZWICK (U. Tel-Aviv)
A forward-backward algorithm for single-source shortest paths [ Video | Slides: PDF | PPTX ]
We present a new algorithm for solving the single source shortest paths problem. The expected running time of the algorithm when run on a complete directed graph with independent exponential edge weights, with sorted incoming and outgoing adjacency lists, is O(n). The novelty of the algorithm is that it uses both incoming and outgoing adjacency lists. Any algorithm that only uses the outgoing adjacency lists requires Ω(n log n) expected time to solve the problem.
Joint work with David Wilson
10:25-10:55 Café
10:55-11:15 - Benjamin DOERR (LIX)
Tight Analysis of Randomized Rumor Spreading in Complete Graphs [ Slides: PDF | PPTX ]
11:20-11:40 - Hugues FAUCONNIER (LIAFA)
Quelques résultats sur les registres Multi Ecrivains Multi Lecteurs [ Slides ]
Travail réalisé en collaboration avec: C. Delporte, E. Gafni and S. Rajbaum. A recent extension to the adaptive case has been made jointly with L. Lamport.
11:45-12:05 - Frédéric MAZOIT (LaBRI)
Largeur arborescente, largeur de clique, logiques et graphes subdivisés [ PDF ]
12:10-12:30 - Guillaume DUCOFFE (COATI, U. Nice Sophia Antipolis, ENS Cachan)
On the recognition of 1/2-hyperbolic graphs: a 2
subcubic equivalence with the C4-free graph recognition problem [ Slides ]
Travail réalisé en collaboration avec: David Coudert (COATI).
12:30-13:30 - Conclusion des journées par un Vins et fromages