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 DNABoya Wang*, Siyuan Stella Wang*, Cameron Chalk, Andrew D. Ellington, David Soloveichik
[ PNAS 120 (37) e2217330120, 2023 ] - Optimal Information Encoding in Chemical Reaction NetworksAustin Luchsinger, David Doty, David Soloveichik
[ DNA Computing and Molecular Programming 29 (DNA29), 2023: arXiv ] - Thermodynamically Driven Signal AmplificationJoshua 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 ReactionsBoya 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 NetworksMarko 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 linkagesKeenan Breik, Austin Luchsinger, David Soloveichik
[ DNA Computing and Molecular Programming 27 (DNA27), 2021: DOI, .pdf ] - CRNs Exposed: Systematic Exploration of Chemical Reaction NetworksMarko 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 NetworksMarko 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 nickingS 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 CascadesBoya 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 networksKeenan 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 SystemsBoya 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 LanguageMarko 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 systemsNiranjan 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 paper and .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 clampsBoya 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 systemsChris 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 regimeOphelia 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 DNAYuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, Georg Seelig
[ Nature Nanotechnology 8: 755-762, 2013: .pdf paper and .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 polymersLulu 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 KineticsDavid Soloveichik, Georg Seelig, Erik Winfree
[ Full version: PNAS 107 (12): 5393-5398, 2010: .pdf paper and .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 CircuitsGeorg 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 ClassifiersDavid Soloveichik
[ Preprint: .pdf ] - Programmability of Chemical Reaction NetworksMatt 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-LeapingDavid Soloveichik
[ Journal of Computational Biology 16(3): 501-522, 2009 ]
[ Preprint: arXiv ] - Computation with Finite Stochastic Chemical Reaction NetworksDavid 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-AssemblyDavid Soloveichik, Matthew Cook, Erik Winfree
[ Natural Computing, (online July 2007): .pdf ] - Enzyme-Free Nucleic Acid Logic CircuitsGeorg Seelig, David Soloveichik, David Yu Zhang, Erik Winfree
[ Science 314:1585-1588, 2006: .pdf paper and .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 PatternsDavid Soloveichik and Erik Winfree
[ DNA Computing 11 (DNA11), LNCS 3892: 305-324, 2006: .pdf ] - The Computational Power of Benenson AutomataDavid Soloveichik and Erik Winfree
[ Theoretical Computer Science 244(2-3):279-297, 2005: .pdf paper and .pdf erratum ] - Complexity of Self-Assembled ShapesDavid 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 ]
