David Doty
Publications
Note on author order: In most cases my coauthors and I have
followed the common
mathematics/theoretical computer science convention
of alphabeticallyordered 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 [β].
Refereed conference/journal papers
These papers appear in the order in which the conference version was published, so some journal publication years are out of order.

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 1519, 2018), pp. 46:146:3.
[ PDF (full) 
PDF (brief) 
arXiv 
BibTeX ]

Programming substrateindependent kinetic barriers with thermodynamic binding networks.
Keenan Breik, Cameron Chalk, David Doty, David Haley, and David Soloveichik.
Conference
CMSB 2018:
Proceedings of the 16th International Conference on Computational Methods in Systems Biology,
(Prague, Czech Republic, Sept 1214, 2018), pp. 203219.
[ PDF 
BibTeX ]

Computational complexity of atomic chemical reaction networks.
David Doty and Shaopeng Zhu.
Journal
NaCo 2018: Natural Computing, 17(1): 97108 (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. 212226.
[ PDF 
BibTeX ]

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 2428, 2017), pp. 249266.
[ PDF 
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 1014, 2017), pp. 141:1141:14.
[ PDF 
arXiv 
BibTeX 
DOI ]

Democratic, existential, and consensusbased output conventions in stable computation by chemical reaction networks.
Robert Brijder, David Doty, and David Soloveichik.
Journal
NaCo 2018: Natural Computing, 17(1): 97108 (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 48, 2016), pp. 5266.
[ PDF 
BibTeX 
DOI ]

Design of geometric molecular bonds.
David Doty and Andrew Winslow.
Journal
TMBMC 2017: IEEE Transactions on Molecular, Biological, and MultiScale Communications 3(1):1323. Invited paper.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
ISIT 2016: Proceedings of the 2016 IEEE International Symposium on Information Theory, (Barcelona, Spain, July 1015, 2016), pp. 17891793.
[ PDF 
BibTeX 
DOI ]

Stable leader election in population protocols requires linear time.
David Doty and David Soloveichik.
Journal
DIST 2018: Distributed Computing, 31(4):257271. 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 59, 2015), pp. 602616.
[ PDF 
BibTeX 
DOI ]

Pattern overlap implies runaway growth in hierarchical tile systems.
HoLin Chen, David Doty, Ján Maňuch, Arash Rafiey, and Ladislav Stacho.
Journal
JoCG 2016: Journal of Computational Geometry 7(2):318, 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 2225, 2015), pp. 360373.
[ PDF 
BibTeX 
DOI ]

Designing ordered nucleic acid selfassembly processes.
[β] Rebecca Schulman and David Doty.
Journal
COSTBI 2015: Current Opinion in Structural Biology 31: 5763, 2015. Invited review article.
[ PDF 
BibTeX 
DOI ]

Speed faults in computation by chemical reaction networks.
HoLin Chen, Rachel Cummings, David Doty, and David Soloveichik.
Journal
DIST 2017: Distributed Computing 30(5): 373390, 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 1215, 2014), pp. 1630.
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):245261, 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 2226, 2014), pp. 3752.
[ PDF 
BibTeX 
DOI ]

Fast algorithmic selfassembly of simple shapes using random agitation.
HoLin 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 2226, 2014), pp. 2036.
[ PDF 
arXiv 
BibTeX 
DOI ]

Producibility in hierarchical selfassembly.
David Doty.
Journal
NaCo 2016: Natural Computing, 15(1):4149, 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 1418, 2014), pp. 142154.
[ PDF 
BibTeX ]

Rateindependent computation in continuous chemical reaction networks.
HoLin Chen, David Doty, and David Soloveichik.
Conference
ITCS 2014: Proceedings of the 5th Innovations in Theoretical Computer Science Conference,
(Princeton, New Jersey, USA, January 1214, 2014), pp. 313326.
[ PDF 
arXiv 
BibTeX 
DOI ]

Timing in chemical reaction networks.
David Doty.
Conference
SODA 2014: Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms,
(Portland, Oregon, USA, January 57, 2014), pp. 772784.
[ PDF 
arXiv 
BibTeX 
DOI ]

