[CoA 2014] Andrew Winslow (A/B)

Troisièmes journées du GT CoA Complexité et Algorithmes : Algorithmes naturels
du mercredi 10 septembre 12h30 au vendredi 12 septembre 13h30, Université Paris Diderot
LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème

10:30-11:30 - Exposé invité n°7 : Andrew WINSLOW (U. Libre de Bruxelles)
The Limits of a Simple Model of Active Self-Assembly [A/B]

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.