1;2802;0c Journées GT COA

Journées GT COA

28 et 29 novembre 2016



Conférenciers invités:

Guillaume FERTIN (LINA, U. Nantes)  [web]

Pierre FRAIGNIAUD (IRIF Paris)  [web]

Damien WOODS (INRIA Paris)  [web]

 

Programme:

Lundi 28 novembre, Amphi LaBRI:


12h45-14h00: repas au "Carpe Diem"

14h00-15h00: Guillaume FERTIN - The Graph Motif Problem
15h00-15h25: Tatiana Starikovskaya. Streaming k-mismatch with error correcting and applications
15h25-15h50:  Julien Fradin. An algorithmic study of the Maximum Colorful Arborescence problem
15h50-16h15: Mamadou Kanté. Counting minimal dominating sets in graphs

16h15-16h40: pause café

16h40-17h05: Frederik Mallmann-Trenn. On coalescence time in graphs -- When is coalescing as fast as meeting?
17h05-17h30: Dennis Olivetti. Sparsifying Congested Cliques and Core-Periphery Networks
17h30-17h55: Simon Collet. Local distributed Algorithms for selfish Agents

17h55-18h40:  discussions et réflexion sur le GT CoA

 

Mardi 29 novembre, Amphi LaBRI:


9h00-9h45:  - Pierre FRAIGNIAUD. Algorithmes distribués locaux
9h45-10h10:  Lucas Boczkowski. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits 10h10-10h35: Alkida Balliiu. Local Distributed Verifcation
 
10h35-10h55: pause café

10h55-11h20: Nguyen Kim Thang. Online Primal-Dual Algorithms with Configuration Linear Programs
11h20-11h45: Jean-Florent RAYMOND. Linear kernels for edge deletion problems to immersion-closed graph classes

11h45-12h45: Damien WOODS - Evaluating a large class of boolean circuits via algorithmic self-assembly of DNA strands

13h00-14h00: repas au "Carpe Diem"

 

Guillaume Fertin

The Graph Motif Problem

The Graph Motif problem is defined as follows: given a vertex-colored graph G=(V,E) and a multiset M of colors, determine whether there exists V' subset (might be equal) of V such that (1) the colors of V' exactly agree with M and (2) the subgraph G' of G induced by V' is connected. Graph Motif has been introduced roughly 10 years ago as a way to model searching for functional motifs in biological networks (such as Protein-Protein Interaction graphs or metabolic networks), and has received much attention since. In this talk, I will present a series of algorithmic complexity results concerning the Graph Motif problem, including fixed-parameterized tractable algorithms and some complexity lower bounds. In the process, different proof techniques, hopefully of interest for the audience, will be presented.

Pierre Fraigniaud

Algorithmes distribués locaux

Cet exposé présente les récentes avancées obtenues en algorithmique distribuée relatives aux problèmes qu’il est possible de résoudre localement dans un réseau, c’est-à-dire les problèmes pour lesquels les processus impliqués dans le calcul peuvent générer leurs sorties après avoir consulté uniquement les entrées des processus proches dans le réseau. Plus spécifiquement, le modèle considéré suppose qu’une étape permet à chaque processus d’échanger des messages avec ses voisins dans le réseau, et d’effectuer un calcul individuel. L’exposé s’attachera à répondre à des questions telles que : qu’est-il possible de calculer en un nombre constant d’étapes, de façon déterministe ou probabiliste ? Qu’est-il possible de calculer en un nombre faible d’étapes, par exemple O(polylog n), voire O(log∗ n) étapes ? L’exposé s’attachera également à l’étude de problèmes de bris de symétrie tels que la coloration distribuée ou le calcul distribué d’un ensemble indépendant maximal, en présentant l’état de l’art des meilleures bornes supérieures et inférieures connues pour ces problèmes, pour des algorithmes déterministes aussi bien que pour des algorithmes probabilistes.

Damien Woods

Evaluating a large class of Boolean circuits via algorithmic self-assembly of DNA strands

This talk will cover our recent theoretical and experimental work on designing and implementing a set of 356 self-assembling DNA strands, or single-stranded tiles, that implement any one of 2^44 6-bit Boolean circuits. The programmer first specifies a 6-bit input string encoded in a cylindrical-shaped DNA origami seed structure, then chooses a subset of 89 or more DNA tiles so that they begin attaching to the seed, self-assembling into a cylindrical nanotube lattice that evaluates a Boolean function as it grows. We show that this algorithmic growth process implements any one of a suite computations, such as bit copying, bit sorting, telling if an input string is a palindrome or represents a multiple of three in binary, randomised algorithms, cute patterns, leader election, and even simulation of the Turing-universal cellular automaton Rule 110. We implement a total of 20 such circuits in the wet-lab. This work represents a significant increase in the complexity and generality of algorithmic self-assembly systems that have been experimentally demonstrated to date.
Joint work with David Doty, Cameron Myhrvold, Felix Zhou, Joy Hui, Peng Yin and Erik Winfree.


Au LaBRI

Le LaBRI est une unité de recherche associée au CNRS (UMR 5800), à l'Université de Bordeaux et à Bordeaux INP. Depuis 2002, il est partenaire de l'Inria.

Comment y venir ?
Où se loger ?

Liste des participants
 

# Prénom Nom Institut
1 Mathieu Raffinot LaBRI
2 Nicolas Schabanel CNRS - U. Paris Diderot
3 Florent Becker LIFO - Université d'Orléans
4 David Ilcinkas LaBRI - CNRS & Univ. Bordeaux
5 Julien Fradin LINA - Université de Nantes
6 Mamadou M. KANTé Université Clermont Auvergne, LIMOS, CNRS
7 Claire Mathieu CNRS, École normale supérieure
8 Brieuc Guinard IRIF
9 Ralf Klasing CNRS, LaBRI, Université de Bordeaux
10 Kim Thang Nguyen IBISC, Université d'Evry
11 Jean-Florent Raymond LIRMM (Montpellier) et Université de Varsovie
12 Frederic Magniez IRIF
13 chien-chung Huang CNRS, École normale supérieure
14 Lucas Boczkowski Université Paris Diderot
15 Frederik Mallmann-Trenn ENS
16 Alkida Balliu CNRS and Univ Paris 7, GSSI L'Aquila
17 Dennis Olivetti CNRS and Univ Paris 7, GSSI L'Aquila
18 Simon Collet IRIF
19 Cyril Gavoille LaBRI, Université de Bordeaux
20 Guillaume Blin LaBRI, Université de Bordeaux
21 Damien Woods INRIA
22 Tatiana Starikovskaya IRIF, l'Université Paris-Diderot
23 Pierre Fraigniaud IRIF
24 Damien Woods INRIA
25 Christoph Dürr UPMC, LIP6
26 Akka Zemmari LaBRI, Université de Bordeaux - CNRS
27 Paul Dorbec U-bordeaux-CNRS
28 Colette Johnen LaBRI
29 Arnaud Casteigts LaBRI
30 Bruno Courcelle Labri
31 Raluca Uricaru UB
32 Ghazal Kachigar IMB
33 corentin travers LaBRI
34 Nicolas Bonichon LaBRI - U Bordeaux
35 Paul OUVRARD Université de Bordeaux
36 Yves Métivier LaBRI
37 Alessia Milani LaBRI
38 Jérôme leroux LaBRI
39 Sofian Maabout INS2I
40 Yvan Le Borgne CNRS, LaBRI
41 nicolas hanusse CNRS - Bordeaux - LaBRI

Inscrivez vous ici !