Search Results

Documents authored by Luchsinger, Austin

Document
DOI: 10.4230/LIPIcs.DNA.29.9
Optimal Information Encoding in Chemical Reaction Networks

Authors: Austin Luchsinger, David Doty, and David Soloveichik

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities. While for Turing-universal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count x ∈ ℕ with probability 1 is asymptotically equal to a "space-aware" version of the Kolmogorov complexity of x, defined as K̃s(x) = min_p {|p|/log|p| + log(space(𝒰(p))) : 𝒰(p) = x}, where p is a program for universal Turing machine 𝒰. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating x, but also the space usage of that program. Probability 1 computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they "know when they are done" in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any b bits of information via O(b/log{b}) reactions, which is information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization can be encoded - in the sense of generating precise molecular counts of species as the desired state.
Cite as

Austin Luchsinger, David Doty, and David Soloveichik. Optimal Information Encoding in Chemical Reaction Networks. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{luchsinger_et_al:LIPIcs.DNA.29.9,
  author =	{Luchsinger, Austin and Doty, David and Soloveichik, David},
  title =	{{Optimal Information Encoding in Chemical Reaction Networks}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.9},
  URN =		{urn:nbn:de:0030-drops-187920},
  doi =		{10.4230/LIPIcs.DNA.29.9},
  annote =	{Keywords: chemical reaction networks, Kolmogorov complexity, stable computation}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2022.24
Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete

Authors: Austin Luchsinger

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Chemical and molecular systems exist in a world between kinetics and thermodynamics. Engineers of such systems often design them to perform computation solely by following particular kinetic pathways. That is, just like silicon computation, these systems are intentionally designed to run contrary to the natural thermodynamic driving forces of the system. The thermodynamic binding networks (TBN) model is a relatively new model that is particularly well-equipped to investigate this dichotomy between kinetics and thermodynamics. The kinetic TBN model uses reconfiguration energy barriers to inform kinetic pathways. This work shows that deciding if two TBN configurations have a barrier-1 pathway between them is PSPACE-complete. This result comes via a reduction from nondeterministic constraint logic (NCL).
Cite as

Austin Luchsinger. Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 24:1-24:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{luchsinger:LIPIcs.SAND.2022.24,
  author =	{Luchsinger, Austin},
  title =	{{Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{24:1--24:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.24},
  URN =		{urn:nbn:de:0030-drops-159664},
  doi =		{10.4230/LIPIcs.SAND.2022.24},
  annote =	{Keywords: Thermodynamic Binding Networks, Nondeterministic Constraint Logic, NP-complete, PSPACE-complete}
}
Document
DOI: 10.4230/LIPIcs.DNA.27.7
Molecular Machines from Topological Linkages

Authors: Keenan Breik, Austin Luchsinger, and David Soloveichik

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

Abstract
Life is built upon amazingly sophisticated molecular machines whose behavior combines mechanical and chemical action. Engineering of similarly complex nanoscale devices from first principles remains an as yet unrealized goal of bioengineering. In this paper we formalize a simple model of mechanical motion (mechanical linkages) combined with chemical bonding. The model has a natural implementation using DNA with double-stranded rigid links, and single-stranded flexible joints and binding sites. Surprisingly, we show that much of the complex behavior is preserved in an idealized topological model which considers solely the graph connectivity of the linkages. We show a number of artifacts including Boolean logic, catalysts, a fueled motor, and chemo-mechanical coupling, all of which can be understood and reasoned about in the topological model. The variety of achieved behaviors supports the use of topological chemical linkages in understanding and engineering complex molecular behaviors.
Cite as

Keenan Breik, Austin Luchsinger, and David Soloveichik. Molecular Machines from Topological Linkages. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{breik_et_al:LIPIcs.DNA.27.7,
  author =	{Breik, Keenan and Luchsinger, Austin and Soloveichik, David},
  title =	{{Molecular Machines from Topological Linkages}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.7},
  URN =		{urn:nbn:de:0030-drops-146749},
  doi =		{10.4230/LIPIcs.DNA.27.7},
  annote =	{Keywords: chemical computation, mechanical computation, bioengineering, models of biochemistry, molecular machines, mechanical linkages, generic rigidity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.53
Signal Passing Self-Assembly Simulates Tile Automata

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

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
The natural process of self-assembly has been studied through various abstract models due to the abundant applications that benefit from self-assembly. Many of these different models emerged in an effort to capture and understand the fundamental properties of different physical systems and the mechanisms by which assembly may occur. A newly proposed model, known as Tile Automata, offers an abstract toolkit to analyze and compare the algorithmic properties of different self-assembly systems. In this paper, we show that for every Tile Automata system, there exists a Signal-passing Tile Assembly system that can simulate it. Finally, we connect our result with a recent discovery showing that Tile Automata can simulate Amoebot programmable matter systems, thus showing that the Signal-passing Tile Assembly can simulate any Amoebot system.
Cite as

Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. Signal Passing Self-Assembly Simulates Tile Automata. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cantu_et_al:LIPIcs.ISAAC.2020.53,
  author =	{Cantu, Angel A. and Luchsinger, Austin and Schweller, Robert and Wylie, Tim},
  title =	{{Signal Passing Self-Assembly Simulates Tile Automata}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.53},
  URN =		{urn:nbn:de:0030-drops-133978},
  doi =		{10.4230/LIPIcs.ISAAC.2020.53},
  annote =	{Keywords: self-assembly, signal-passing tile assembly model, tile automata, cellular automata, simulation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.31
Covert Computation in Self-Assembled Circuits

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

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

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.
Cite as

Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. Covert Computation in Self-Assembled Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cantu_et_al:LIPIcs.ICALP.2019.31,
  author =	{Cantu, Angel A. and Luchsinger, Austin and Schweller, Robert and Wylie, Tim},
  title =	{{Covert Computation in Self-Assembled Circuits}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.31},
  URN =		{urn:nbn:de:0030-drops-106075},
  doi =		{10.4230/LIPIcs.ICALP.2019.31},
  annote =	{Keywords: self-assembly, covert circuits}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.14
Self-Assembly of Any Shape with Constant Tile Types using High Temperature

Authors: Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Inspired by nature and motivated by a lack of top-down tools for precise nanoscale manufacture, self-assembly is a bottom-up process where simple, unorganized components autonomously combine to form larger more complex structures. Such systems hide rich algorithmic properties - notably, Turing universality - and a self-assembly system can be seen as both the object to be manufactured as well as the machine controlling the manufacturing process. Thus, a benchmark problem in self-assembly is the unique assembly of shapes: to design a set of simple agents which, based on aggregation rules and random movement, self-assemble into a particular shape and nothing else. We use a popular model of self-assembly, the 2-handed or hierarchical tile assembly model, and allow the existence of repulsive forces, which is a well-studied variant. The technique utilizes a finely-tuned temperature (the minimum required affinity required for aggregation of separate complexes). We show that calibrating the temperature and the strength of the aggregation between the tiles, one can encode the shape to be assembled without increasing the number of distinct tile types. Precisely, we show one tile set for which the following holds: for any finite connected shape S, there exists a setting of binding strengths between tiles and a temperature under which the system uniquely assembles S at some scale factor. Our tile system only uses one repulsive glue type and the system is growth-only (it produces no unstable assemblies). The best previous unique shape assembly results in tile assembly models use O(K(S)/(log K(S))) distinct tile types, where K(S) is the Kolmogorov (descriptional) complexity of the shape S.
Cite as

Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie. Self-Assembly of Any Shape with Constant Tile Types using High Temperature. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chalk_et_al:LIPIcs.ESA.2018.14,
  author =	{Chalk, Cameron and Luchsinger, Austin and Schweller, Robert and Wylie, Tim},
  title =	{{Self-Assembly of Any Shape with Constant Tile Types using High Temperature}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.14},
  URN =		{urn:nbn:de:0030-drops-94773},
  doi =		{10.4230/LIPIcs.ESA.2018.14},
  annote =	{Keywords: self-assembly, molecular computing, tiling, tile, shapes}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact