du mercredi 10 septembre 12h30 au vendredi 12 septembre 13h30, Université Paris Diderot
LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème
[ Plan d'accès ]
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 ]
Mercredi 10 septembre 2014 - 12:30-17:45
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) ![[web]](hyperlien20.png){kind=small}
[ 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
The problem of exploration of a network by a team of mobile agents has been extensively studied in unsafe networks containing malicious hosts of a highly harmful nature, called black holes, which completely destroy mobile agents that visit them. In a recent work, Královič and Miklík [SIROCCO 2010, LNCS 6058, pp. 157–167] considered various types of malicious host behavior in the context of the Periodic Data Retrieval problem in asynchronous ring networks with exactly one malicious host. In this problem, a team of initially co-located agents must report data from all safe nodes of the network to the homebase, infinitely often. The malicious host can choose whether to kill visiting agents or allow them to pass through (gray hole). In another variation of the model, the malicious host can, in addition, alter its whiteboard contents in order to deceive visiting agents. The goal is to design a protocol for Periodic Data Retrieval using as few agents as possible.
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
We consider unidirectional data streams with restricted access, such as
read-only and write-only streams. For read-write streams, we also
introduce a new complexity measure called expansion, the ratio between
the space used on the stream and the input size.
We give tight bounds for the complexity of reversing a stream of length
n in several of the
possible models. In the read-only and write-only model, we show that
p-pass algorithms need
memory space Θ(n/p). But if either the output stream or the input stream
is read-write, then
the complexity falls to Θ(n/p^2). It becomes logarithmic if p = O(log n)
and both streams are
read-write.
We also study the complexity of sorting a stream and give two algorithms
with small expan-
sion. Our main sorting algorithm is randomized and has O(1) expansion,
O(log n) passes and
O(log n) memory.
Joint work with Frédéric Magniez (LIAFA) and Rahul Jain (National University of Singapore).
Jeudi 11 septembre 2014 - 9:00-18:30
9:00-9:40 - Shinnosuke SEKI (U. Aalto) - DNA pattern-assembly: introduction and recent breakthroughs
[
Video
]
Self-assembly is a process through which disorganized, relatively simple
components autonomously coalesce according to local rules to form more complex
target structures, in the absence of orders from an external global conductor.
DNA self-assembly can produce various nanoscale structures experimentally,
including regular arrays, fractal structures, smiley faces, logic circuits, and
molecular robots. In particular, pattern-assembly aims at allocating molecular
components on a 2D-array according to a given layout called pattern. A
long-standing open problem (PATS) is about the complexity of optimizing the
design of DNA self-assembly system that self-assembles a given pattern. In this
talk, an overview is given about DNA pattern-assembly, a mathematical model for
that, and PATS. Recent breakthroughs on PATS are also reported, including a
computer-assisted proof for the open problem.
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
]
Les algorithmes constituent un langage très expressif pour modéliser les systèmes biologiques ou physiques et les phénomènes de synchronisation et de coordination que l’on peut observer au sein de ces systèmes multi-agents. Cette expression algorithmique permet non seulement d’effectuer des simulations numériques mais aussi et surtout fournit un cadre très puissant pour l’analyse de ces systèmes naturels. Ainsi, on peut légitimement envisager que, pour les sciences du vivant, les algorithmes naturels jouent un rôle analogue à celui des équations différentielles en Physique. Pour conforter cette analogie, il faudrait développer un calcul algorithmique qui serait aux sciences du vivant ce que le calcul différentiel est à la Physique.
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
Joint work with Éric Rémila.
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
Vendredi 12 septembre 2014 - 9:20-13:30
9:20-10:00 - Zvi LOTKER (B.G,U) - Homophily and the Glass Ceiling Effect in Social Networks
The glass ceiling effect, preventing women and minorities from reaching
the highest levels of success in society, is a disturbing social phenomenon
whose causes and operation are not fully understood.
This paper studies the glass ceiling effect in the context of social networks and analyzes
a natural mathematical model that provides a possible mechanism
for the creation of this effect.
Using such modeling can help to identify and understand possible causes that contribute to
the glass ceiling effect, and in turn, help to come up with policies for alleviating it and reducing its severity.
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
Randomized search heuristics (RSH) like simulated annealing, evolutionary algorithms, or randomized hill climbers form a large class of general-purpose optimization algorithms. They have various industrial applications, and can be found in many solvers for real-world optimization problems.
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