David Doty
Publications
Note on author order: In all 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.
My
DBLP page is an automatically generated
index that tracks (some) computer science publication venues.
Google Scholar automatically tracks my publications, including citation counts.
However, the page you are currently reading represents my official list of publications.
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.
Refereed Conference Papers
The PDF document links here are preprints, similar to what
was submitted to the conference, with appendices containing material that
did not fit in the page limit. The
Computing Research Repository
(CoRR) link references a publicly archived version of the paper
that is possibly more outofdate than the files hosted on this server.
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.

David Doty.
Producibility in hierarchical selfassembly.
UCNC 2014: Proceedings of the 13th International Conference on Unconventional Computation and Natural Computation, (London, Ontario, Canada, July 1418, 2014), to appear.
[ PDF 
CoRR 
BibTeX ]

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

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

David Doty and Monir Hajiaghayi.
Leaderless deterministic chemical reaction networks.
DNA 2013: Proceedings of the 19th International
Meeting on DNA Computing and Molecular Programming, (Tempe, Arizona, USA, Sept 2327, 2013), pp. 4660.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods.
The tile assembly model is intrinsically universal.
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 
CoRR 
BibTeX 
DOI ]

HoLin Chen, David Doty, and David Soloveichik.
Deterministic function computation with chemical reaction networks.
DNA 2012: Proceedings of the 18th International
Meeting on DNA Computing and Molecular Programming, (Aarhus, Denmark, August 1417, 2012),
Lecture Notes in Computer Science, volume 7433, SpringerVerlag, 2012, pp. 2542.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

HoLin Chen and David Doty.
Parallelism and time in hierarchical selfassembly.
SODA 2012: Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms,
(Kyoto, Japan, January 1719, 2012), pp. 11631182.
[ PDF 
CoRR 
BibTeX 
DOI ]

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

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

David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, and Scott M. Summers.
Strong faulttolerance for selfassembly with fuzzy temperature.
FOCS 2010: Proceedings of the 51st Annual IEEE
Symposium on Foundations of Computer Science,
(Las Vegas, Nevada, USA, October 2326, 2010), pp. 417426.
[ PDF 
CoRR 
BibTeX 
DOI ]

Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
Scalable, timeresponsive, digital, energyefficient molecular circuits using DNA strand displacement.
DNA 2010: Proceedings of the 16th International
Meeting on DNA Computing and Molecular Programming,
(Hong Kong, China, June 1417, 2010)
Lecture Notes in Computer Science, volume 6518, SpringerVerlag, 2010, pp. 2536.
[ PDF 
CoRR 
BibTeX 
DOI ]

David Doty, Lila Kari, and Benoît Masson.
Negative interactions in irreversible selfassembly.
DNA 2010: Proceedings of the 16th International
Meeting on DNA Computing and Molecular Programming,
(Hong Kong, China, June 1417, 2010)
Lecture Notes in Computer Science, volume 6518, SpringerVerlag, 2010, pp. 3748.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods.
Intrinsic universality in selfassembly.
STACS 2010: Proceedings of the 27th International Symposium on
Theoretical Aspects of Computer Science,
(Nancy, France, March 46, 2010), pp. 275286.
[ PDF 
CoRR 
BibTeX 
DOI ]

David Doty.
Randomized selfassembly for exact shapes.
FOCS 2009: Proceedings of the 50th Annual IEEE
Symposium on Foundations of Computer Science,
(Atlanta, Georgia, USA, October 2427, 2009), pp. 8594.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods.
Random number selection in selfassembly.
UC 2009: Proceedings of the 8th International
Conference on Unconventional Computation,
(Ponta Delgada, Portugal, September 711, 2009), pp. 143157.
[ PDF 
BibTeX 
DOI ]

David Doty and Matthew J. Patitz.
A domainspecific language for programming in the tile assembly model.
DNA 2009: Proceedings of The 15th International
Meeting on DNA Computing and Molecular Programming,
(Fayetteville, Arkansas, USA, June 811, 2009)
Lecture Notes in Computer Science, volume 5877, SpringerVerlag, 2009, pp. 2534.
[ PDF 
CoRR 
BibTeX 
DOI ]

David Doty, Matthew J. Patitz, and Scott M. Summers.
Limitations of selfassembly at temperature 1.
DNA 2009: Proceedings of The 15th International
Meeting on DNA Computing and Molecular Programming,
(Fayetteville, Arkansas, USA, June 811, 2009),
Lecture Notes in Computer Science, volume 5877, SpringerVerlag, 2009, pp. 3544.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty and Philippe Moser.
Feasible depth.
CiE 2007: S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (editors),
Computation and Logic in the Real World  3rd Conference of
Computability in Europe,
(Siena, Italy, June 1823, 2007),
Proceedings, Lecture Notes in Computer Science, volume 4497,
SpringerVerlag, 2007, pp. 228237.
[ PDF 
CoRR 
BibTeX 
DOI ]

