10 Search Results for "Soloveichik, David"


Document
Minimum Free Energy, Partition Function and Kinetics Simulation Algorithms for a Multistranded Scaffolded DNA Computer

Authors: Ahmed Shalaby, Chris Thachuk, and Damien Woods

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


Abstract
Polynomial time dynamic programming algorithms play a crucial role in the design, analysis and engineering of nucleic acid systems including DNA computers and DNA/RNA nanostructures. However, in complex multistranded or pseudoknotted systems, computing the minimum free energy (MFE), and partition function of nucleic acid systems is NP-hard. Despite this, multistranded and/or pseudoknotted systems represent some of the most utilised and successful systems in the field. This leaves open the tempting possibility that many of the kinds of multistranded and/or pseudoknotted systems we wish to engineer actually fall into restricted classes, that do in fact have polynomial time algorithms, but we've just not found them yet. Here, we give polynomial time algorithms for MFE and partition function calculation for a restricted kind of multistranded system called the 1D scaffolded DNA computer. This model of computation thermodynamically favours correct outputs over erroneous states, simulates finite state machines in 1D and Boolean circuits in 2D, and is amenable to DNA storage applications. In an effort to begin to ask the question of whether we can naturally compare the expressivity of nucleic acid systems based on the computational complexity of prediction of their preferred energetic states, we show our MFE problem is in logspace (the complexity class L), making it perhaps one of the simplest known, natural, nucleic acid MFE problems. Finally, we provide a stochastic kinetic simulator for the 1D scaffolded DNA computer and evaluate strategies for efficiently speeding up this thermodynamically favourable system in a constant-temperature kinetic regime.

Cite as

