Robert Schweller

TCS Journal 2025 Journal Article

Reachability in restricted chemical reaction networks

• Robert M. Alaniz
• Bin Fu
• Timothy Gomez
• Elise Grizzell
• Andrew Rodriguez
• Marco Rodriguez
• Robert Schweller
• Tim Wylie

The popularity of molecular computation has given rise to several models of abstraction, one of the more recent ones being Chemical Reaction Networks (CRNs). These are equivalent to other popular computational models, such as Vector Addition Systems and Petri-Nets, and restricted versions are equivalent to Population Protocols. This paper continues the work on core reachability questions related to Chemical Reaction Networks; given two configurations, can one reach the other according to the system's rules? With no restrictions, reachability was recently shown to be Ackermann-complete, which resolved a decades-old problem. In this work, we fully characterize monotone reachability problems based on various restrictions such as the allowed rule size, the number of rules that may create a species (k-source), the number of rules that may consume a species (k-consuming), the volume, and whether the rules have an acyclic production order (feed-forward). We show PSPACE-completeness of reachability with only bimolecular reactions in two-source and two-consuming rules. This proves hardness of reachability in a restricted form of Population Protocols. This is accomplished using new techniques within the motion planning framework. We give several important results for feed-forward CRNs, where rules are single-source or single-consuming. We show that reachability is solvable in polynomial time as long as the system does not contain special void or autogenesis rules. We then fully characterize all systems of this type and show that with void/autogenesis rules, or more than one source and one consuming, the problems become NP-complete. Finally, we show several interesting special cases of CRNs based on these restrictions or slight relaxations and note future significant open questions related to this taxonomy.

TCS Journal 2021 Journal Article

On the effects of hierarchical self-assembly for reducing program-size complexity

• Sarah Cannon
• Erik D. Demaine
• Martin L. Demaine
• Sarah Eisenstat
• David Furcy
• Matthew J. Patitz
• Robert Schweller
• Scott M. Summers

In this paper we present a series of results which show separations between the standard seeded model of self-assembly, Winfree's abstract Tile Assembly Model (aTAM), and the “seedless” 2-Handed Assembly Model (2HAM), which incorporates the dynamics of hierarchical self-assembly. In particular, we focus on the problem of self-assembling various shapes while minimizing the sizes of tile sets, or “programs”, in each of these models in order to compare and contrast the models. A high-level overview of a subset of these results was presented in a paper by the authors in STACS 2013, but in this version we expand and improve the set of results related to showing separations between the two models according to their abilities to self-assemble various shapes. We exhibit classes of finite shapes that can be self-assembled more efficiently in each model. We also demonstrate infinite shapes that can self-assemble in one model but not in the other, as well as a shape which cannot self-assemble in either model.

SODA Conference 2020 Conference Paper

Hierarchical Shape Construction and Complexity for Slidable Polyominoes under Uniform External Forces

• Jose Balanza-Martinez
• Timothy Gomez
• David Caballero
• Austin Luchsinger
• Angel A. Cantu
• Rene Reyes
• Mauricio Flores
• Robert Schweller

Advances in technology have given us the ability to create and manipulate robots for numerous applications at the molecular scale. At this size, fabrication tool limitations motivate the use of simple robots. The individual control of these simple objects can be infeasible. We investigate a model of robot motion planning, based on global external signals, known as the tilt model. Given a board and initial placement of polyominoes, the board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. We propose a new hierarchy of shapes and design a single configuration that is strongly universal for any w × h bounded shape within this hierarchy (it can be reconfigured to construct any w × h bounded shape in the hierarchy). This class of shapes constitutes the most general set of buildable shapes in the literature, with most previous work consisting of just the first-level of our hierarchy. We accompany this result with a O ( n 4 log n )-time algorithm for deciding if a given hole-free shape is a member of the hierarchy. For our second result, we resolve a long-standing open problem within the field: We show that deciding if a given position may be covered by a tile for a given initial board configuration is PSPACEcomplete, even when all movable pieces are 1 × 1 tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game.

SODA Conference 2019 Conference Paper

Full Tilt: Universal Constructors for General Shapes with Uniform External Forces

• Jose Balanza-Martinez
• Austin Luchsinger
• David Caballero
• Rene Reyes
• Angel A. Cantu
• Robert Schweller
• Luis Angel Garcia
• Tim Wylie

