Hiring
Seeking talented graduate students and postdocs with an interest in one or both of the following: (1) CS theory/discrete math/algorithms, or (2) (wet lab)
molecular biology.
Postdoc job posting
Recent News
October 2023: David is named Schmidt Science Polymath
January 2023: Congratulations to Boya and Cameron on starting new postdoctoral positions in Caltech!
November 2022: Boya is awarded the Helen Hay Whitney Foundation Fellowship!
November 2022: Congratulations to Cameron for his successful PhD thesis defense!
Advising
bioECE advising notes (MS/PhD): overview slides, notes
Teaching
Fall 2023: ECE 360C: Algorithms
[ syllabus,
introductory slides,
schedule
]
Spring 2023: ECE 381V/CS 395T: Unconventional Computation
[ syllabus,
introductory slides,
schedule ]
Research Interests: Unconventional Computation
-
Molecular programming: engineering smart molecules
Using DNA hybridization and "strand displacement cascades" we build molecular interactions for synthetic biology, nanotechnology, and bioengineering in our wet-lab. We use chemistry as a "programming language". -
Models of chemical kinetics and distributed computing
We use formal models to discover the potential and limits of chemical information processing. Many of our results generalize beyond chemistry to distributed computing with computationally weak agents. -
Quantum and reversible computation
For low energy computation and for quantum computing, computation must "look similar" both forward and backward in time. We study such computation and develop tricks to optimize it.
Research Group
Current
Aditi Awasthi (CS MS student)Niels Kornerup (CS PhD student)
Austin Luchsinger (ECE PhD student)
Leo Orshansky (CS undergraduate student)
Nadia Siles (ECE PhD student)
Former
Cameron Chalk (now postdoc at Caltech)Boya Wang (now postdoc at Caltech)
Yizhuo Du (now at Google)
Keenan Breik
Lakshmi Prakash (now at Bloomberg LP)
Software
-
StableGen: online tool for answering questions about stable
configurations of a Thermodynamic Binding Network [related
paper].
For large problem instances, please install the command line tool locally.
A restricted set of functionalities is also available as the TBNSolver Mathematica package. - CRNSimulator: Mathematica package for deterministic and stochastic simulation of Chemical Reaction Networks.
Publications [Google scholar profile]
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.-
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 ] -
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 ] -
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) ] -
The Spooky Pebble Game (in Quantum Computing)[α] 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 ]