David Doty
Google Scholar,
dblp,
ORCID
Note on author order: In most cases my co-authors and I have
followed the common
mathematics/theoretical computer science convention
of alphabetically-ordered authors. Unlike the standard in some other areas of
science, in my papers there is no
lead author or second author or special place for a principal investigator.
It's just alphabetical.
See
here,
here,
here,
or
here
for more discussion of this convention.
Exceptions are marked with [β].
Invited talks
Preprints (unpublished)
-
Harvesting Brownian motion: Zero energy computational sampling.
David Doty, Niels Kornerup, Austin Luchsinger, Leo Orshansky, David Soloveichik, Damien Woods.
Preprint.
[ arXiv ]
Refereed conference/journal publications
-
The computational power of discrete chemical reaction networks with bounded executions.
David Doty, Ben Heckmann.
DISC 2024, to appear.
[ arXiv ]
-
Rate-independent continuous inhibitory chemical reaction networks are Turing-universal.
Kim Calabrese, David Doty.
UCNC 2024: Proceedings of the 21st International Conference on Unconventional Computation and Natural Computation, 2024.
[ arXiv ]
-
Optimal information encoding in chemical reaction networks.
[β] Austin Luchsinger, David Doty, and David Soloveichik.
DNA 2023: Proceedings of the 20th International Conference on DNA
Computing and Molecular Programming, 9:1-9:16, 2023.
[ arXiv |
DOI
]
-
Thermodynamically driven signal amplification.
[β] Joshua Petrack, David Soloveichik, and David Doty.
DNA 2023: Proceedings of the 20th International Conference on DNA
Computing and Molecular Programming, 8:1-8:22, 2023.
[ arXiv |
DOI
]
-
Accelerating self-assembly of crisscross slat systems.
David Doty, Hunter Fleming, Daniel Hader, Matthew J. Patitz, and Lukas A. Vaughan.
DNA 2023: Proceedings of the 20th International Conference on DNA
Computing and Molecular Programming, 7:1--7:23, 2023.
[ DOI
]
-
Rate-independent computation in continuous chemical reaction networks.
Ho-Lin Chen, David Doty, Wyatt Reeves, and David Soloveichik.
Journal
JACM 2023: Journal of the ACM, 70(3):1-61, 2023.
[
arXiv |
BibTeX |
DOI ]
Conference
(note: the journal version is heavily updated, so check the links above instead of the old links below)
ITCS 2014: Proceedings of the 5th Innovations in Theoretical Computer
Science Conference,
(Princeton, New Jersey, USA, January 12-14, 2014), pp. 313-326.
[ PDF |
BibTeX |
DOI ]
-
Dynamic size counting in population protocols.
David Doty and Mahsa Eftekhari.
SAND 2022: 1st Symposium on Algorithmic Foundations of Dynamic Networks.
[
arXiv |
BibTeX |
DOI
]
-
Simulating 3-symbol Turing machines with SIMD||DNA.
David Doty and Aaron Ong.
SAND 2022: 1st Symposium on Algorithmic Foundations of Dynamic Networks.
[
arXiv |
BibTeX |
DOI
]
-
A survey of size counting in population protocols.
David Doty and Mahsa Eftekhari.
TCS 2021: Theoretical Computer Science, 894:91-102 (2021).
[ arXiv |
BibTeX |
DOI ]
-
A time and space optimal stable population protocol solving exact majority.
David Doty, Mahsa Eftekhari, Leszek Gąsieniec, Grzegorz Stachowiak, Eric
Severson, and Przemysław Uznański.
Full conference
FOCS 2021:
62nd Annual IEEE Symposium on Foundations of Computer Science,
(Boulder, Colorado, Feb. 7-10, 2022).
[ arXiv |
BibTeX |
DOI
]
Brief announcement
PODC 2021:
Proceedings of the 40th ACM Symposium on Principles of Distributed Computing,
(Salerno, Italy, Jul 26-30, 2021).
[ BibTeX |
DOI ]
-
ppsim: A software package for efficiently simulating and visualizing population
protocols.
David Doty and Eric Severson.
CMSB 2021:
Proceedings of the 19th International Conference on Computational Methods in Systems
Biology,
(Bordeaux, France, 22nd-24th September 2021), pages 245--253.
[ arXiv |
BibTeX |
DOI ]
-
Computing properties of thermodynamic binding networks: An integer programming
approach.
[β] David Haley and David Doty.
DNA 2021: Proceedings of the 27th International Conference on DNA
Computing and Molecular Programming, 205:2:1--2:16, 2021.
[ arXiv |
BibTeX |
DOI
]
-
Time-optimal self-stabilizing leader election in population protocols.
Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson,
and Chuan Xu.
PODC 2021:
Proceedings of the 40th ACM Symposium on Principles of Distributed Computing,
(Salerno, Italy, Jul 26-30, 2021).
[ arXiv |
BibTeX |
DOI ]
-
Message complexity of population protocols.
Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson.
Conference
DISC 2020:
Proceedings of the 34th International Symposium on DIStributed Computing,
(Freiburg, Germany, Oct 12-16, 2020), pp. 6:1--6:18.
[ arXiv |
BibTeX |
DOI ]
-
scadnano: A browser-based, scriptable tool for designing DNA nanostructures.
David Doty, Benjamin L Lee, and Tristan Stérin.
DNA 2020: Proceedings of the 26th International Conference on DNA
Computing and Molecular Programming, 174:9:1--9:17, 2020.
[ arXiv |
BibTeX |
DOI ]
-
Efficient size estimation and impossibility of termination in uniform dense
population protocols.
David Doty and Mahsa Eftekhari.
Conference
PODC 2019:
Proceedings of the 38th ACM Symposium on Principles of Distributed Computing,
(Toronto, Canada, Jul 29-Aug 2, 2019), pp. 34-42.
[ arXiv |
BibTeX |
DOI ]
-
Composable computation in discrete chemical reaction networks.
[β] Eric E. Severson, David Haley, and David Doty.
Journal
DIST 2021: Distributed Computing, 34(6):437-461. Special issue of
invited papers from PODC 2019.
[ arXiv |
BibTeX |
DOI ]
Conference
PODC 2019:
Proceedings of the 38th ACM Symposium on Principles of Distributed Computing,
(Toronto, Canada, Jul 29-Aug 2, 2019), pp. 14-23.
[ BibTeX |
DOI]
-
Diverse and robust molecular algorithms using reprogrammable DNA self-assembly.
[β] Damien Woods†, David Doty†, Cameron
Myhrvold, Joy Hui, Felix Zhou, Peng Yin, Erik Winfree.
†joint first authors
Journal
Nature 2019: Nature 567(7748):366-372 (2019).
[ Main paper |
Supplementary Information |
BibTeX |
DOI (official Nature site) ]
[ Supplementary data:
DNA
sequences,
sample
AFM images,
related code and
data
]
[ Press releases:
UC-Davis,
Caltech,
Maynooth,
Inria (en
français)
]
[ Media coverage:
Chemistry
World,
Irish
Times,
Physics
World,
Wired,
IEEE
Spectrum,
Silicon
Republic,
Europa
Press (en español),
The California Aggie,
Nature Asia
]
[ Interviews:
Maynooth University,
The
Wider View (Northern Sound Radio),
Futureproof
(Newstalk Radio)
]
[ Artwork:
A
carpet of algorithms
]
Erik's
observations on this experiment's relation to mathematical logic, automatic
theorem proving, Gödel's Incompleteness Theorem, Turing's uncomputability, and
aluminum-manganese alloys.
-
Brief announcement: Exact size counting in uniform population protocols
in nearly logarithmic time.
David Doty, Mahsa Eftekhari, Othon Michail, Paul Spirakis, and Michail Theofilatos.
Conference
DISC 2018:
Proceedings of the 32nd International Symposium on DIStributed Computing,
(New Orleans, LA, USA, Oct 15-19, 2018), pp. 46:1-46:3.
[ PDF (full) |
PDF (brief) |
arXiv |
BibTeX |
DOI ]
-
Programming substrate-independent kinetic barriers with thermodynamic binding
networks.
Keenan Breik, Cameron Chalk, David Doty, David Haley, and David Soloveichik.
Journal
TCBB 2021: IEEE/ACM Transactions on Computational Biology and
Bioinformatics, 18(1): 283-295 (2021).
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
CMSB 2018:
Proceedings of the 16th International Conference on Computational Methods in Systems
Biology,
(Prague, Czech Republic, Sept 12-14, 2018), pp. 203-219.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Computational complexity of atomic chemical reaction networks.
David Doty and Shaopeng Zhu.
Journal
NaCo 2018: Natural Computing, 17(4): 677-691 (2018).
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
SOFSEM 2018: Proceedings of the 44th International Conference on Current
Trends in Theory and Practice of Computer Science,
(Krems an der Donau, Austria, Jan 29 - Feb 2, 2018), pp. 212-226.
[ PDF |
BibTeX |
DOI ]
-
Thermodynamic binding networks.
David Doty, Trent A. Rogers, David Soloveichik, Chris Thachuk, Damien Woods.
Conference
DNA 2017: Proceedings of the 23rd International Conference on DNA
Computing and Molecular Programming,
(Austin, TX, USA, Sept 24-28, 2017), pp. 249-266.
[
arXiv |
BibTeX |
DOI ]
-
Hardness of computing and approximating predicates and functions with leaderless
population protocols.
Amanda Belleville, David Doty, and David Soloveichik.
Conference
ICALP 2017: Proceedings of the 44th International Colloquium on Automata,
Languages and Programming,
(Warsaw, Poland, July 10-14, 2017), pp. 141:1-141:14.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Democratic, existential, and consensus-based output conventions in stable
computation by chemical reaction networks.
Robert Brijder, David Doty, and David Soloveichik.
Journal
NaCo 2018: Natural Computing, 17(1): 97-108 (2018). Special issue of
invited papers from DNA 2016.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
Robustness of expressivity in chemical reaction networks.
DNA 2016: Proceedings of the 22nd International Conference on DNA
Computing and Molecular Programming,
(Munich, Germany, Sept 4-8, 2016), pp. 52-66.
[ PDF |
BibTeX |
DOI ]
-
Design of geometric molecular bonds.
David Doty and Andrew Winslow.
Journal
T-MBMC 2017: IEEE Transactions on Molecular, Biological, and Multi-Scale
Communications 3(1):13-23 (2017). Invited paper.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
ISIT 2016: Proceedings of the 2016 IEEE International Symposium on
Information Theory, (Barcelona, Spain, July 10-15, 2016), pp. 1789-1793.
[ PDF |
BibTeX |
DOI ]
-
Stable leader election in population protocols requires linear time.
David Doty and David Soloveichik.
Journal
DIST 2018: Distributed Computing, 31(4):257-271 (2018). Special
issue of invited papers from DISC 2015.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
DISC 2015: Proceedings of the 29th International
Symposium on DIStributed Computing, (Tokyo, Japan, Oct 5-9, 2015), pp. 602-616.
[ PDF |
BibTeX |
DOI ]
-
Pattern overlap implies runaway growth in hierarchical tile systems.
Ho-Lin Chen, David Doty, Ján Maňuch, Arash Rafiey, and Ladislav Stacho.
Journal
JoCG 2016: Journal of Computational Geometry 7(2):3-18, 2016.
Special issue of invited papers from SoCG 2015.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
SoCG 2015: Proceedings of the 31st International Symposium on
Computational Geometry, (Eindhoven, the Netherlands, June 22-25, 2015), pp.
360-373.
[ PDF |
BibTeX |
DOI ]
-
Designing ordered nucleic acid self-assembly processes.
[β] Rebecca Schulman and David Doty.
Journal
COSTBI 2015: Current Opinion in Structural Biology 31: 57-63, 2015.
Invited review article.
[ PDF |
BibTeX |
DOI ]
-
Speed faults in computation by chemical reaction networks.
Ho-Lin Chen, Rachel Cummings, David Doty, and David Soloveichik.
Journal
DIST 2017: Distributed Computing 30(5): 373-390, 2017. Special issue
of invited papers from DISC 2013, DISC 2014, and PODC 2014.
[ PDF |
BibTeX |
DOI ]
Conference
DISC 2014: Proceedings of the 28th International
Symposium on DIStributed Computing, (Austin, Texas, USA, Oct 12-15, 2014), pp.
16-30.
Best paper award.
[ PDF |
BibTeX |
DOI ]
-
Probability 1 computation with chemical reaction networks.
Rachel Cummings, David Doty, and David Soloveichik.
Journal
NaCo 2016: Natural Computing, 15(2):245-261, 2016. Special issue of
invited papers from DNA 2014.
[ PDF |
BibTeX |
DOI ]
Conference
DNA 2014: Proceedings of the 20th International
Meeting on DNA Computing and Molecular Programming, (Kyoto, Japan, Sept 22-26,
2014), pp. 37-52.
[ PDF |
BibTeX |
DOI ]
-
Fast algorithmic self-assembly of simple shapes using random agitation.
Ho-Lin Chen, David Doty, Dhiraj Holden, Chris Thachuk, Damien Woods, and Chun Tao
Yang.
Conference
DNA 2014: Proceedings of the 20th International
Meeting on DNA Computing and Molecular Programming, (Kyoto, Japan, Sept 22-26,
2014), pp. 20-36.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Producibility in hierarchical self-assembly.
David Doty.
Journal
NaCo 2016: Natural Computing, 15(1):41-49, 2016. Special issue of
invited papers from UCNC 2014.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
UCNC 2014: Proceedings of the 13th International Conference on
Unconventional Computation and Natural Computation, (London, Ontario, Canada,
July 14-18, 2014), pp. 142-154.
[ PDF |
BibTeX |
DOI ]
-
Timing in chemical reaction networks.
David Doty.
Conference
SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete
Algorithms,
(Portland, Oregon, USA, January 5-7, 2014), pp. 772-784.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Leaderless deterministic chemical reaction networks.
David Doty and Monir Hajiaghayi.
Journal
NaCo 2015: Natural Computing 14(2):213-223, 2015. Special issue of
invited papers from DNA 2013.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
DNA 2013: Proceedings of the 19th International
Meeting on DNA Computing and Molecular Programming, (Tempe, Arizona, USA, Sept
23-27, 2013), pp. 46-60.
[ PDF |
BibTeX |
DOI ]
-
Theory of algorithmic self-assembly.
David Doty.
Journal
CACM 2012: Communications of the ACM 55(12):78-88, 2012. Invited
review article.
[ PDF |
BibTeX |
DOI |
Online
version ]
I created a
short video
to accompany and introduce this article.
-
The tile assembly model is intrinsically universal.
David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers,
and Damien Woods.
Conference
FOCS 2012: Proceedings of the 53rd Annual IEEE
Symposium on Foundations of Computer Science
(New Brunswick, New Jersey, USA, October 20-23, 2012), pp. 302-310.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Deterministic function computation with chemical reaction networks.
Ho-Lin Chen, David Doty, and David Soloveichik.
Journal
NaCo 2014: Natural Computing 13(4):517-534, 2014. Special issue of
invited papers from DNA 2012.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
DNA 2012: Proceedings of the 18th International
Meeting on DNA Computing and Molecular Programming, (Aarhus, Denmark, August
14-17, 2012),
pp. 25-42.
[ PDF |
BibTeX |
DOI ]
-
Parallelism and time in hierarchical self-assembly.
Ho-Lin Chen and David Doty.
Journal
SICOMP 2017: SIAM Journal on Computing 46(2):661-709, 2017.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete
Algorithms,
(Kyoto, Japan, January 17-19, 2012), pp. 1163-1182.
[ PDF |
BibTeX |
DOI
]
-
Program size and temperature in self-assembly.
Ho-Lin Chen, David Doty, and Shinnosuke Seki.
Journal
Algorithmica 2015: Algorithmica 72(3):884-899, 2015.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
ISAAC 2011: Proceedings of the 22nd International Symposium on
Algorithms and Computation,
(Yokohama, Japan, December 5-8, 2011), LNCS 7074, pp. 445-453.
[ PDF |
BibTeX |
DOI ]
-
The power of nondeterminism in self-assembly.
Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
Journal
ToC 2013: Theory of Computing 9(1):1-29, 2013.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
SODA 2011: Proceedings of the 22nd Annual ACM-SIAM
Symposium on Discrete Algorithms,
(San Francisco, California, USA, January 23-25, 2011), pp. 590-602.
[ PDF |
BibTeX |
DOI ]
-
Strong fault-tolerance for self-assembly with fuzzy temperature.
David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, and Scott M.
Summers.
Conference
FOCS 2010: Proceedings of the 51st Annual IEEE
Symposium on Foundations of Computer Science,
(Las Vegas, Nevada, USA, October 23-26, 2010), pp. 417-426.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Scalable, time-responsive, digital, energy-efficient molecular circuits using
DNA strand displacement.
Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
Conference
DNA 2010: Proceedings of the 16th International
Meeting on DNA Computing and Molecular Programming,
(Hong Kong, China, June 14-17, 2010)
pp. 25-36.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Negative interactions in irreversible self-assembly.
David Doty, Lila Kari, and Benoît Masson.
Journal
Algorithmica 2013: Algorithmica 66(1):153-172, 2013.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
DNA 2010: Proceedings of the 16th International
Meeting on DNA Computing and Molecular Programming,
(Hong Kong, China, June 14-17, 2010)
pp. 37-48.
[ PDF |
BibTeX |
DOI ]
-
Intrinsic universality in self-assembly.
David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods.
Conference
STACS 2010: Proceedings of the 27th International Symposium on
Theoretical Aspects of Computer Science,
(Nancy, France, March 4-6, 2010), pp. 275-286.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Randomized self-assembly for exact shapes.
David Doty.
Journal
SICOMP 2010: SIAM Journal on Computing 39(8):3521-3552, 2010.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
FOCS 2009: Proceedings of the 50th Annual IEEE
Symposium on Foundations of Computer Science,
(Atlanta, Georgia, USA, October 24-27, 2009), pp. 85-94.
[ PDF |
BibTeX |
DOI ]
-
Random number selection in self-assembly.
David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods.
Conference
UC 2009: Proceedings of the 8th International
Conference on Unconventional Computation,
(Ponta Delgada, Portugal, September 7-11, 2009), pp. 143-157.
[ PDF |
BibTeX |
DOI ]
-
A domain-specific language for programming in the tile assembly model.
David Doty and Matthew J. Patitz.
Conference
DNA 2009: Proceedings of The 15th International
Meeting on DNA Computing and Molecular Programming,
(Fayetteville, Arkansas, USA, June 8-11, 2009)
pp. 25-34.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Limitations of self-assembly at temperature 1.
David Doty, Matthew J. Patitz, and Scott M. Summers.
Journal
TCS 2011: Theoretical Computer Science 412(1-2):145-158, 2011.
Special issue of
invited papers from Complexity of Simple Programs workshop, Cork, Ireland, 2008.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
DNA 2009: Proceedings of The 15th International
Meeting on DNA Computing and Molecular Programming,
(Fayetteville, Arkansas, USA, June 8-11, 2009),
pp. 35-44.
[ PDF |
BibTeX |
DOI ]
-
Feasible depth.
David Doty and Philippe Moser.
Conference
CiE 2007:
3rd Conference of
Computability in Europe,
(Siena, Italy, June 18-23, 2007),
pp. 228-237.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Constructive dimension and Turing degrees.
Laurent Bienvenu, David Doty, and Frank Stephan.
Journal
ToCS 2009: Theory of Computing Systems 45(4):740-755, 2009. Special
issue of
invited papers from Computability in Europe 2007.
[ PDF |
arXiv |
BibTeX |
DOI ]
This version corrects an error in the proof of Theorem 2.4 in the conference version
Constructive dimension and weak truth-table degrees
from CiE 2007,
and the revised proof only applies to Turing degrees, hence the change of the name of the
paper. Also, the printed version of this paper
in ToCS 2009 contains a different error in the proof of Theorem 2.4. The corrected proof is
in the file hosted on this website
and on arXiv.
Conference
Constructive dimension and weak truth-table degrees.
CiE 2007:
3rd Conference of
Computability in Europe,
(Siena, Italy, June 18-23, 2007),
pp. 63-72.
[ PDF |
BibTeX |
DOI ]
-
Pushdown dimension.
David Doty and Jared Nichols.
Journal
TCS 2007: Theoretical Computer Science 381(1-3):105-123, 2007.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Finite-state dimension and real arithmetic.
David Doty, Jack H. Lutz, and Satyadev Nandakumar.
Journal
I&C 2007: Information and Computation 205(11):1640-1651, 2007.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
ICALP 2006: Proceedings of the 33rd International
Colloquium on
Automata, Languages and Programming,
(Venice, Italy, July 9-16, 2006), Springer-Verlag,
2006, pp. 537-547.
[ PDF |
BibTeX |
DOI ]
-
Dimension extractors and optimal decompression.
David Doty.
Journal
ToCS 2008: Theory of Computing Systems 43(3-4):425-463, 2008.
Special issue of
invited papers from Computability in Europe 2006.
[ PDF |
arXiv |
BibTeX |
DOI ]
Conference
Every sequence is decompressible from a random one.
CiE 2006: Logical Approaches to Computational Barriers, 2nd
Conference on Computability in Europe,
(Swansea, UK, June 30 - July 5, 2006),
Proceedings, Lecture Notes in Computer Science volume 3988,
Springer-Verlag, 2006, pp. 153-162.
[ PDF |
BibTeX |
DOI ]
-
Zeta-dimension.
David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser.
Conference
MFCS 2005: Proceedings of the 30th International Symposium on
Mathematical Foundations of Computer Science,
(Gdansk, Poland, August 29 - September 2, 2005),
Springer-Verlag, 2005, pp. 283-294.
[ PDF |
arXiv |
BibTeX |
DOI ]
-
Non-local evolutionary adaptation in gridplants.
David Doty.
Conference
CEC 2004: Proceedings of the 2004 IEEE Congress on Evolutionary
Computation, IEEE, 2004, pp. 1602-1609.
[ PDF |
BibTeX |
DOI ]
-
Morphometric grayscale texture analysis using foot patterns.
Dan Ashlock, Dean C. Adams, and David Doty.
Conference
CEC 2003: Proceedings of the 2003 IEEE Congress on Evolutionary
Computation, IEEE, 2003, pp. 1575-1581.
[ PDF |
BibTeX |
DOI ]
Invited book chapters
-
Hierarchical self-assembly.
David Doty.
Encyclopedia of Algorithms, pp. 903-909, 2016.
[ PDF |
BibTeX |
DOI
]
-
Randomized self-assembly.
David Doty.
Encyclopedia of Algorithms, pp. 1759-1767, 2016.
[ PDF |
BibTeX |
DOI
]
Ph.D. Thesis
-
Applications of the theory of computation to nanoscale self-assembly.
David Doty.
Ph.D. Thesis, Iowa State University, 2009.
[ PDF |
BibTeX ]
Invited talks
-
The computational power of execution bounded chemical reaction networks
UC Santa Cruz Applied Math Department Seminar,
June 3, 2024.
[ PPT,
PDF ]
-
Execution bounded chemical reaction networks
Seminar on the Mathematics of Reaction Networks,
Online, May 9, 2024.
[ PPT,
PDF ]
-
Time-optimal self-stabilizing leader election in population protocols.
Hamilton
Institute Seminar Series,
Maynooth University, Maynooth, Ireland, Feb 2022.
-
Crystals that think about how they're growing.
Workshop on
Computing with Unconventional Technologies (CUT):
for Green and Sustainable Computing,
Oct 2021.
[
PPT,
PDF
]
-
Crystals that think about how they're growing.
University
of Minnesota ECE Colloquium,
Oct 2021.
[
PPT,
PDF
]
-
Crystals that think about how they're growing.
University
of Washington Molecular Programming Seminar Series,
Apr 2021.
[ PPT,
PDF,
video
]
-
Crystals that think about how they're growing.
Biocompute.club,
Mar 2021.
-
Crystals that think about how they're growing.
CELLS: Workshop on
Computing among Cells
Oct 2020.
-
Crystals that think about how they're growing.
Computer Science Colloquium,
University of New Mexico, Sept 2019.
[ PPT, PDF ]
-
Digging (energy) wells for unknown substances: Programming substrate-independent energy
barriers in catalytic chemical reactions.
Hamilton
Institute Seminar Series,
Maynooth University, Maynooth, Ireland, May 2019.
[ PPT, PDF ]
-
DNA tile self-assembly.
Dagstuhl meeting on Algorithmic Foundations of Programmable Matter,
Schloss Dagstuhl, Wadern, Germany, Aug 2018.
[ PPT, PDF ]
-
Thermodynamic binding networks: How to self-assemble molecules reliably without knowing too
much about them.
Unconventional Computation and Natural Computation,
Workshop on Self-Assembly, Geometry, and Computation,
Fontainebleau, France, June 2018.
[ PPT, PDF ]
-
Hardness of computing and approximating predicates and functions with leaderless population
protocols.
JMM 2018: Joint Mathematics Meetings, AMS Special Session on Emergent Phenomena in Discrete
Models,
San Diego, CA, USA, Jan 2018.
-
The limits of chemical computing.
DNA 2017: 23rd International Conference on DNA Computing and Molecular Programming,
Austin, Texas, USA, Sept 2017.
Plenary talk.
[ PPT, PDF ]
-
DNA tile self-assembly.
DNA 2017: 23rd International Conference on DNA Computing and Molecular Programming,
Austin, Texas, USA, Sept 2017.
Tutorial.
[ PPT, PDF
]
-
Limits of chemical computing.
CS Departmental Seminar, University of Liverpool, UK, Sept 2017.
-
Thermodynamic binding networks.
Workshop on Thermodynamics and Computation: Towards a New Synthesis, Santa Fe Institute, Aug
2017.
-
Slow Molecule Revolution: Time lower bounds for computation with chemical reaction networks.
Laboratoire de Recherche en Informatique, Université Paris-Sud, Jul 2017.
Invited Talk.
[ PPT ]
-
"No we can't": Impossiblity of efficient leader election in chemical reaction networks
Workshop on Advances in
Numerical and Analytic Approaches for the Study of Non-Spatial Stochastic Dynamical
Systems in Molecular Biology,
Isaac Newton Institute for Mathematical Sciences, University of Cambridge,
Invited Talk, April 2016.
[ PPT |
PDF ]
-
Design of geometric molecular bonds, à la Reed-Solomon
Workshop on Coding Techniques for
Synthetic Biology,
University of Illinois at Urbana-Champaign,
Invited Talk, October
2015.
[ PPT |
PDF ]
-
Programming with chemical kinetics
Kinetic Networks: From
topology to design,
Santa Fe Institute,
Invited Talk,
September 2015.
[ ODP |
PDF ]
-
Computation by (not about) chemistry
Workshop on Mathematical Trends in
Reaction Network Theory,
University of Copenhagen,
Invited Talk, July 2015.
[ ODP |
PDF ]
-
Agents and reagents: Distributed systems in a test tube. (with David Soloveichik)
DISC 2014:
28th International
Symposium on DIStributed Computing,
Austin, TX,
Tutorial, October 2014.
[ ODP |
PDF ]
-
Deterministic function computation with chemical reaction networks.
University of British Columbia, Department of Computer Science, Seminar
Talk, September 2012.
[ ODP |
PDF ]
-
Deterministic computation with chemical reaction networks.
Aalto University, Department of
Information and Computer Science, ICS
Forum, June
2012.
[ ODP |
PDF ]
-
Algorithmic self-assembly with DNA tiles.
DNA 2011:
17th International Conference on DNA
Computing and Molecular Programming,
Pasadena, CA,
Tutorial,
September 2011.
[ ODP |
PPT ]
-
The state of algorithmic self-assembly at Iowa State.
FNANO 2010:
7th Annual Foundations of Nanoscience
Conference,
Snowbird, UT,
Invited Talk,
April 2010.
[ ODP |
PPT ]
-
Coevolution and non-local adaptation in gridplants.
Pioneer Hi-Bred Bioinformatics Group, March
2004.
[ PDF |
PS ]
Other technical reports
The following are unpublished technical reports that I will probably not attempt to publish.
Both are results that I enjoyed working on, but later found out that they were already known in some
sense.
-
An oracle strongly separating deterministic time from nondeterministic time, via
Kolmogorov complexity.
David Doty.
Technical Report 1004.3993, arXiv.org, 2010.
[ PDF |
arXiv |
BibTeX ]
-
Finite-state dimension and lossy decompressors.
David Doty and Philippe Moser.
Technical Report cs.CC/0609096, arXiv.org, 2006.
[ PDF |
arXiv |
BibTeX ]
The PDF document links above are preprints, similar to what
was submitted to the conference, with appendices containing material that
did not fit in the page limit. The
arXiv
link references a publicly archived version of the paper
that is possibly more out-of-date than the PDF files available here.
The "Journal Version" links can mean that the paper from the conference was
submitted to the journal with largely the same content (other than possibly
re-arranging due to conference page limits), or it could mean that
substantial content from the conference version was used in the journal
version, although the journal version may have additional content.
These papers may be downloaded for research or personal use only.
The copyright for each paper is owned either by the publisher of
the journal or conference proceedings in which the paper is published,
or by the authors of the paper if the paper is unpublished.