We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. In this model, corresponding particles may bond when adjacent with one another. Succinctly, this model considers a 2D grid of “open” and “blocked” spaces, along with a set of slidable polyominoes placed at open locations on the board. The board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. By successively applying a sequence of such tilts, along with allowing different polyominoes to stick when adjacent, tilt sequences provide a method to reconfigure an initial board configuration so as to assemble a collection of previous separate polyominoes into a larger shape. While previous work within this model of assembly has focused on designing a specific board configuration for the assembly of a specific given shape, we propose the problem of designing universal configurations that are capable of constructing a large class of shapes and patterns. For these constructions, we present the notions of weak and strong universality which indicate the presence of “excess” polyominoes after the shape is constructed. In particular, for given integers h, w, we show that there exists a weakly universal configuration with O ( hw ) 1 × 1 slidable particles that can be reconfigured to build any h × w patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any h × w -bounded size connected shape. Following these results, which require an admittedly relaxed assembly definition, we go on to show the existence of a strongly universal configuration (no excess particles) which can assemble any shape within a previously studied “drop” class, while using quadratically less space than previous results. Finally, we include a study of the complexity of deciding if a particle within a configuration may be relocated to another position, and deciding if a given configuration may be transformed into a second given configuration. We show both problems to be PSPACE-complete even when no particles stick to one another and movable particles are restricted to 1 × 1 tiles and a single 2 × 2 polyomino.

TCS Journal 2017 Journal Article

Concentration independent random number generation in tile self-assembly

• Cameron T. Chalk
• Bin Fu
• Eric Martinez
• Robert Schweller
• Tim Wylie

In this paper we introduce the robust random number generation problem where the goal is to design an abstract tile assembly system (aTAM system) whose terminal assemblies can be split into n partitions such that a resulting assembly of the system lies within each partition with probability 1/n, regardless of the relative concentration assignment of the tile types in the system. First, we show this is possible for n = 2 (a robust fair coin flip) within the aTAM, and that such systems guarantee a worst case O ( 1 ) space usage. We accompany our primary construction with variants that show trade-offs in space complexity, initial seed size, temperature, tile complexity, bias, and extensibility, and also prove some negative results. As an application, we combine our coin-flip system with a result of Chandran, Gopalkrishnan, and Reif to show that for any positive integer n, there exists a O ( log ⁡ n ) tile system that assembles a constant-width linear assembly of expected length n for any concentration assignment. We then extend our robust fair coin flip result to solve the problem of robust random number generation in the aTAM for all n. Two variants of robust random bit generation solutions are presented: an unbounded space solution and a bounded space solution which incurs a small bias. Further, we consider the harder scenario where tile concentrations change arbitrarily at each assembly step and show that while this is not possible in the aTAM, the problem can be solved by exotic tile assembly models from the literature.

SODA Conference 2017 Conference Paper

Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces

• Cameron T. Chalk
• Erik D. Demaine
• Martin L. Demaine
• Eric Martinez
• Robert Schweller
• Luis Vega
• Tim Wylie

We show how to design a universal shape replicator in a self- assembly system with both attractive and repulsive forces. More precisely, we show that there is a universal set of constant-size objects that, when added to any unknown holefree polyomino shape, produces an unbounded number of copies of that shape (plus constant-size garbage objects). The constant-size objects can be easily constructed from a constant number of individual tile types using a constant number of preprocessing self-assembly steps. Our construction uses the well-studied 2-Handed Assembly Model (2HAM) of tile self-assembly, in the simple model where glues interact only with identical glues, allowing glue strengths that are either positive (attractive) or negative (repulsive), and constant temperature (required glue strength for parts to hold together). We also require that the given shape has specified glue types on its surface, and that the feature size (smallest distance between nonincident edges) is bounded below by a constant. Shape replication necessarily requires a self-assembly model where parts can both attach and detach, and this construction is the first to do so using the natural model of negative/repulsive glues (also studied before for other problems such as fuel-efficient computation); previous replication constructions require more powerful global operations such as an “enzyme” that destroys a subset of the tile types.

SODA Conference 2015 Conference Paper

Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly

• Sándor P. Fekete
• Jacob Hendricks
• Matthew J. Patitz
• Trent A. Rogers
• Robert Schweller

SODA Conference 2013 Conference Paper

Fuel Efficient Computation in Passive Self-Assembly

• Robert Schweller
• Michael Sherman

In this paper we show that passive self-assembly in the context of the tile self-assembly model is capable of performing fuel efficient, universal computation. The tile self-assembly model is a premiere model of self-assembly in which particles are modeled by four-sided squares with glue types assigned to each tile edge. The assembly process is driven by positive and negative force interactions between glue types, allowing for tile assemblies floating in the plane to combine and break apart over time. We refer to this type of assembly model as passive in that the constituent parts remain unchanged throughout the assembly process regardless of their interactions. A computationally universal system is said to be fuel efficient if the number of tiles used up per computation step is bounded by a constant. Work within this model has shown how fuel guzzling tile systems can perform universal computation with only positive strength glue interactions [33]. Recent work has introduced space-efficient, fuel-guzzling universal computation with the addition of negative glue interactions and the use of a powerful non-diagonal class of glue interactions [20]. Other recent work has shown how to achieve fuel efficient computation [28] within active tile self-assembly. In this paper we utilize negative interactions in the tile self-assembly model to achieve the first computationally universal passive tile self-assembly system that is both space and fuel-efficient. In addition, we achieve this result using a limited diagonal class of glue interactions.

