The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
The program-size complexity of self-assembled squares (extended abstract)
Abstract
Molecular self-assembly gives rise to a great diversityofcomplex forms, from crystals and DNA helices to microtubules and holoenzymes. We study a formal model of pseudocrystalline self-assembly, called the Tile Assembly Model, in which atilemay be added to the growing object when the total interaction strength with its neighbors exceeds a parameter T. This model has been shown to be Turinguniversal. Thus, self-assembled objects can be studied from the point of view of computational complexity. Here, we dene the program size complexity ofanNN square to be the minimum number of distinct tiles required to self-assemble the square and no other objects. We study this complexity under the Tile Assembly Model and nd a dramatic decrease in complexity, from N 2 tiles to O(log N) tiles,asT is increased from 1 (where bonding is noncooperative) to 2 (allowing cooperative bonding). Further, we nd that the size of the largest square uniquely produced by a set of n tiles grows faster than any computable function. 1.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Metallic Phase with Long-Range Orientational Order and No Translational Symmetry
Shechtman, D., Blech, I., Gratias, D., & Cahn, J. W. (1984) · Physical Review Letters · doi:10.1103/physrevlett.53.1951 · Cited by 7,060
Molecular Computation of Solutions to Combinatorial Problems
Adleman, L. M. (1994) · Science · doi:10.1126/science.7973651 · Cited by 4,474
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (2019) · Texts in Computer Science · doi:10.1007/978-3-030-11298-1 · Cited by 3,681
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
Self-citationThe thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0 · Cited by 1,775
Proving Theorems by Pattern Recognition - II
Wang, H. (1961) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1961.tb03975.x · Cited by 862
Undecidability and nonperiodicity for tilings of the plane
Robinson, R. M. (1971) · Inventiones mathematicae · doi:10.1007/bf01418780 · Cited by 697
(1995) · Cited by 678
Self-Assembly of Mesoscale Objects into Ordered Two-Dimensional Arrays
Bowden, N., Terfort, A., Carbeck, J., & Whitesides, G. M. (1997) · Science · doi:10.1126/science.276.5310.233 · Cited by 660
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
Self-citationDesign and Characterization of Programmable DNA Nanotubes
Rothemund, P. W. K., Ekani-Nkodo, A., Papadakis, N., Kumar, A., Fygenson, D. K., & Winfree, E. (2004) · Journal of the American Chemical Society · doi:10.1021/ja044319l · Cited by 512
Self-citationDiverse and robust molecular algorithms using reprogrammable DNA self-assembly
Woods, D., Doty, D., Myhrvold, C., Hui, J., Zhou, F., Yin, P., & Winfree, E. (2019) · Nature · doi:10.1038/s41586-019-1014-9 · Cited by 295
Self-citation
Metadata
- Authors
- Rothemund, P. W. K., & Winfree, E.
- Venue
- Proceedings of the thirty-second annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2000-05
- Pages
- 459-468
- OpenAlex
- W1983241546
- Cited by
- 407
- References
- 23
- FWCI
- 10.74
- 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: The program-size complexity of self-assembled squares (extended abstract). https://app.cochat.ai/papers/10.1145/335305.335358
- The paper
- Rothemund, P. W. K., & Winfree, E. (2000). The program-size complexity of self-assembled squares (extended abstract). Proceedings of the thirty-second annual ACM symposium on Theory of computing. https://doi.org/10.1145/335305.335358
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.