Leaderless deterministic chemical reaction networks.
David Doty and Monir Hajiaghayi.
Journal
NaCo 2015: Natural Computing 14(2):213223, 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 2327, 2013), pp. 4660.
[ PDF 
BibTeX 
DOI ]

Theory of algorithmic selfassembly.
David Doty.
Journal
CACM 2012: Communications of the ACM 55(12):7888, 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 2023, 2012), pp. 302310.
[ PDF 
arXiv 
BibTeX 
DOI ]

Deterministic function computation with chemical reaction networks.
HoLin Chen, David Doty, and David Soloveichik.
Journal
NaCo 2014: Natural Computing 13(4):517534, 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 1417, 2012),
pp. 2542.
[ PDF 
BibTeX 
DOI ]

Parallelism and time in hierarchical selfassembly.
HoLin Chen and David Doty.
Journal
SICOMP 2017: SIAM Journal on Computing 46(2):661709, 2017.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
SODA 2012: Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms,
(Kyoto, Japan, January 1719, 2012), pp. 11631182.
[ PDF 
BibTeX 
DOI ]

Program size and temperature in selfassembly.
HoLin Chen, David Doty, and Shinnosuke Seki.
Journal
Algorithmica 2015: Algorithmica 72(3):884899, 2015.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
ISAAC 2011: Proceedings of the 22nd International Symposium on Algorithms and Computation,
(Yokohama, Japan, December 58, 2011), LNCS 7074, pp. 445453.
[ PDF 
BibTeX 
DOI ]

The power of nondeterminism in selfassembly.
Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
Journal
ToC 2013: Theory of Computing 9(1):129, 2013.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
SODA 2011: Proceedings of the 22nd Annual ACMSIAM
Symposium on Discrete Algorithms,
(San Francisco, California, USA, January 2325, 2011), pp. 590602.
[ PDF 
BibTeX 
DOI ]

Strong faulttolerance for selfassembly 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 2326, 2010), pp. 417426.
[ PDF 
arXiv 
BibTeX 
DOI ]

Scalable, timeresponsive, digital, energyefficient 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 1417, 2010)
pp. 2536.
[ PDF 
arXiv 
BibTeX 
DOI ]

Negative interactions in irreversible selfassembly.
David Doty, Lila Kari, and Benoît Masson.
Journal
Algorithmica 2013: Algorithmica 66(1):153172, 2013.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
DNA 2010: Proceedings of the 16th International
Meeting on DNA Computing and Molecular Programming,
(Hong Kong, China, June 1417, 2010)
pp. 3748.
[ PDF 
BibTeX 
DOI ]

Intrinsic universality in selfassembly.
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 46, 2010), pp. 275286.
[ PDF 
arXiv 
BibTeX 
DOI ]

Randomized selfassembly for exact shapes.
David Doty.
Journal
SICOMP 2010: SIAM Journal on Computing 39(8):35213552, 2010.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
FOCS 2009: Proceedings of the 50th Annual IEEE
Symposium on Foundations of Computer Science,
(Atlanta, Georgia, USA, October 2427, 2009), pp. 8594.
[ PDF 
BibTeX 
DOI ]

Random number selection in selfassembly.
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 711, 2009), pp. 143157.
[ PDF 
BibTeX 
DOI ]

A domainspecific 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 811, 2009)
pp. 2534.
[ PDF 
arXiv 
BibTeX 
DOI ]

Limitations of selfassembly at temperature 1.
David Doty, Matthew J. Patitz, and Scott M. Summers.
Journal
TCS 2011: Theoretical Computer Science 412(12):145158, 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 811, 2009),
pp. 3544.
[ PDF 
BibTeX 
DOI ]

Feasible depth.
David Doty and Philippe Moser.
Conference
CiE 2007:
3rd Conference of
Computability in Europe,
(Siena, Italy, June 1823, 2007),
pp. 228237.
[ 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):740755, 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 truthtable 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 truthtable degrees.
CiE 2007:
3rd Conference of
Computability in Europe,
(Siena, Italy, June 1823, 2007),
pp. 6372.
[ PDF 
BibTeX 
DOI ]

