Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author James I. Lathrop:

TR08-035 | 18th February 2008
James I. Lathrop, Jack H. Lutz, Scott M. Summers

Strict Self-Assembly of Discrete Sierpinski Triangles

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>>

TR08-031 | 14th January 2008
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

Computability and Complexity in Self-Assembly

This paper explores the impact of geometry on computability =
and complexity in
Winfree's model of nanoscale self-assembly. We work in the =
tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =
main theorem says that there is a roughly quadratic function f ... more >>>

ISSN 1433-8092 | Imprint