CS 789 THEORY SEMINAR [home]

Speaker:  David Kempe   
Affiliation: Computer Science, Cornell University
Date: Monday, April 29, 2002
Title: An introduction to self-assembly

Abstract: 

Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. Recent experimental activity includes self-assembly of macro-scale plastic tiles and nano-scale multi-stranded DNA motifs which show great promise despite the presence of experimental difficulties. Most recently, Bell Labs has announced the construction of the world's first molecular-thickness transistor by self-assembly.

In order to analyze self-assembly in a clean model, Rothemund&Winfree proposed the Tile Assembly Model, building upon the idea of Wang tiles. In this model, uniform-sized square tiles are designed with "glues" on their sides that let them bond to other tiles. The designer of a tile system determines the interaction strengths between the various types of glue, and designs types of tiles by prescribing the glues on the sides. Each tile type is assumed to exist in very large (practically infinite) numbers.

The set of tile types can be considered as a program, and the process of self-assembly as a (potentially non-deterministic) computation, resulting upon termination in an assembly, which is the output. Hence, this defines an alternate model of computation. In this model, the number of distinct tile types can be considered as an analogue of space complexity, and there is a natural definition for time complexity based on the relative concentrations of tile types.

One can ask many interesting algorithmic questions about this new model of computation, such as: Does a given tile system (uniquely) produce a desired assembly? What is the minimum number of tile types needed to produce a given assembly? How should we choose concentrations to achieve minimum assembly time? What is the complexity of the previous questions? Etc.

In this talk, I will give an introduction to the model, and answer some of the above questions. The results presented are mostly from the following three papers:

P. Rothemund, E. Winfree: The program-size complexity of self-assembled squares. STOC 2000

L. Adleman, Q. Cheng, A. Goel, M. Huang: Running time and program size for self-assembled squares. STOC 2001

L. Adleman, Q. Cheng, A. Goel, M. Huang, D. Kempe, P. Moisset, P. Rothemund:
Combinatorial Optimization Problems in Self-Assembly. STOC 2002