David Doty



Publications

Note on author order: In all 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.

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 out-of-date 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 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.

  1. David Doty.
    Producibility in hierarchical self-assembly.
    UCNC 2014: Proceedings of the 13th International Conference on Unconventional Computation and Natural Computation, (London, Ontario, Canada, July 14-18, 2014), to appear.
    [ PDF | CoRR | BibTeX ]

  2. Ho-Lin Chen, David Doty, and David Soloveichik.
    Rate-independent computation in continuous chemical reaction networks.
    ITCS 2014
    : Proceedings of the 5th Innovations in Theoretical Computer Science Conference, (Princeton, New Jersey, USA, January 12-14, 2014), pp. 313-326.
    [ PDF | CoRR | BibTeX | DOI ]

  3. David Doty.
    Timing in chemical reaction networks.
    SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, (Portland, Oregon, USA, January 5-7, 2014), pp. 772-784.
    [ PDF | CoRR | BibTeX | DOI ]

  4. 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 23-27, 2013), pp. 46-60.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

  5. 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 20-23, 2012), pp. 302-310.
    [ PDF | CoRR | BibTeX | DOI ]

  6. Ho-Lin 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 14-17, 2012), Lecture Notes in Computer Science, volume 7433, Springer-Verlag, 2012, pp. 25-42.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

  7. Ho-Lin Chen and David Doty.
    Parallelism and time in hierarchical self-assembly.
    SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, (Kyoto, Japan, January 17-19, 2012), pp. 1163-1182.
    [ PDF | CoRR | BibTeX | DOI ]

  8. Ho-Lin Chen, David Doty, and Shinnosuke Seki.
    Program size and temperature in self-assembly.
    ISAAC 2011
    : Proceedings of the 22nd International Symposium on Algorithms and Computation, (Yokohama, Japan, December 5-8, 2011), LNCS 7074, pp. 445-453.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

  9. Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
    The power of nondeterminism in self-assembly.
    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 | CoRR | BibTeX | DOI | Journal Version ]

  10. David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, and Scott M. Summers.
    Strong fault-tolerance for self-assembly with fuzzy temperature.
    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 | CoRR | BibTeX | DOI ]

  11. Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki.
    Scalable, time-responsive, digital, energy-efficient molecular circuits using DNA strand displacement.
    DNA 2010: Proceedings of the 16th International Meeting on DNA Computing and Molecular Programming, (Hong Kong, China, June 14-17, 2010) Lecture Notes in Computer Science, volume 6518, Springer-Verlag, 2010, pp. 25-36.
    [ PDF | CoRR | BibTeX | DOI ]

  12. David Doty, Lila Kari, and Benoît Masson.
    Negative interactions in irreversible self-assembly.
    DNA 2010
    : Proceedings of the 16th International Meeting on DNA Computing and Molecular Programming, (Hong Kong, China, June 14-17, 2010) Lecture Notes in Computer Science, volume 6518, Springer-Verlag, 2010, pp. 37-48.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

  13. David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods.
    Intrinsic universality in self-assembly.
    STACS 2010: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, (Nancy, France, March 4-6, 2010), pp. 275-286.
    [ PDF | CoRR | BibTeX | DOI ]

  14. David Doty.
    Randomized self-assembly for exact shapes.
    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 | CoRR | BibTeX | DOI | Journal Version ]

  15. David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods.
    Random number selection in self-assembly.
    UC 2009: Proceedings of the 8th International Conference on Unconventional Computation, (Ponta Delgada, Portugal, September 7-11, 2009), pp. 143-157.
    [ PDF | BibTeX | DOI ]

  16. David Doty and Matthew J. Patitz.
    A domain-specific 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 8-11, 2009) Lecture Notes in Computer Science, volume 5877, Springer-Verlag, 2009, pp. 25-34.
    [ PDF | CoRR | BibTeX | DOI ]

  17. David Doty, Matthew J. Patitz, and Scott M. Summers.
    Limitations of self-assembly at temperature 1.
    DNA 2009
    : Proceedings of The 15th International Meeting on DNA Computing and Molecular Programming, (Fayetteville, Arkansas, USA, June 8-11, 2009), Lecture Notes in Computer Science, volume 5877, Springer-Verlag, 2009, pp. 35-44.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

  18. 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 18-23, 2007), Proceedings, Lecture Notes in Computer Science, volume 4497, Springer-Verlag, 2007, pp. 228-237.
    [ PDF | CoRR | BibTeX | DOI ]

  19. Laurent Bienvenu, David Doty, and Frank Stephan.
    Constructive dimension and weak truth-table 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 18-23, 2007), Proceedings, Lecture Notes in Computer Science, volume 4497, Springer-Verlag, 2007, pp. 63-72.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

  20. David Doty, Jack H. Lutz, and Satyadev Nandakumar.
    Finite-state dimension and real arithmetic.
    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 | CoRR | BibTeX | DOI | Journal Version ]

  21. 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, Springer-Verlag, 2006, pp. 153-162.
    [ PDF | CoRR | BibTeX | DOI | Journal Version ]

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

  23. David Doty.
    Non-local evolutionary adaptation in gridplants.
    CEC 2004: Proceedings of the 2004 IEEE Congress on Evolutionary Computation, IEEE, 2004, pp. 1602-1609.
    [ PDF | BibTeX | DOI ]

  24. 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. 1575-1581.
    [ PDF | BibTeX | DOI ]

