Group Publications

Most copyrights are owned by the publisher; files are provided here as a convenience for one-time individual use. [α]=alphabetical author order following the common mathematics and theoretical computer science convention.

  • Quantum Time-Space Tradeoffs for Matrix Problems
    [α] Paul Beame, Niels Kornerup, Michael Whitmeyer
    [ 56th ACM Symposium on Theory of Computing (STOC), 2024: arXiv ]
  • Harvesting Brownian Motion: Zero Energy Computational Sampling
    [α] David Doty, Niels Kornerup, Austin Luchsinger, Leo Orshansky, David Soloveichik, Damien Woods
    [ Preprint: arXiv]
  • Parallel molecular computation on digital data stored in DNA
    Boya Wang*, Siyuan Stella Wang*, Cameron Chalk, Andrew D. Ellington, David Soloveichik
    [ PNAS 120 (37) e2217330120, 2023]
  • Optimal Information Encoding in Chemical Reaction Networks
    Austin Luchsinger, David Doty, David Soloveichik
    [ DNA Computing and Molecular Programming 29 (DNA29), 2023: arXiv]
  • Thermodynamically Driven Signal Amplification
    Joshua Petrack, David Soloveichik, David Doty
    [ DNA Computing and Molecular Programming 29 (DNA29), 2023: arXiv]
  • Cumulative Memory Lower Bounds for Randomized and Quantum Computation
    [α] Paul Beame, Niels Kornerup
    [ International Colloquium on Automata, Languages, and Programming (ICALP), 2023: arXiv ]
  • Uniform Robot Relocation is Hard in Only Two Directions Even Without Obstacles
    [α] David Caballero, Angel Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie
    [ Proceedings of the 20th International Conference on Unconventional Computation and Natural Computation (UCNC), 2023: conference paper ]
  • Rate-independent computation in continuous chemical reaction networks
    [α] Ho-Lin Chen, David Doty, Wyatt Reeves, David Soloveichik
    [ Journal of the ACM 70 (3): 1-61, 2023]
    [ See below for conference version (ITCS'14) ]
  • Speed and Correctness Guarantees for Programmable Enthalpy-Neutral DNA Reactions
    Boya Wang, Chris Thachuk, David Soloveichik
    [ ACS Synthetic Biology 12(4): 993-1006, 2023 ]
  • Barrier-1 Reachability for Thermodynamic Binding Networks is PSPACE-Complete (Brief Announcement)
    Austin Luchsinger
    [ Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND), 2022: .pdf ]
  • Programming and Training Rate-Independent Chemical Reaction Networks
    Marko Vasić*, Cameron Chalk*, Austin Luchsinger, Sarfraz Khurshid, David Soloveichik
    [ PNAS 119 (24) e2111552119, 2022]
    [ Also see Recorded talk at DNA Computing and Molecular Programming 27 (DNA27) ]
  • Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
    [α] Niels Kornerup, Jonathan Sadun, David Soloveichik
    [ Draft: arXiv]
  • Molecular machines from topological linkages
    Keenan Breik, Austin Luchsinger, David Soloveichik
    [ DNA Computing and Molecular Programming 27 (DNA27), 2021: DOI, .pdf]
  • CRNs Exposed: Systematic Exploration of Chemical Reaction Networks
    Marko Vasić, David Soloveichik, Sarfraz Khurshid
    [ (Best Student Paper Award) DNA Computing and Molecular Programming 26 (DNA26), 2020: arXiv]
  • Deep Molecular Programming: A Natural Implementation of Binary-Weight ReLU Neural Networks
    Marko Vasić, Cameron Chalk, Sarfraz Khurshid, David Soloveichik
    [ International Conference on Machine Learning (ICML), 2020: arXiv ]
    [ Also see Recorded talk]
  • DNA punch cards for storing data on native DNA sequences via enzymatic nicking
    S Kasra Tabatabaei, Boya Wang, Nagendra Bala Murali Athreya, Behnam Enghiad, Alvaro Gonzalo Hernandez, Christopher J Fields, Jean-Pierre Leburton, David Soloveichik, Huimin Zhao, Olgica Milenkovic
    [ Nature Communications 11: 1742, 2020 ]
  • SIMD||DNA: Single Instruction, Multiple Data Computation with DNA Strand Displacement Cascades
    Boya Wang, Cameron Chalk, David Soloveichik
    [ (Best Student Paper Award) DNA Computing and Molecular Programming 25 (DNA25), 2019: .pdf]
  • Computing properties of stable configurations of thermodynamic binding networks
    Keenan Breik, Chris Thachuk, Marijn Heule, David Soloveichik
    [ Theoretical Computer Science 785, 17-29, 2019: arXiv]
    [ Poster: .png]
    [ Software: TBNSolver ]
  • Effective Design Principles for Leakless Strand Displacement Systems
    Boya Wang, Chris Thachuk, Andrew Ellington, Erik Winfree, David Soloveichik
    [ PNAS 115 (52): E12182-E12191, 2018]
  • Programming Substrate-Independent Kinetic Barriers with Thermodynamic Binding Networks
    [α] Keenan Breik, Cameron Chalk, David Doty, David Haley, David Soloveichik
    [ Full version: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2019: arXiv]
    [ Extended abstract: 16th International Conference on Computational Methods in Systems Biology (CMSB), 2018: .pdf]
  • Composable Rate-Independent Computation in Continuous Chemical Reaction Networks
    [α] Cameron Chalk, Niels Kornerup, Wyatt Reeves, David Soloveichik
    [ Full version: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2019: arXiv]
    [ (Best Paper Award) Extended abstract: 16th International Conference on Computational Methods in Systems Biology (CMSB), 2018: .pdf]
  • CRN++: Molecular Programming Language
    Marko Vasić, David Soloveichik, Sarfraz Khurshid
    [ Natural Computing 19: 391-407, 2020]
    [ DNA Computing and Molecular Programming 24 (DNA24), 2018: arXiv]
  • Enzyme-free nucleic acid dynamical systems
    Niranjan Srinivas, James Parkin, Georg Seelig, Erik Winfree, David Soloveichik
    [ Science 358 (6369), 2017]
    [ Also see Introductory video, UT Press-Release: First-of-its-Kind Chemical Oscillator Offers New Level of Molecular Control, Scientific American Article: Programming a DNA Clock]
    [ Preprint: bioRxiv: .pdf paperand .pdf supplementary information ]
  • Thermodynamic binding networks
    [α] David Doty, Trent A. Rogers, David Soloveichik, Chris Thachuk, Damien Woods
    [ Full version (preprint): arXiv]
    [ Extended abstract: DNA Computing and Molecular Programming 23 (DNA23), 2017: .pdf]
  • Robust detection in leak-prone population protocols
    [α] Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski, David Soloveichik, Przemysław Uznański
    [ DNA Computing and Molecular Programming 23 (DNA23), 2017: .pdf ]
  • The design space of strand displacement cascades with toehold-size clamps
    Boya Wang, Chris Thachuk, Andrew D. Ellington, David Soloveichik
    [ DNA Computing and Molecular Programming 23 (DNA23), 2017: .pdf]
  • Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols
    [α] Amanda Belleville, David Doty, David Soloveichik
    [ Full version (preprint): arXiv]
    [ 44th International Colloquium on Automata, Languages and Programming (ICALP), 2017: .pdf]
  • Democratic, Existential, and Consensus-Based Output Conventions in Stable Computation by Chemical Reaction Networks
    [α] Robert Brijder, David Doty, David Soloveichik
    [ Natural Computing 17: 97-108, 2018]
    [ Preprint: arXiv]
  • Leakless DNA strand displacement systems
    Chris Thachuk, Erik Winfree, David Soloveichik
    [ DNA Computing and Molecular Programming 21 (DNA21), 2015: .pdf]
  • Stable leader election in population protocols requires linear time
    [α] David Doty, David Soloveichik
    [ Full version: Distributed Computing 31 (4): 257-271, 2018: arXiv]
    [ Extended abstract: International Symposium on Distributed Computing (DISC'15), 2015: .pdf]
  • Speed faults in computation by chemical reaction networks
    [α] Ho-Lin Chen, Rachel Cummings, David Doty, David Soloveichik
    [ Full version: Distributed Computing 30 (5): 373-390, 2017: .pdf]
    [ (Best Paper Award) Extended abstract: International Symposium on Distributed Computing (DISC'14), 2014: .pdf]
  • Completeness of transcriptional repressor networks operating in the unsaturated regime
    Ophelia S. Venturelli, David Soloveichik
    [ Draft: .pdf]
  • Probability 1 computation with chemical reaction networks
    [α] Rachel Cummings, David Doty, David Soloveichik
    [ Full version: Natural Computing 15: 245-261, 2016: .pdf]
    [ Extended abstract: DNA Computing and Molecular Programming 20 (DNA20), LNCS 8727:37-52, 2014: .pdf]
  • Rate-independent computation in continuous chemical reaction networks
    [α] Ho-Lin Chen, David Doty, David Soloveichik
    [ Conference on Innovations in Theoretical Computer Science (ITCS'14): 313-326, 2014: .pdf]
  • Programmable chemical controllers made from DNA
    Yuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, Georg Seelig
    [ Nature Nanotechnology 8: 755-762, 2013: .pdf paperand .pdf supplementary information]
    [ Also see Ehud Shapiro and Tom Ran's News and Views essay ]
  • Deterministic Function Computation with Chemical Reaction Networks
    [α] Ho-Lin Chen, David Doty, David Soloveichik
    [ Full version: Natural Computing 13: 517-534, 2013: .pdf]
    [ Preliminary extended abstract: DNA Computing and Molecular Programming 18 (DNA18), LNCS 7433:25-42, 2012 ]
  • Efficient Turing-universal computation with DNA polymers
    Lulu Qian, David Soloveichik, Erik Winfree
    [ Extended abstract: DNA Computing and Molecular Programming 16 (DNA16), LNCS 6518:123-140, 2011: .pdf]
  • DNA as a Universal Substrate for Chemical Kinetics
    David Soloveichik, Georg Seelig, Erik Winfree
    [ Full version: PNAS 107 (12): 5393-5398, 2010: .pdf paperand .pdf supplementary information ]
    [ (Best Student Paper Award) Preliminary extended abstract: DNA Computing 14 (DNA14), LNCS 5347:57-69, 2009: .pdf]
  • Time-Complexity of Multilayered DNA Strand Displacement Circuits
    Georg Seelig, David Soloveichik
    [ Revised version (improved lemmas 1 and 4): .pdf]
    [ Preliminary extended abstract: DNA Computing 15 (DNA15), LNCS 5877: 144-153, 2009: .pdf]
  • Statistical Learning of Arbitrary Computable Classifiers
    David Soloveichik
    [ Preprint: .pdf]
  • Programmability of Chemical Reaction Networks
    Matt Cook, David Soloveichik, Erik Winfree, Shuki Bruck
    [ Algorithmic Bioprocesses, (Eds. Condon, Harel, Kok, Salomaa, Winfree), Springer, pp. 543-584, 2009 ]
    [ Preprint: .pdf]
  • Robust Stochastic Chemical Reaction Networks and Bounded Tau-Leaping
    David Soloveichik
    [ Journal of Computational Biology 16(3): 501-522, 2009 ]
    [ Preprint: arXiv]
  • Computation with Finite Stochastic Chemical Reaction Networks
    David Soloveichik, Matt Cook, Erik Winfree, Shuki Bruck
    [ Natural Computing, (online Feb 2008), or Technical Report: CaltechPARADISE:2007.ETR085: .pdf ]
  • Combining Self-Healing and Proofreading in Self-Assembly
    David Soloveichik, Matthew Cook, Erik Winfree
    [ Natural Computing, (online July 2007): .pdf ]
  • Enzyme-Free Nucleic Acid Logic Circuits
    Georg Seelig, David Soloveichik, David Yu Zhang, Erik Winfree
    [ Science 314:1585-1588, 2006: .pdf paperand .pdf supplementary information]
    [ Also see Walter Fontana's Perspectives essay, Udi Shapiro's News and Views essay ]
    [ Our related patent is #20070072215: "Nucleic acid-based logic circuits" ]
  • Complexity of Compact Proofreading for Self-Assembled Patterns
    David Soloveichik and Erik Winfree
    [ DNA Computing 11 (DNA11), LNCS 3892: 305-324, 2006: .pdf]
  • The Computational Power of Benenson Automata
    David Soloveichik and Erik Winfree
    [ Theoretical Computer Science 244(2-3):279-297, 2005: .pdf paperand .pdf erratum]
  • Complexity of Self-Assembled Shapes
    David Soloveichik and Erik Winfree
    [ Full version: SIAM Journal on Computing 36 (6): 1544-1569, 2007: .pdf]
    [ (Best Student Paper Award) Extended abstract: DNA Computing 10 (DNA10), LNCS 3384:344-354, 2005: .pdf]