## Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

Title: Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

Authors: Robert Schweller, Andrew Winslow, and Tim Wylie

Journal: Algorithmica, 2019

Abstract:

Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information.

In particular, for all $n \in \mathbb{N}$, we assemble $n \times n$ squares using $O(2^{\log^*{n}})$ tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with $O(2^{\log^*{K}})$ tiles, where $K$ denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct $n \times O(1)$ rectangles using only $O(\log{n}/\log\log{n})$ tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature.

These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.

## Optimal Staged Self-Assembly of General Shapes

Title: Optimal Staged Self-Assembly of General Shapes
Authors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
Abstract:
We analyze the number of tile types t, bins b, and stages necessary to assemble $$n \times n$$ squares and scaled shapes in the staged tile assembly model. For $$n \times n$$ squares, we prove $$\mathcal {O}\left( \frac{\log {n} – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}\right)$$ stages suffice and $$\varOmega \left( \frac{\log {n} – tb – t\log t}{b^2}\right)$$ are necessary for almost all n. For shapes S with Kolmogorov complexity K(S), we prove $$\mathcal {O}\left( \frac{K(S) – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}\right)$$ stages suffice and $$\varOmega \left( \frac{K(S) – tb – t\log t}{b^2}\right)$$ are necessary to assemble a scaled version of S, for almost all S. We obtain similarly tight bounds when the more powerful flexible glues are permitted.
Published: Arxiv, European Symposium on Algorithms (ESA’16), Algorithmica

Journal Citation: Algorithmica, 80(4), 1383-1409, 2018.

Bibtex:
@article{CMSVWW:2018:Algorithmica,
author=”Chalk, Cameron and Martinez, Eric and Schweller, Robert and Vega, Luis and Winslow, Andrew and Wylie, Tim”,
title=”Optimal Staged Self-Assembly of General Shapes”,
journal=”Algorithmica”,
year=”2018″,
month=”Apr”,
day=”01″,
volume=”80″,
number=”4″,
pages=”1383–1409″,
issn=”1432-0541″,
doi=”10.1007/s00453-017-0318-0″,
url=”https://doi.org/10.1007/s00453-017-0318-0″
}

Conference Citation: Proceedings of the 24th European Symposium of Algorithms (ESA’16), 57, 26:1–26:17, 2016.