Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Aaron Koch

dblp:250/9160 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
0since 2021 · last 2020
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Computer architecture, parallel and distributed computing, and storage systems
1 paper
Emerging computing paradigms · 100%
Theoretical computer science
1 paper
Algorithms and data structures · 100%

Topics — the 3 heaviest of 3, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Emerging computing paradigms
molecular computing
0.412020
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model · SODA 2020
Emerging computing paradigms › molecular computing › algorithmic self-assembly
tile assembly model
0.412020
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model · SODA 2020
Algorithms and data structures
self-assembly
0.412020
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model · SODA 2020

Methods — techniques the papers use, named apart from their topics

simulation · 0.9
YearPublicationVenuePosition
2020 The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model
abstract
In this paper we present a series of results related to mathematical models of self-assembling systems of tiles and the impacts that three diverse properties have on their dynamics. In these self-assembling systems, initially unorganized collections of tiles undergo random motion and can bind together, if they collide and enough of their incident glues match, to form assemblies. Here we greatly expand upon a series of prior results which showed that (1) the abstract Tile Assembly Model (aTAM) is intrinsically universal (FOCS 2012), and (2) the class of directed aTAM systems is not intrinsically universal (FOCS 2016). Intrinsic universality (IU) for a model (or class of systems within a model) means that there is a universal tile set which can be used to simulate an arbitrary system within that model (or class). Furthermore, the simulation must not only produce the same resultant structures, it must also maintain the full dynamics of the systems being simulated and display the same behaviors modulo a scale factor. While the FOCS 2012 result showed that the standard, two-dimensional (2D) aTAM is IU, here we show that this is also the case for the three-dimensional (3D) version. Conversely, the FOCS 2016 result showed that the class of aTAM systems which are directed (a.k.a. deterministic, or confluent) is not IU, meaning that there is no universal simulator which can simulate directed aTAM systems while itself always remaining directed, implying that nondeterminism is fundamentally required for such simulations. Here, however, we show that, in 3D, the class of directed aTAM systems is actually IU, i.e. there is a universal directed simulator for them. This implies that the constraint of tiles binding only in the plane forced the necessity of nondeterminism for the simulation of 2D directed systems. This then leads us to continue to explore the impacts of dimensionality and directedness on simulation of tile-based self-assembling systems by considering the influence of more rigid notions of dimensionality. Namely, we introduce the Planar aTAM, where tiles are not only restricted to binding in the plane, but they are also restricted to traveling within the plane, and we prove that the Planar aTAM is not IU, and prove that the class of directed systems within the Planar aTAM also is not IU. Finally, analogous to the Planar aTAM, we introduce the Spatial aTAM, its 3D counterpart, and prove that the Spatial aTAM is IU. This paper adds to a broad set of results which have been used to classify and compare the relative powers of differing models and classes of self-assembling systems, and also helps to further the understanding of the roles of dimension and nondeterminism on the dynamics of self-assembling systems. Furthermore, to prove our positive results we have not only designed, but also implemented what we believe to be the first IU tile set ever implemented and simulated in any tile assembly model, and have made it, along with a simulator which can demonstrate it, freely available.
Daniel Hader, Aaron Koch, Matthew J. Patitz, Michael Sharp
SODA2