Paper accepted to ICALP

Our paper “Covert Computation in Self-Assembled Circuits” was accepted to the 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19), which is a top tier conference. The authors on the paper are Angel Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. For more information about the paper, visit the post.

Covert Computation in Self-Assembled Circuits

Title: Covert Computation in Self-Assembled Circuits

Authors: Angel Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie

Abstract:

Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography.

In this paper we propose the problem of performing “covert computation” within tile self-assembly that seeks to design self-assembly systems that “conceal” both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract tile assembly model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.

 

Citation: Proc. of the 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19).

Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

Title: Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

Authors: Robert Schweller, Andrew Winslow, and Tim Wylie

Abstract:

Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information.

In particular, for all $n \in \mathbb{N}$, we assemble $n \times n$ squares using $O(2^{\log^*{n}})$ tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with $O(2^{\log^*{K}})$ tiles, where $K$ denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct $n \times O(1)$ rectangles using only $O(\log{n}/\log\log{n})$ tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature.

These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.

Citation: Algorithmica, 2019

Single-Step Shape Constructors

Here are some videos from our latest single-step work!

3X3 K-Colored Shape

3X3 K-Colored Pattern

4X4 K-Colored Pattern

4X4 K-Colored Shape

 

Spring semester

Xtreme algorithms will be starting back up today (1/24) and will be every Thursday at 3. Today will be a talk by Austin Luchsinger where he’ll go over the paper he presented at the ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) on January 9th. We will continue to keep the Xtreme page up to date.

As is true with every semester, our group changes. We also say goodbye to Andrew Winslow, who has taken a job at Google, and to David Dittman, who graduated in December. Good luck! Joining our group is Michael Alaniz and Eden Canales. Welcome!

Finally, we had a journal version of a conference paper from UCNC last year accepted.

HackR Proceedings

The HackR hackathon was a lot of fun and had some really great results. The proceedings are now online here. Thanks to everyone for a great event!