RSRobert T. Schweller

Robert T. Schweller

*This is an algorithmically generated author record based on publicly available information.

Robert T. Schweller has a total of 24 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Fast arithmetic in algorithmic self-assembly

    by Alexandra Keenan, Robert Schweller, Michael Sherman, Xingsi Zhong


  • Open Access

    Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability

    by Sándor P. Fekete, Robert T. Schweller, Andrew Winslow

    We introduce a new model of algorithmic tile self-assembly called size-dependent assembly. In previous models, supertiles are stable when the total strength of the bonds between any two halves exceeds some constant temperature. In this model, this constant temperature requirement is replaced by an nondecreasing temperature function $\tau : \mathbb{N} \rightarrow \mathbb{N}$ that depends on the size of the smaller of the two halves. This generalization allows supertiles to become unstable and break apart, and captures the increased forces that large structures may place on the bonds holding them together. We demonstrate the power of this model in two ways. First, we give fixed tile sets that assemble constant-height rectangles and squares of arbitrary input size given an appropriate temperature function. Second, we prove that deciding whether a supertile is stable is coNP-complete. Both results contrast with known results for fixed temperature.

  • Strict Self-Assembly of Fractals Using Multiple Hands

    by Cameron T. Chalk, Dominic A. Fernandez, Alejandro Huerta, Mario A. Maldonado, Robert T. Schweller, Leslie Sweet


  • The Two-Handed Tile Assembly Model is not Intrinsically Universal

    by Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods


  • Open Access

    The two-handed tile assembly model is not intrinsically universal

    by Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods

    The well-studied Two-Handed Tile Assembly Model (2HAM) is a model of tile assembly in which pairs of large assemblies can bind, or self-assemble, together. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature $\tau$, where $\tau$ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal, in other words we ask: is there a single universal 2HAM tile set $U$ which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all $\tau' < \tau$, each temperature-$\tau'$ 2HAM tile system does not simulate at least one temperature-$\tau$ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal, in stark contrast to the simpler (single-tile addition only) abstract Tile Assembly Model which is intrinsically universal ("The tile assembly model is intrinsically universal", FOCS 2012). However, on the positive side, we prove that, for every fixed temperature $\tau \geq 2$, temperature-$\tau$ 2HAM tile systems are indeed intrinsically universal: in other words, for each $\tau$ there is a single universal 2HAM tile set $U$ that, when appropriately initialized, is capable of simulating the behavior of any temperature-$\tau$ 2HAM tile system. As a corollary of these results we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each $\tau$, there is a temperature-$\tau$ 2HAM system that simultaneously simulates all temperature-$\tau$ 2HAM systems.

  • Open Access

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

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

    In this paper we explore the power of geometry to overcome the limitations of non-cooperative self-assembly. We define a generalization of the abstract Tile Assembly Model (aTAM), such that a tile system consists of a collection of polyomino tiles, the Polyomino Tile Assembly Model (polyTAM), and investigate the computational powers of polyTAM systems at temperature 1, where attachment among tiles occurs without glue cooperation. Systems composed of the unit-square tiles of the aTAM at temperature 1 are believed to be incapable of Turing universal computation (while cooperative systems, with temperature > 1, are able). As our main result, we prove that for any polyomino $P$ of size 3 or greater, there exists a temperature-1 polyTAM system containing only shape-$P$ tiles that is computationally universal. Our proof leverages the geometric properties of these larger (relative to the aTAM) tiles and their abilities to effectively utilize geometric blocking of particular growth paths of assemblies, while allowing others to complete. To round out our main result, we provide strong evidence that size-1 (i.e. aTAM tiles) and size-2 polyomino systems are unlikely to be computationally universal by showing that such systems are incapable of geometric bit-reading, which is a technique common to all currently known temperature-1 computationally universal systems. We further show that larger polyominoes with a limited number of binding positions are unlikely to be computationally universal, as they are only as powerful as temperature-1 aTAM systems. Finally, we connect our work with other work on domino self-assembly to show that temperature-1 assembly with at least 2 distinct shapes, regardless of the shapes or their sizes, allows for universal computation.

  • Exponential replication of patterns in the signal tile assembly model

    by Alexandra Keenan, Robert Schweller, Xingsi Zhong


  • One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile

    by Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods


  • Open Access

    Fast Arithmetic in Algorithmic Self-Assembly

    by Alexandra Keenan, Robert Schweller, Michael Sherman, Xingsi Zhong

    In this paper we consider the time complexity of computing the sum and product of two $n$-bit numbers within the tile self-assembly model. The (abstract) tile assembly model is a mathematical model of self-assembly in which system components are square tiles with different glue types assigned to tile edges. Assembly is driven by the attachment of singleton tiles to a growing seed assembly when the net force of glue attraction for a tile exceeds some fixed threshold. Within this frame work, we examine the time complexity of computing the sum or product of 2 n-bit numbers, where the input numbers are encoded in an initial seed assembly, and the output is encoded in the final, terminal assembly of the system. We show that the problems of addition and multiplication have worst case lower bounds of $\Omega(\sqrt{n})$ in 2D assembly, and $\Omega(\sqrt[3]{n})$ in 3D assembly. In the case of addition, we design algorithms for both 2D and 3D that meet this bound with worst case run times of $O(\sqrt{n})$ and $O(\sqrt[3]{n})$ respectively, which beats the previous best known upper bound of O(n). Further, we consider average case complexity of addition over uniformly distributed n-bit strings and show how to achieve $O(\log n)$ average case time with a simultaneous $O(\sqrt{n})$ worst case run time in 2D. For multiplication, we present an $O(n^{5/6})$ time multiplication algorithm which works in 3D, which beats the previous best known upper bound of O(n). As additional evidence for the speed of our algorithms, we implement our addition algorithms, along with the simpler O(n) time addition algorithm, into a probabilistic run-time simulator and compare the timing results.

  • Open Access

    One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece

    by Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods

    In this paper we explore the power of tile self-assembly models that extend the well-studied abstract Tile Assembly Model (aTAM) by permitting tiles of shapes beyond unit squares. Our main result shows the surprising fact that any aTAM system, consisting of many different tile types, can be simulated by a single tile type of a general shape. As a consequence, we obtain a single universal tile type of a single (constant-size) shape that serves as a "universal tile machine": the single universal tile type can simulate any desired aTAM system when given a single seed assembly that encodes the desired aTAM system. We also show how to adapt this result to convert any of a variety of plane tiling systems (such as Wang tiles) into a "nearly" plane tiling system with a single tile (but with small gaps between the tiles). All of these results rely on the ability to both rotate and translate tiles; by contrast, we show that a single nonrotatable tile, of arbitrary shape, can produce assemblies which either grow infinitely or cannot grow at all, implying drastically limited computational power. On the positive side, we show how to simulate arbitrary cellular automata for a limited number of steps using a single nonrotatable tile and a linear-size seed assembly.