Pushdown dimension.
David Doty and Jared Nichols.
Journal
TCS 2007: Theoretical Computer Science 381(13):105123, 2007.
[ PDF 
arXiv 
BibTeX 
DOI ]

Finitestate dimension and real arithmetic.
David Doty, Jack H. Lutz, and Satyadev Nandakumar.
Journal
I&C 2007: Information and Computation 205(11):16401651, 2007.
[ PDF 
arXiv 
BibTeX 
DOI ]
Conference
ICALP 2006: Proceedings of the 33^{rd} International Colloquium on
Automata, Languages and Programming,
(Venice, Italy, July 916, 2006), SpringerVerlag,
2006, pp. 537547.
[ PDF 
BibTeX 
DOI ]

Dimension extractors and optimal decompression.
David Doty.
Journal
ToCS 2008: Theory of Computing Systems 43(34):425463, 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,
SpringerVerlag, 2006, pp. 153162.
[ PDF 
BibTeX 
DOI ]

Zetadimension.
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),
SpringerVerlag, 2005, pp. 283294.
[ PDF 
arXiv 
BibTeX 
DOI ]

Nonlocal evolutionary adaptation in gridplants.
David Doty.
Conference
CEC 2004: Proceedings of the 2004 IEEE Congress on Evolutionary
Computation, IEEE, 2004, pp. 16021609.
[ 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. 15751581.
[ PDF 
BibTeX 
DOI ]
Unrefereed Technical Reports

Efficient size estimation and impossibility of termination in uniform dense population protocols.
David Doty and Mahsa Eftekhari.
Technical Report 1808.08913, arXiv, 2018.
[ PDF 
arXiv ]

An oracle strongly separating deterministic time from nondeterministic time, via Kolmogorov complexity.
David Doty.
Technical Report 1004.3993, arXiv, 2010.
[ PDF 
arXiv 
BibTeX ]

Finitestate dimension and lossy decompressors.
David Doty and Philippe Moser.
Technical Report cs.CC/0609096, arXiv, 2006.
[ PDF 
arXiv 
BibTeX ]
Invited book chapters

Hierarchical selfassembly.
David Doty.
Encyclopedia of Algorithms, pp. 903909, 2016.
[ PDF 
BibTeX 
DOI
]

Randomized selfassembly.
David Doty.
Encyclopedia of Algorithms, pp. 17591767, 2016.
[ PDF 
BibTeX 
DOI
]
Ph.D. Thesis

David Doty.
Applications of the theory of computation to nanoscale selfassembly.
Ph.D. Thesis, Iowa State University, 2009.
[ PDF 
BibTeX ]
Invited Talks

Thermodynamic binding networks: How to selfassemble molecules reliably without knowing too much about them
Unconventional Computation and Natural Computation,
Workshop on SelfAssembly, Geometry, and Computation,
Fontainebleau, France, June 2018.

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.

DNA tile selfassembly.
DNA 2017: 23rd International Conference on DNA Computing and Molecular Programming,
Austin, Texas, USA, Sept 2017.
Tutorial.

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é ParisSud, Jul 2017.
Invited Talk, April 2016.
[ 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 NonSpatial 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 ReedSolomon
Workshop on Coding Techniques for Synthetic Biology,
University of Illinois at UrbanaChampaign,
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:
28^{th} 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 selfassembly with DNA tiles.
DNA 2011:
17^{th} International Conference on DNA Computing and Molecular Programming,
Pasadena, CA,
Tutorial,
September 2011.
[ ODP 
PPT ]

The state of algorithmic selfassembly at Iowa State.
FNANO 2010:
7^{th} Annual Foundations of Nanoscience Conference,
Snowbird, UT,
Invited Talk,
April 2010.
[ ODP 
PPT ]

Coevolution and nonlocal adaptation in gridplants.
Pioneer HiBred Bioinformatics Group, March 2004.
[ PDF 
PS ]
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 outofdate 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
rearranging 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.