TCS Journal 2013 Journal Article

On testing monomials in multivariate polynomials

• Zhixiang Chen
• Bin Fu
• Yang Liu
• Robert Schweller

This paper presents a summary of our initial work on developing a theory of testing monomials in multivariate polynomials. The central question is to ask whether a polynomial represented by certain economically compact structure has a multilinear monomial in its sum-product expansion. The complexity aspects of this problem and its variants are investigated with two objectives. One is to understand how this problem relates to critical problems in complexity, and if so to what extent. The other is to exploit possibilities of applying algebraic properties of polynomials to the study of those problems. A series of results about Π Σ Π and Π Σ polynomials is obtained in this paper, laying a basis for further study along this line. Several randomized and deterministic algorithms are devised for testing multilinear monomials or p -monomials in certain respective types of polynomials, where p is prime.

FOCS Conference 2012 Conference Paper

The Tile Assembly Model is Intrinsically Universal

• David Doty
• Jack H. Lutz
• Matthew J. Patitz
• Robert Schweller
• Scott M. Summers
• Damien Woods

We prove that the abstract Tile Assembly Model (aTAM) of nanoscale self-assembly is intrinsically universal. This means that there is a single tile assembly system U that, with proper initialization, simulates any tile assembly system T. The simulation is "intrinsic" in the sense that the self-assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m × m "super tile" of U. Our construction works for the full aTAM at any temperature, and it faithfully simulates the deterministic or nondeterministic behavior of each T. Our construction succeeds by solving an analog of the cell differentiation problem in developmental biology: Each super tile of U, starting with those in the seed assembly, carries the "genome" of the simulated system T. At each location of a potential super tile in the self-assembly of U, a decision is made whether and how to express this genome, i. e. , whether to generate a super tile and, if so, which tile of T it will represent. This decision must be achieved using asynchronous communication under incomplete information, but it achieves the correct global outcome(s).

SODA Conference 2011 Conference Paper

Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D

• Matthew Cook 0001
• Yunhui Fu
• Robert Schweller

SODA Conference 2010 Conference Paper

Shape Replication through Self-Assembly and RNase Enzymes

• Zachary Abel
• Nadia M. Benbernou
• Mirela Damian
• Erik D. Demaine
• Martin L. Demaine
• Robin Y. Flatland
• Scott Duke Kominers
• Robert Schweller

We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only O (1) distinct tile types and O (1) stages. Further, we show how to replicate precisely n copies of a shape using O (log n ) stages and O (1) tile types.

FOCS Conference 2010 Conference Paper

Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature

• David Doty
• Matthew J. Patitz
• Dustin Reishus
• Robert Schweller
• Scott M. Summers

We consider the problem of fault-tolerance in nanoscale algorithmic self-assembly. We employ a standard variant of Winfree's abstract Tile Assembly Model (aTAM), the two-handed aTAM, in which square “tiles” - a model of molecules constructed from DNA for the purpose of engineering self-assembled nanostructures - aggregate according to specific binding sites of varying strengths, and in which large aggregations of tiles may attach to each other, in contrast to the seeded aTAM, in which tiles aggregate one at a time to a single specially designated “seed” assembly. We focus on a major cause of errors in tile-based self-assembly: that of unintended growth due to “weak” strength-1 bonds, which if allowed to persist, may be stabilized by subsequent attachment of neighboring tiles in the sense that at least energy 2 is now required to break apart the resulting assembly, i. e. , the errant assembly is stable at temperature 2. We study a common self-assembly benchmark problem, that of assembling an n×n square using O(log n) unique tile types, under the two-handed model of self-assembly. Our main result achieves a much stronger notion of fault-tolerance than those achieved previously. Arbitrary strength-1 growth is allowed, however, any assembly that grows sufficiently to become stable at temperature 2 is guaranteed to assemble into the correct final assembly of an n×n square. In other words, errors due to insufficient attachment, which is the cause of errors studied in earlier papers on fault-tolerance, are prevented absolutely in our main construction, rather than only with high probability and for sufficiently small structures, as in previous fault tolerance studies.

SODA Conference 2006 Conference Paper

Reducing tile complexity for self-assembly through temperature programming

• Ming-Yang Kao
• Robert Schweller

SODA Conference 2004 Conference Paper

Complexities for generalized models of self-assembly

• Gagan Aggarwal
• Michael H. Goldwasser
• Ming-Yang Kao
• Robert Schweller