LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème

**Liste des [ inscrit-e-s ]**

**Shortcuts: [ Mercredi 12:30-17:45 | Jeudi 9:00-18:30 | Vendredi 9:20-13:30 | PDF ]**

**Videos: [ All videos playlist ]**

**12:30-13:30 Buffet repas chaud et froid**

**13:30-13:40 Ouverture des journées**

**13:45-14:45 - Exposé invité n°1 : Damien WOODS (Caltech, professeur invité au LIAFA)
[ Video:
A
B
]
**

**Intrinsic universality and the computational power of self-assembly**

*Our story is set in the world of algorithmic self-assembly, where small unit-sized tiles stick together to form large complicated structures. This kind of self-assembly is best described as an asynchronous and distributed computational process. We regale the forging of a powerful tool, simulation. We tell of its wielding by brave adventurers to classify and separate the computational and expressive power of self-assembly models.
Our journey begins with the result that there is a single intrinsically universal tile set, that with proper initialization and scaling, simulates any tile assembly system. This intrinsically universal tile set exhibits something stronger than Turing universality: it directly simulates the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchical model, where large assemblies can bind together in one step, we encounter an infinite set, of infinite hierarchies, with strictly increasing simulation power. Towards the end of our adventure, we find one tile to rule them all: a single rotatable, flipable, polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.*

**14:50-15:30 - Evangelos BAMPAS (LaBRI, U. Bordeaux) - Improved Periodic Data Retrieval in Asynchronous Rings with a Faulty Host**

In this work, we present the first nontrivial lower bounds on the number of agents for Periodic Data Retrieval in asynchronous ring networks. Specifically, we show that at least 4 agents are needed when the malicious host is a gray hole, and at least 5 agents are needed when the malicious host whiteboard is unreliable. This improves the previous lower bound of 3 in both cases and answers an open question posed in the aforementioned paper. On the positive side, we propose an optimal protocol for Periodic Data Re- trieval in asynchronous rings with a gray hole, which solves the problem with only 4 agents. This improves the previous upper bound of 9 agents and settles the question of the optimal number of agents in the gray-hole case. Finally, we propose a protocol with 7 agents when the whiteboard of the malicious host is unreliable, significantly improving the previously known upper bound of 27 agents. Along the way, we set forth a detailed framework for studying networks with malicious hosts of varying capabilities.

Joint work with Nikos Leonardos, Euripides Markou, Aris Pagourtzis, and Matoula Petrolia.

**15:30-16:00 Café**

**16:00-17:00 - Exposé invité n°2 : Florent BECKER (LIFO)
[
Video
]
**

**You Look Funny when you Simulate:
The Price of Intrinsic Universality in Self-Assembly**

*Self-assembly is a tile-based model of natural computation, which is notably not totally unlike what can be implemented using DNA. It has been known to be Turing Complete for a long time, but recent works by Patitz, Meunier, Woods and others have brought forward and studied the notions of internal simulation of self-assembly (simulating self-assembly systems by other self-assembly systems) and intrinsic universality. Yet, simulator constructions tend to exhibit peculiar behaviours such as using mismatches between tiles in order to implement locking of critical sections. Is this complexity necessary?
In this talk, I will present some classes of behavior for self-assembly systems, and show that they are actually separated, and which of them have a complete system. In doing so, we will explore the tools for a detailed look into the dynamics of self-assembly systems: Turing complexity, but also the less familiar bisimilarity lemma and cutspaces.*

**17:05-17:45 - Nathanaël FRANÇOIS (LIAFA - Université Paris Diderot) -
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting**

Joint work with Frédéric Magniez (LIAFA) and Rahul Jain (National University of Singapore).

**9:00-9:40 - Shinnosuke SEKI (U. Aalto) - DNA pattern-assembly: introduction and recent breakthroughs**
[
Video
]

**9:45-10:45 - Exposé invité n°3 : Laurent VUILLON (LAMA)
[
Video
]
**

**From tilings to fibers: bio-mathematical aspects of fold plasticity**

*Protein oligomers are made by the association of protein chains via intermolecular amino acid interactions (interaction between subunits) forming so called protein interfaces. This talk proposes mathematical concepts to investigate the shape constraints on the protein interfaces in order to promote oligomerization. First, we focus on tiling the plane (2 dimensions) by translation with abstract shapes. Using the fundamental Theorem of Beauquier-Nivat, we show that the shapes of the tiles must be either like a square or like a hexagon to tile the whole plane. Second, we look in more details at the tiling of a cylinder and discuss its relevancy in constructing protein fibers. The universality of such “building” properties are investigated through biological examples.*

**10:45-11:15 Café**

**11:15-11:55 - Bernadette CHARRON-BOST (LIX) - Les algorithmes naturels
[
Video
]
**

Je présenterai plus en détail ce nouveau domaine de recherche et discuterai de ce que peut recouvrir un tel programme de travail autour des notions fondamentales que sont le Con- sensus, la synchronisation et la tolérance aux défaillances. J’exposerai différents éléments de calcul algorithmique récemment proposés pour l’analyse des algorithmes naturels et qui mettent en jeu des techniques classiques en Systèmes Dynamiques, en théorie des chaines de Markov ou encore en théorie spectrale des graphes.

**12:00-13:25 Buffet repas chaud et froid**

**13:30-14:30 - Exposé invité n°4 : Claire LESIEUR (AGIM) **

**Robust and systemic amino acids in self-assembled proteins**