Ahmed Shalaby, Chris Thachuk, and Damien Woods. Minimum Free Energy, Partition Function and Kinetics Simulation Algorithms for a Multistranded Scaffolded DNA Computer. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{shalaby_et_al:LIPIcs.DNA.29.1,
  author =	{Shalaby, Ahmed and Thachuk, Chris and Woods, Damien},
  title =	{{Minimum Free Energy, Partition Function and Kinetics Simulation Algorithms for a Multistranded Scaffolded DNA Computer}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{1:1--1:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.1},
  URN =		{urn:nbn:de:0030-drops-187840},
  doi =		{10.4230/LIPIcs.DNA.29.1},
  annote =	{Keywords: thermodynamic computation, model of computation, molecular computing, minimum free energy, partition function, DNA computing, DNA self-assembly, DNA strand displacement, kinetics simulation}
}
Document
Thermodynamically Driven Signal Amplification

Authors: Joshua Petrack, David Soloveichik, and David Doty

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


Abstract
The field of chemical computation attempts to model computational behavior that arises when molecules, typically nucleic acids, are mixed together. By modeling this physical phenomenon at different levels of specificity, different operative computational behavior is observed. Thermodynamic binding networks (TBNs) is a highly abstracted model that focuses on which molecules are bound to each other in a "thermodynamically stable" sense. Stability is measured based only on how many bonds are formed and how many total complexes are in a configuration, without focusing on how molecules are binding or how they became bound. By defocusing on kinetic processes, TBNs attempt to naturally model the long-term behavior of a mixture (i.e., its thermodynamic equilibrium). We study the problem of signal amplification: detecting a small quantity of some molecule and amplifying its signal to something more easily detectable. This problem has natural applications such as disease diagnosis. By focusing on thermodynamically favored outcomes, we seek to design chemical systems that perform the task of signal amplification robustly without relying on kinetic pathways that can be error prone and require highly controlled conditions (e.g., PCR amplification). It might appear that a small change in concentrations can result in only small changes to the thermodynamic equilibrium of a molecular system. However, we show that it is possible to design a TBN that can "exponentially amplify" a signal represented by a single copy of a monomer called the analyte: this TBN has exactly one stable state before adding the analyte and exactly one stable state afterward, and those two states "look very different" from each other. In particular, their difference is exponential in the number of types of molecules and their sizes. The system can be programmed to any desired level of resilience to false positives and false negatives. To prove these results, we introduce new concepts to the TBN model, particularly the notions of a TBN’s entropy gap to describe how unlikely it is to be observed in an undesirable state, and feed-forward TBNs that have a strong upper bound on the number of polymers in a stable configuration. We also show a corresponding negative result: a doubly exponential upper bound, meaning that there is no TBN that can amplify a signal by an amount more than doubly exponential in the number and sizes of different molecules that comprise it. We leave as an open question to close this gap by either proving an exponential upper bound, or giving a construction with a doubly-exponential difference between the stable configurations before and after the analyte is added. Our work informs the fundamental question of how a thermodynamic equilibrium can change as a result of a small change to the system (adding a single molecule copy). While exponential amplification is traditionally viewed as inherently a non-equilibrium phenomenon, we find that in a strong sense exponential amplification can occur at thermodynamic equilibrium as well - where the "effect" (e.g., fluorescence) is exponential in types and complexity of the chemical components.

Cite as

Joshua Petrack, David Soloveichik, and David Doty. Thermodynamically Driven Signal Amplification. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{petrack_et_al:LIPIcs.DNA.29.8,
  author =	{Petrack, Joshua and Soloveichik, David and Doty, David},
  title =	{{Thermodynamically Driven Signal Amplification}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{8:1--8:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.8},
  URN =		{urn:nbn:de:0030-drops-187917},
  doi =		{10.4230/LIPIcs.DNA.29.8},
  annote =	{Keywords: Thermodynamic binding networks, signal amplification, integer programming}
}
Document
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-dev.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
Track A: Algorithms, Complexity and Games
Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Authors: Paul Beame and Niels Kornerup

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
Cumulative memory - the sum of space used per step over the duration of a computation - is a fine-grained measure of time-space complexity that was introduced to analyze cryptographic applications like password hashing. It is a more accurate cost measure for algorithms that have infrequent spikes in memory usage and are run in environments such as cloud computing that allow dynamic allocation and de-allocation of resources during execution, or when many multiple instances of an algorithm are interleaved in parallel. We prove the first lower bounds on cumulative memory complexity for both sequential classical computation and quantum circuits. Moreover, we develop general paradigms for bounding cumulative memory complexity inspired by the standard paradigms for proving time-space tradeoff lower bounds that can only lower bound the maximum space used during an execution. The resulting lower bounds on cumulative memory that we obtain are just as strong as the best time-space tradeoff lower bounds, which are very often known to be tight. Although previous results for pebbling and random oracle models have yielded time-space tradeoff lower bounds larger than the cumulative memory complexity, our results show that in general computational models such separations cannot follow from known lower bound techniques and are not true for many functions. Among many possible applications of our general methods, we show that any classical sorting algorithm with success probability at least 1/poly(n) requires cumulative memory ̃ Ω(n²), any classical matrix multiplication algorithm requires cumulative memory Ω(n⁶/T), any quantum sorting circuit requires cumulative memory Ω(n³/T), and any quantum circuit that finds k disjoint collisions in a random function requires cumulative memory Ω(k³n/T²).

Cite as

Paul Beame and Niels Kornerup. Cumulative Memory Lower Bounds for Randomized and Quantum Computation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{beame_et_al:LIPIcs.ICALP.2023.17,
  author =	{Beame, Paul and Kornerup, Niels},
  title =	{{Cumulative Memory Lower Bounds for Randomized and Quantum Computation}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.17},
  URN =		{urn:nbn:de:0030-drops-180694},
  doi =		{10.4230/LIPIcs.ICALP.2023.17},
  annote =	{Keywords: Cumulative memory complexity, time-space tradeoffs, branching programs, quantum lower bounds}
}
Document
Simulating 3-Symbol Turing Machines with SIMD||DNA

Authors: David Doty and Aaron Ong

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


Abstract
SIMD||DNA [Wang et al., 2019] is a model of DNA strand displacement allowing parallel in-memory computation on DNA storage. We show how to simulate an arbitrary 3-symbol space-bounded Turing machine with a SIMD||DNA program, giving a more direct and efficient route to general-purpose information manipulation on DNA storage than the Rule 110 simulation of Wang, Chalk, and Soloveichik [Wang et al., 2019]. We also develop software (https://github.com/UC-Davis-molecular-computing/simd-dna) that can simulate SIMD||DNA programs and produce SVG figures.

Cite as

David Doty and Aaron Ong. Simulating 3-Symbol Turing Machines with SIMD||DNA. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.SAND.2022.14,
  author =	{Doty, David and Ong, Aaron},
  title =	{{Simulating 3-Symbol Turing Machines with SIMD||DNA}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{14:1--14:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.14},
  URN =		{urn:nbn:de:0030-drops-159568},
  doi =		{10.4230/LIPIcs.SAND.2022.14},
  annote =	{Keywords: DNA storage, strand displacement, parallel computation}
}
Document
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-dev.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
Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching

Authors: Tonglin Chen, Arnav Solanki, and Marc Riedel

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


Abstract
Prior research has introduced the Single-Instruction-Multiple-Data paradigm for DNA computing (SIMD DNA). It offers the potential for storing information and performing in-memory computations on DNA, with massive parallelism. This paper introduces three new SIMD DNA operations: sorting, shifting, and searching. Each is a fundamental operation in computer science. Our implementations demonstrate the effectiveness of parallel pairwise operations with this new paradigm.

Cite as

Tonglin Chen, Arnav Solanki, and Marc Riedel. Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.DNA.27.11,
  author =	{Chen, Tonglin and Solanki, Arnav and Riedel, Marc},
  title =	{{Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{11:1--11:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.11},
  URN =		{urn:nbn:de:0030-drops-146780},
  doi =		{10.4230/LIPIcs.DNA.27.11},
  annote =	{Keywords: Molecular Computing, DNA Computing, DNA Storage, Parallel Computing, Strand Displacement}
}
Document
CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks

Authors: Marko Vasic, David Soloveichik, and Sarfraz Khurshid

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)


Abstract
Formal methods have enabled breakthroughs in many fields, such as in hardware verification, machine learning and biological systems. The key object of interest in systems biology, synthetic biology, and molecular programming is chemical reaction networks (CRNs) which formalizes coupled chemical reactions in a well-mixed solution. CRNs are pivotal for our understanding of biological regulatory and metabolic networks, as well as for programming engineered molecular behavior. Although it is clear that small CRNs are capable of complex dynamics and computational behavior, it remains difficult to explore the space of CRNs in search for desired functionality. We use Alloy, a tool for expressing structural constraints and behavior in software systems, to enumerate CRNs with declaratively specified properties. We show how this framework can enumerate CRNs with a variety of structural constraints including biologically motivated catalytic networks and metabolic networks, and seesaw networks motivated by DNA nanotechnology. We also use the framework to explore analog function computation in rate-independent CRNs. By computing the desired output value with stoichiometry rather than with reaction rates (in the sense that X → Y+Y computes multiplication by 2), such CRNs are completely robust to the choice of reaction rates or rate law. We find the smallest CRNs computing the max, minmax, abs and ReLU (rectified linear unit) functions in a natural subclass of rate-independent CRNs where rate-independence follows from structural network properties.

Cite as

Marko Vasic, David Soloveichik, and Sarfraz Khurshid. CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 4:1-4:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{vasic_et_al:LIPIcs.DNA.2020.4,
  author =	{Vasic, Marko and Soloveichik, David and Khurshid, Sarfraz},
  title =	{{CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{4:1--4:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.4},
  URN =		{urn:nbn:de:0030-drops-129574},
  doi =		{10.4230/LIPIcs.DNA.2020.4},
  annote =	{Keywords: molecular programming, formal methods}
}
Document
Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols

Authors: Amanda Belleville, David Doty, and David Soloveichik

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
Population protocols are a distributed computing model appropriate for describing massive numbers of agents with very limited computational power (finite automata in this paper), such as sensor networks or programmable chemical reaction networks in synthetic biology. A population protocol is said to require a leader if every valid initial configuration contains a single agent in a special "leader" state that helps to coordinate the computation. Although the class of predicates and functions computable with probability 1 (stable computation) is the same whether a leader is required or not (semilinear functions and predicates), it is not known whether a leader is necessary for fast computation. Due to the large number of agents n (synthetic molecular systems routinely have trillions of molecules), efficient population protocols are generally defined as those computing in polylogarithmic in n (parallel) time. We consider population protocols that start in leaderless initial configurations, and the computation is regarded finished when the population protocol reaches a configuration from which a different output is no longer reachable. In this setting we show that a wide class of functions and predicates computable by population protocols are not efficiently computable (they require at least linear time), nor are some linear functions even efficiently approximable. It requires at least linear time for a population protocol even to approximate division by a constant or subtraction (or any linear function with a coefficient outside of N), in the sense that for sufficiently small gamma > 0, the output of a sublinear time protocol can stabilize outside the interval f(m) (1 +/- gamma) on infinitely many inputs m. In a complementary positive result, we show that with a sufficiently large value of gamma, a population protocol can approximate any linear f with nonnegative rational coefficients, within approximation factor gamma, in O(log n) time. We also show that it requires linear time to exactly compute a wide range of semilinear functions (e.g., f(m)=m if m is even and 2m if m is odd) and predicates (e.g., parity, equality).

Cite as

Amanda Belleville, David Doty, and David Soloveichik. Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{belleville_et_al:LIPIcs.ICALP.2017.141,
  author =	{Belleville, Amanda and Doty, David and Soloveichik, David},
  title =	{{Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{141:1--141:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.141},
  URN =		{urn:nbn:de:0030-drops-75044},
  doi =		{10.4230/LIPIcs.ICALP.2017.141},
  annote =	{Keywords: population protocol, time lower bound, stable computation}
}
Document
Intrinsic Universality in Self-Assembly

Authors: David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile assembly system. We give a tile assembly system that is capable of simulating a very wide class of tile systems, including itself. Specifically, we give a tile set that simulates the assembly of any tile assembly system in a class of systems that we call \emph{locally consistent}: each tile binds with exactly the strength needed to stay attached, and that there are no glue mismatches between tiles in any produced assembly. Our construction is reminiscent of the studies of \emph{intrinsic universality} of cellular automata by Ollinger and others, in the sense that our simulation of a tile system $T$ by a tile system $U$ represents each tile in an assembly produced by $T$ by a $c \times c$ block of tiles in $U$, where $c$ is a constant depending on $T$ but not on the size of the assembly $T$ produces (which may in fact be infinite). Also, our construction improves on earlier simulations of tile assembly systems by other tile assembly systems (in particular, those of Soloveichik and Winfree, and of Demaine et al.) in that we simulate the actual process of self-assembly, not just the end result, as in Soloveichik and Winfree's construction, and we do not discriminate against infinite structures. Both previous results simulate only temperature 1 systems, whereas our construction simulates tile assembly systems operating at temperature 2.

Cite as

David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods. Intrinsic Universality in Self-Assembly. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.STACS.2010.2461,
  author =	{Doty, David and Lutz, Jack H. and Patitz, Matthew J. and Summers, Scott M. and Woods, Damien},
  title =	{{Intrinsic Universality in Self-Assembly}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2461},
  URN =		{urn:nbn:de:0030-drops-24619},
  doi =		{10.4230/LIPIcs.STACS.2010.2461},
  annote =	{Keywords: Biological computing, Molecular computation, intrinsic universality, self-assembly}
}
  • Refine by Author
  • 5 Doty, David
  • 5 Soloveichik, David
  • 2 Luchsinger, Austin
  • 2 Woods, Damien
  • 1 Beame, Paul
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Models of computation
  • 1 Applied computing → Computational biology
  • 1 Applied computing → Physical sciences and engineering
  • 1 Computing methodologies → Parallel computing methodologies
  • 1 Theory of computation
  • Show More...

  • Refine by Keyword
  • 2 stable computation
  • 1 Biological computing
  • 1 Cumulative memory complexity
  • 1 DNA Computing
  • 1 DNA Storage
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 4 2023
  • 2 2021
  • 1 2010
  • 1 2017
  • 1 2020
  • Show More...

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