Laurent Bienvenu, David Doty, and Frank Stephan.
Constructive dimension and weak truthtable degrees.
CiE 2007: S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (editors),
Computation and Logic in the Real World  3rd Conference of
Computability in Europe,
(Siena, Italy, June 1823, 2007),
Proceedings, Lecture Notes in Computer Science, volume 4497,
SpringerVerlag, 2007, pp. 6372.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty, Jack H. Lutz, and Satyadev Nandakumar.
Finitestate dimension and real arithmetic.
ICALP 2006: Proceedings of the 33^{rd} International Colloquium on
Automata, Languages and Programming,
(Venice, Italy, July 916, 2006), SpringerVerlag,
2006, pp. 537547.
[ PDF 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty.
Every sequence is decompressible from a random one.
CiE 2006: Arnold Beckmann, Ulrich Berger, Benedikt Löwe, and John V Tucker
(editors): 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 
CoRR 
BibTeX 
DOI 
Journal Version ]

David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser.
Zetadimension.
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 
CoRR 
BibTeX 
DOI ]

David Doty.
Nonlocal evolutionary adaptation in gridplants.
CEC 2004: Proceedings of the 2004 IEEE Congress on Evolutionary
Computation, IEEE, 2004, pp. 16021609.
[ PDF 
BibTeX 
DOI ]

Dan Ashlock, Dean C. Adams, and David Doty.
Morphometric grayscale texture analysis using foot patterns.
CEC 2003: Proceedings of the 2003 IEEE Congress on Evolutionary
Computation, IEEE, 2003, pp. 15751581.
[ PDF 
BibTeX 
DOI ]
Journal Papers

David Doty and Monir Hajiaghayi.
Leaderless deterministic chemical reaction networks.
NaCo 2014: Natural Computing, to appear.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

HoLin Chen, David Doty, and Shinnosuke Seki.
Program size and temperature in selfassembly.
Algorithmica 2014: Algorithmica to appear.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

HoLin Chen, David Doty, and David Soloveichik.
Deterministic function computation with chemical reaction networks.
NaCo 2013: Natural Computing to appear. Special issue of
invited papers from DNA 2012.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

David Doty, Lila Kari, and Benoît Masson.
Negative interactions in irreversible selfassembly.
Algorithmica 2013: Algorithmica 66(1): 153172, 2013.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
The power of nondeterminism in selfassembly.
ToC 2013: Theory of Computing 9(1): 129, 2013.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

David Doty.
Theory of algorithmic selfassembly.
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.
To embed this video into a website, use this code:
<iframe src="http://player.vimeo.com/video/54214122?badge=0" width="50%" height="37%"
frameborder="0" webkitAllowFullScreen mozallowfullscreen allowFullScreen></iframe>

David Doty, Matthew J. Patitz, and Scott M. Summers.
Limitations of selfassembly at temperature 1.
TCS 2011: Theoretical Computer Science 412(12):145158, 2011. Special issue of
invited papers from Complexity of Simple Programs workshop, Cork, Ireland, 2008.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

David Doty.
Randomized selfassembly for exact shapes.
SICOMP 2010: SIAM Journal on Computing 39(8):35213552, 2010.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

Laurent Bienvenu, David Doty, and Frank Stephan.
Constructive dimension and Turing degrees.
ToCS 2009: Theory of Computing Systems 45(4):740755, 2009. Special issue of
invited papers from Computability in Europe 2007.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]
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 CoRR.

David Doty.
Dimension extractors and optimal decompression.
ToCS 2008: Theory of Computing Systems 43(34):425463, 2008. Special issue of
invited papers from Computability in Europe 2006.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

David Doty, Jack H. Lutz, and Satyadev Nandakumar.
Finitestate dimension and real arithmetic.
I&C 2007: Information and Computation 205(11):16401651, 2007.
[ PDF 
CoRR 
BibTeX 
DOI 
Conference Version ]

David Doty and Jared Nichols.
Pushdown dimension.
TCS 2007: Theoretical Computer Science 381(13):105123, 2007.
[ PDF 
CoRR 
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

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: Tutorial, 17^{th} International
Meeting on DNA Computing and Molecular Programming, September 2011.
[ ODP 
PPT ]

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

Coevolution and nonlocal adaptation in gridplants.
Pioneer HiBred Bioinformatics Group, March 2004.
[ PDF 
PS ]
Unrefereed Technical Reports

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

David Doty and Philippe Moser.
Finitestate dimension and lossy decompressors.
Technical Report cs.CC/0609096, Computing Research Repository, 2006.
[ PDF 
CoRR 
BibTeX ]