*Proteins are biological entities made of a chain of amino acids bound to one another in a specific sequence. Based on the sequence and the environment, the protein acquires a tridimensional shape suitable for its biological function. In addition, to be functional most proteins assemble several copies of their chains.
Proteins combine robustness and plasticity to local perturbation, i.e. modification of a single amino acid (mutation). The individual mutation of most of the amino acids of a protein does not change the protein function and /or shape. Yet, the individual mutation of some targeted amino acids, produces enough changes to modify the structure (fold plasticity/allostery) and/or the function (innovability). Such observation suggests that some amino acids transfer information globally while others do not.
How to distinguish the two types? Experimental approaches are feasible but empirical, case by case and time consuming. On the other hand, the science of networks is very well suited to investigate local to global communication in a network. It is possible to model a protein as a network of amino acids in interactions, and in the last decade such approaches have improved the understanding of protein dynamics.
Here we explore network measures that might distinguish the amino acids central to the network communication/controllability.*

**14:35-15:15 - Damien REGNAULT (Université d'Evry Val d'Essonne) - Lost in Self-Stabilization**

One of the questions addressed here is "How can a twisted thread correct itself?". We consider a theoretical model where the studied mathematical object represents a 2D twisted discrete thread linking two points. This thread is made of a chain of agents which are lost, i.e. they have no knowledge of the global setting and no sense of direction. Thus, the modifications made by the agents are local and all the decisions use only minimal information about the local neighborhood. We introduce a random process such that the thread reorganizes itself efficiently to become a discrete line between these two points. The second question addressed here is to reorder a word by local flips in order to scatter the letters to avoid long successions of the same letter. These two questions are equivalent. The work presented here is at the crossroad of many different domains such as modeling cooling process in crystallography, stochastic cellular automata, organizing a line of robots in distributed algorithms (the robot chain problem), and Christoffel words in language theory.

**15:15-15:45 Café**

**15:45-16:45 - Exposé invité n°5 : Pierre-Étienne MEUNIER (U. Aalto)
[
Video
]
**

**Non-cooperative self-assembly : A geometric pumping lemma**

*L'auto-assemblage est le mécanisme par lequel des entités atomiques se composent pour former de grandes molécules complexes. Un modèle de ce phénomène est dérivé des tuiles de Wang : on représente les molécules élémentaires par des tuiles, qui viennent s'assembler à une structure existante suivant une condition de couleurs sur les côtés des tuiles.
Le modèle non-coopératif de l'auto-assemblage est un modèle où cette condition est très faible : les tuiles peuvent s'assembler dès lors qu'au moins un des côtés est de la bonne couleur. Malgré la simplicité de sa définition, c'est l'un des modèles les moins bien compris d'auto-assemblage.
Les résultats présentés dans cet exposé montreront l'existence de constructions algorithmiques efficaces, un résultat qui a longtemps été cru impossible. Malgré ces constructions, nous verrons aussi pourquoi ce modèle ne peut pas faire de calcul Turing arbitraires (en deux dimensions), alors que sa variante en trois dimensions en est capable.*

**16:50-17:50 - Exposé invité n°6 : André ESTÉVEZ-TORRES (LPN)
[ Video:
A
B
]
**

**Programming reaction-diffusion spatio-temporal patterns with DNA**

*The generation of macroscopic spatiotemporal order in a system of microscopic objects is a fundamental question with important implications in biological morphogenesis. Self-assembly and self-organization are two fundamental processes that contribute to the emergence of such order, in particular in molecular systems. I will first review some examples of these two processes and make a distinction between the two, with an emphasis in nucleic acids. I will then introduce an experimental set of highly programmable synthetic chemical reaction networks based on DNA. Finally, I will show that this set of reactions is particularly advantageous for studying spatio-temporal chemical self-organization.*

**17:55-18:30 - Open session**

**9:20-10:00 - Zvi LOTKER (B.G,U) - Homophily and the Glass Ceiling Effect in Social Networks**

**10:00-10:30 Café**

**10:30-11:30 - Exposé invité n°7 : Andrew WINSLOW (U. Libre de Bruxelles)
[ Video:
A
B
]
**

**The Limits of a Simple Model of Active Self-Assembly**

*Many models of self-assembly, including Winfree's abstract tile assembly model, carry out crystallization-like processes where particles attach to the growing frontier of a rigid structure. These models have been shown to be capable of efficient, flexible, and universal forms of growth, and are often capable of not only universal computation, but forms of universal behavior. Despite this power, these systems have a drawback: the assembly process is slow. The limited frontier of growth on the static or passive structures, implies that assemblies grow only polynomially fast.
Polynomial growth may not seem slow, except that some naturally occurring systems, including some stages of embryo development, demonstrate exponential growth! Such quick growth is made possible by an active structure that reconfigures to allow the addition of new particles throughout the structure. Dabby and Chen (2013) introduced a simple formal model of active self-assembly, implementable in DNA, exhibiting exponential growth. In their model, a linear polymer grows by the insertion of new particles between consecutive existing particles in the polymer according to simple rules.
We develop tight bounds on the speed, size, and complexity of polymers constructable by these active insertion-based systems of Dabby and Chen. Both upper and lower bounds are proved, including a surprising tradeoff between constructing faster and fewer polymers.
Joint work with Benjamin Hescott and Caleb Malchik.*

**11:35-12:15 - Carola DOERR (CNRS, LIP6) - Theory of Bio-Inspired Optimization **

Understanding RSH from a theoretical point of view has become a research topic of increasing interest. While most research in this area focuses on computing the running times of RSH, a meaningful complexity theory is yet to be developed. A common notion for the latter are variants of the classical query complexity. In this talk, I will briefly survey existing complexity models. I will also show how insights from these models have inspired the design of new crossover-based genetic algorithms that are provably faster on some problems than any purely mutation-based algorithm.

12:15-13:30 - Conclusion des journées par un Vins et fromages