The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Running time and program size for self-assembled squares
Abstract
Recently Rothemund and Winfree [6] have considered the program size complexity of constructing squares by self-assembly. Here, we consider the time complexity of such constructions using a natural generalization of the Tile Assembly Model defined in [6]. In the generalized model, the Rothemund-Winfree construction of n \times n squares requires time Θ(n log n) and program size Θ(log n). We present a new construction for assembling n \times n squares which uses optimal time Θ(n) and program size Θ(\frac{log n}{log log n}). This program size is also optimal since it matches the bound dictated by Kolmogorov complexity. Our improved time is achieved by demonstrating a set of tiles for parallel self-assembly of binary counters. Our improved program size is achieved by demonstrating that self-assembling systems can compute changes in the base representation of numbers. Self-assembly is emerging as a useful paradigm for computation. In addition the development of a computational theory of self-assembly promises to provide a new conduit by which results and methods of theoretical computer science might be applied to problems of interest in biology and the physical sciences.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Design and self-assembly of two-dimensional DNA crystals
Winfree, E., Liu, F., Wenzler, L. A., & Seeman, N. C. (1998) · Nature · doi:10.1038/28998 · Cited by 2,857
Logical computation using algorithmic self-assembly of DNA triple-crossover molecules
Mao, C., LaBean, T. H., Reif, J. H., & Seeman, N. C. (2000) · Nature · doi:10.1038/35035038 · Cited by 779 · cited 1×
“Recently, work related to DNA computation has led to experimental systems for the investigation of self-assembly and its relation to computation [8, 5, 3, 2].”
Background
Cited by
Algorithmic Self-Assembly of DNA Sierpinski Triangles
Rothemund, P. W. K., Papadakis, N., & Winfree, E. (2004) · PLoS Biology · doi:10.1371/journal.pbio.0020424 · Cited by 860
Parker, L. E., Rus, D., & Sukhatme, G. S. (2016) · Springer Handbooks · doi:10.1007/978-3-319-32552-1_53 · Cited by 290
An information-bearing seed for nucleating algorithmic self-assembly
Barish, R. D., Schulman, R., Rothemund, P. W. K., & Winfree, E. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0808736106 · Cited by 267
Metadata
- Authors
- Adleman, L., Cheng, Q., Goel, A., & Huang, M.-D.
- Venue
- Proceedings of the thirty-third annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2001-07-06
- Pages
- 740-748
- OpenAlex
- W1981863124
- Cited by
- 233
- References
- 2
- FWCI
- 7.16
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Running time and program size for self-assembled squares. https://app.cochat.ai/papers/10.1145/380752.380881
- The paper
- Adleman, L., Cheng, Q., Goel, A., & Huang, M.-D. (2001). Running time and program size for self-assembled squares. Proceedings of the thirty-third annual ACM symposium on Theory of computing. https://doi.org/10.1145/380752.380881
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.