Journal Papers

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

  2. Ho-Lin Chen, David Doty, and Shinnosuke Seki.
    Program size and temperature in self-assembly.
    Algorithmica 2014
    : Algorithmica to appear.
    [ PDF | CoRR | BibTeX | DOI | Conference Version ]

  3. Ho-Lin 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 ]

  4. David Doty, Lila Kari, and Benoît Masson.
    Negative interactions in irreversible self-assembly.
    Algorithmica 2013
    : Algorithmica 66(1): 153-172, 2013.
    [ PDF | CoRR | BibTeX | DOI | Conference Version ]

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

  6. David Doty.
    Theory of algorithmic self-assembly.
    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.



    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>
        
  7. David Doty, Matthew J. Patitz, and Scott M. Summers.
    Limitations of self-assembly at temperature 1.
    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 | CoRR | BibTeX | DOI | Conference Version ]

  8. David Doty.
    Randomized self-assembly for exact shapes.
    SICOMP 2010
    : SIAM Journal on Computing 39(8):3521-3552, 2010.
    [ PDF | CoRR | BibTeX | DOI | Conference Version ]

  9. Laurent Bienvenu, David Doty, and Frank Stephan.
    Constructive dimension and Turing degrees.
    ToCS 2009
    : Theory of Computing Systems 45(4):740-755, 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 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 CoRR.

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

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

  12. David Doty and Jared Nichols.
    Pushdown dimension.
    TCS 2007: Theoretical Computer Science 381(1-3):105-123, 2007.
    [ PDF | CoRR | BibTeX | DOI ]

Ph.D. Thesis

Invited Talks

  1. Deterministic function computation with chemical reaction networks.
    University of British Columbia, Department of Computer Science, Seminar Talk, September 2012.
    [ ODP | PDF ]

  2. Deterministic computation with chemical reaction networks.
    Aalto University, Department of Information and Computer Science, ICS Forum, June 2012.
    [ ODP | PDF ]

  3. Algorithmic self-assembly with DNA tiles.
    DNA 2011: Tutorial, 17th International Meeting on DNA Computing and Molecular Programming, September 2011.
    [ ODP | PPT ]

  4. The state of algorithmic self-assembly at Iowa State.
    FNANO 2010: 7th Annual Foundations of Nanoscience Conference, April 2010.
    [ ODP | PPT ]

  5. Coevolution and non-local adaptation in gridplants.
    Pioneer Hi-Bred Bioinformatics Group, March 2004.
    [ PDF | PS ]

Unrefereed Technical Reports

  1. 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 ]

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