Watch Pierre-Etienne's video presentation for the STOC 2020 conference to learn about our mathematical result proving that long self-assembled paths are 'pumpable' in the so-called non-cooperative model of self-assembly:

Pierre-Etienne Meunier, Damien Regnault, Damien Woods
The program-size complexity of self-assembled paths.
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp 727--737.

What's it all about? In the theory of algorithmic self-assembly, the main idea is to use a small number of molecules to build large complicated structures. This is where algorithms come in: if we can embed algorithms into molecules, we can have the molecules do crazy complicated stuff, in super-efficient ways, just like computers do. In particular, this methodology allows a few kinds of molecules (with many copies of each kind) to come together and build large complex structures. Our most abstract mathematical models consider molecules to be unit-sized square tiles that stick together on the discrete square lattice; like tiles on a bathroom wall. The hope is to use this clean mathematical setting to eventually say something about what is and is not possible with real molecules, such as those made of DNA, and to learn about the interaction of geometry and computation in an asynchronous system.

The simpler the model, the easier it is to think about. Not always. The simplest model considered by researchers in the field is the noncooperative abstract tile assembly model. Molecules are square-shaped tiles, where each square side has a colour, and a tile sticks to a growing structure if one of its sides' colours matches a colour at the edge of the structure at the moment of sticking. Our team's new result shows that if we build a large enough structure in this way, then one eventually gets pumpable 'junk': infinitely long repeated paths. There's no way to avoid it. This formally justifies the long-held intuition (since 2000, see here, and here) that the noncooperative model is too simple to be useful.

STOC 2020 is the 52nd Annual ACM SIGACT Symposium on Theory of Computing, and along with FOCS, is one of the two premier conferences in theoretical computer science. The paper is perhaps one of the juiciest of the fruits of a many-year journey by the authors, spanning multiple previous papers, countries, and academic institutions. Congrats to Pierre-Étienne and Damien Regnault!

The short conference publication is here, and the full version with all proofs and details is freely available on the arXiv.