Damien
Damien Woods
Hamilton Institute

I'm a scientist and Professor at the Hamilton Institute and the Department of Computer Science, Maynooth University. Email: damien.woodsmu.ie

Research group webpage

Read about our research and group members.

Publications by topic:

Current funding:

EIC: DISCO: DNA based Infrastructure for Storage and COmputation (EIC Pathfinder)
SFI: Active DNA tiles for programmable nucleation of robust DNA nanostructures (SFI-FFP award)
ERC: Active-DNA: Computationally active DNA nanostructures (ERC Consolidator)
SFI: ERC-Support Award

Previous funding:

NSF: Scaling up programmable and algorithmic DNA self-assembly. Winfree, Yin, Woods, Doty.
NASA: Simple self-replicating nanostructures. Woods.
NSF: Theory of molecular programming: computability and complexity. Doty, Woods.

Prior lives:

Inria: I led a research group at Inria, Paris, France, 2016-2018.
Caltech: I spent 7 years at Caltech, USA (2009-2016). I finished up there as a Senior Research Fellow in Computing and Mathematical Sciences, and a Molecular Programming Fellow working, with Erik Winfree and Shuki Bruck, in the Department of Computing and Mathematical Sciences and affiliated with the Center for the Mathematics of Information.
Seville: I was a postdoc in the Research Group on Natural Computing at the University of Seville, Spain.
UCC: At University College Cork I was a postdoc at the Boole Centre For Research in Informatics and the School of Mathematics with Tony Seda, and the Cork Complex Systems Lab (CCSL) with Gregory Provan.
Maynooth: PhD at the Department of Computer Science.

       


News!

This news ticker is old hat ... please see our group page for more recent news and blog posts!

Paper on the theory of molecular robotics! We present a new theoretical model of computation for molecular robotics thats as simple as we could make it, yet does interesting stuff. [blog post and videos].

Paper showing that the Collatz (3x+1) process embeds a base conversion algorithm! To appear at RP2020.

Paper on theoretical tile-assembly: long self-assembled structures (paths) are either pumpable or blockable! Accepted to STOC 2020. Feb 2020.

Slides on our work on reprogrammable DNA self-assembly. Jan 2020.

Paper in Nature: Reprogrammable DNA self-assembly. Our set of 355 DNA tiles can run any 6-bit Boolean circuit of a certain kind: we ran 21 circuits on over 100 inputs! Then we did some theory showing the n-bit model simulates Rule 110 and arbitrary Boolean circuits. Mar 2019.

We're advertising two ERC-funded postdoc jobs. Sound exciting? More info: join us. Feb 2019.


ERC
Our newly-funded ERC Consolidator project: Active DNA. €2.35M of funding for molecular computing over the next five years. We're hiring! Nov 2018.

SFI
Received Science Foundation Ireland (SFI) funding of €656k to build a new lab and carry out work on molecular computing. Nov 2018.

SFI
Our group has moved to the Hamilton Institute and the Department of Computer Science at Maynooth University. We bid a sad farewell to Inria, a wonderful place to do science, and look forward to building our new group and lab in Ireland.

New experimental paper: a DNA robot that sorts distinct molecules into distinct piles by randomly walking around a 2D surface. Accepted to Science.

Two submissions accepted to DNA23; experiments on algorithmic self-assembly with DNA tiles, and theory of a new thermodynamic model of computation!

Research talks about DNA experiments on algorithmic self assembly at FNANO, and DNA-based self-replicators at OCAV.

No-go results for tile-assembly: no intrinsic universality nor bounded Turing machine simulation at temperature 1. Accepted to STOC 2017.

Teaching: a week of theory & experiments, ER02, ENS Lyon. Theory slides.

Pierre-Étienne Meunier joins TAPDANCE@Inria. Woohoo!

DNA22 Track A proceedings are available online as LNCS vol 9818.

Wee overviews on nubots and intrinsic universality for the Springer Encyclopedia of Algorithms.

DNA22 accepted papers for Tracks A & B announced.

I've moved to Inria, Paris.

A survey paper on intrinsic universality in self-assembly. Phil. Trans. Royal Soc A, 2015.

Visited Paris 7 (LIAFA) for April 2015, giving talks at Lab. Jean Perrin at Paris 6, and Lifeware at Inria.

Gave a talk to on our experimental work on building self-replicating DNA nanostructures. American Physical Society (APS) March meeting, 2015.

Our paper showing infinite hierarchies of power in the hierarchical self-assembly model is published in Algorithmica. Feb 2015

For the month of September, '14, I visited LIAFA, a CNRS and University Paris 7 lab.

Talk on intrinsic universality in self-assembly (part A, part B), CoA workshop, Paris 7. See related talks by Andrew (part B), Florent, Pierre-Étienne, and Shinnosuke.

Computing by jiggling: our paper shows that the kind of random movements seen at the molecular scale can be exploited to rapidly build simple shapes.

Slides from an invited workshop talk at UCNC 2014.

After an epic journey, The Precious finds a home: ICALP 2014!

Gave an invited talk at a Royal Society meeting in the UK.

Congrats to Moya for winning best student paper award at DNA19!

Our paper on temperature 1 and intrinsic universality was accepted to SODA 2014.

New paper and slides for an invited talk at MCU 2013: A journey through our work on intrinsic universality in self-assembly (no Hobbits were harmed).

New paper: on the computational complexity of molecular motors. Accepted to DNA19.

NASA
To boldly go ... Awarded NASA grant to study molecular self-replicators.

Paper on AND circuits, OR circuits was accepted to MCU.

Our paper on intrinsic universality in two-handed (hierarchical) tile assembly was accepted to ICALP 2013.

New paper: Temperature 1 tile assembly is not capable of simulating arbitrary tile assembly systems

New paper on archaemathematics: Wang B machines & an electromechanical toy

Slides on active self-assembly. Presented at ITCS 2013.

New paper: Nubots: Active self-assembly in polylog time

New paper: The One

New paper: OR circuits and AND circuits

Video and Slides describing how the tile assembly model is intrinsically universal, given at FOCS 2012.

Slides from a tutorial on the theory of molecular computing given at the DNA18 conference.

Our paper on intrinsic universality in tile assembly was accepted to FOCS 2012.

Tom and I discuss the future of optical computing in a News and Views in Nature Physics.

Video and slides of a recent talk on the time complexity of small universal Turing machines, tag systems and Rule 110.


Publications by topic
[α] = Alphabetical author order

Experimental: Molecular computers, DNA nanostructures

Damien Woods*, David Doty*, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, Erik Winfree (*Joint first authors)
Diverse and robust molecular algorithms using reprogrammable DNA self-assembly
Nature 567:366-372. 2019 [pdf], [bib]
Supplementary Info A (theory, design, results), Suppl Info B (DNA sequences), Suppl Info C (Sample data); Sequence design code, AFM images and analysis code, Raw data (Bruker file format).
Presentation: Keynote at DNA26
Media: The Irish Times, Chemistry World, PhysicsWorld, Wired, IEEE Spectrum, Silicon Republic, Europa Press (in Spanish), Nature Asia, The California Aggie.
Live interviews: Futureproof on Newstalk radio, short video interview, The Wider View on Northern Sound.
Press releases: Maynooth University, Inria (in French), Caltech, UC Davis.
An art exhibition with some quirky visitors. Erik's blurbification.


Anupama J. Thubagere, Wei Li, Robert F. Johnson,Zibo Chen, Shayan Doroudi, Yae Lim Lee, Gregory Izatt, Sarah Wittman, Niranjan Srinivas, Damien Woods, Erik Winfree, Lulu Qian
A cargo-sorting DNA robot
Science 357(6356). 2017 [paper] [Supplementary material]


Theory: Algorithms for nucleic acid (DNA/RNA) prediction

Ahmed Shalaby, Chris Thachuk, Damien Woods
Minimum free energy, partition function and kinetics simulation algorithms for a multistranded scaffolded DNA computer
DNA29: The 29th International Conference on DNA Computing and Molecular Programming
Schloss Dagstuhl—Leibniz-Zentrum für Informatik LIPIcs:1:1--1:22, 2023,
[Open Access full paper], [bib]

Theory: Self-assembly, intrinsic universality

[α] Matthew Cook, Tristan Stérin, Damien Woods
Small tile sets that compute while solving mazes.
DNA27: Proceedings of the 27th International Conference on DNA Computing and Molecular Programming. LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum für Informatik. 205:8:1--8:20, 2021.
[LIPIcs version], Full [arxiv] version.

[α] Pierre-Étienne Meunier, Damien Regnault, Damien Woods
The program-size complexity of self-assembled paths.
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. June 2020, pp 727--737. Published ACM version. Full [arxiv] version, [pdf], [bib], YouTube video!

[α] David Doty, Trent Rogers, David Soloveichik, Chris Thachuk, Damien Woods
Thermodynamic Binding Networks.
DNA23: The 23rd International Conference on DNA Computing and Molecular Programming. Springer LNCS 10467:249-266, 2017. [pdf] [arxiv]

[α] Pierre-Étienne Meunier, Damien Woods
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation.
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pp. 328--341. Published ACM version. Full [arxiv] version, [pdf], [bib].

Damien Woods
Intrinsic universality and the computational power of self-assembly. (Survey article)
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 373(2046):20140214. Author copy: [pdf]
Conference version: MCU: Machines, Computations and Universality 2013, Zürich, Switzerland, Sept. 2013. Edited by Turlough Neary and Matthew Cook. Electronic Proceedings in Theoretical Computer Science 128, pp. 16-22. (Invited survey) [EPTCS]

[α] Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods
One tile to rule them all: simulating any Turing machine, tile assembly system, or tiling system with a single puzzle piece.
ICALP: 41st International Colloquium on Automata, Languages and Programming. July, 2014. Springer LNCS 8572, pages 368-379. Copenhagen, Denmark. [arxiv]

[α] Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods
Intrinsic universality in tile self-assembly requires cooperation.
SODA: Proceedings of the 25th SIAM Symposium on Discrete Algorithms, 2014, 752--771. [pdf] [arxiv] [Short version]

[α] Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods
The two-handed tile assembly model is not intrinsically universal. Algorithmica. 2016, 74(2):812-850.
ICALP: 40th International Colloquium on Automata, Languages and Programming. Proceedings, part 1. July, 2013. Springer LNCS 7965, pages 400-412. Riga, Latvia [pdf] [arxiv]

[α] D.S. Doty, J.H. Lutz, M.J. Patitz, R.T. Schweller, S.M. Summers, D.Woods.
The tile assembly model is intrinsically universal
FOCS 2012: The 53rd Annual Symposium on Foundations of Computer Science. Oct 20-23. IEEE. pp 302-310. [arxiv] [pdf] [Erik's blurbification]

[α] D.S. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D.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). [pdf] [arxiv]

[α] D.S. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D.Woods
Random number selection in self-assembly.
UC 2009: Eighth International Conference on Unconventional Computation, Ponta Delgada (Azores), Portugal. Springer LNCS, vol 5715 , pp 143-157. [pdf]


Theory: molecular robots, active self-assembly

Irina Kostitsyna, Cai Wood, Damien Woods
Turning machines: a simple algorithmic model for molecular robotics.
Natural Computing. Open Access. 2022. doi: 10.1007/s11047-022-09880-8, [bib], [Full arXiv version], [blog post and videos].
Earlier conference version: DNA26: The 26th International Conference on DNA Computing and Molecular Programming. 2020. LIPIcs vol 174, pages 11:1-11:21.

[α] Ho-Lin Chen, David Doty, Dhiraj Holden, Chris Thachuk, Damien Woods, Chun-Tao Yang.
Fast algorithmic self-assembly of simple shapes using random agitation.
DNA20: The 20th International Conference on DNA Computing and Molecular Programming. Sept. 2014. Springer LNCS 8727, pages 20-36.
[LNCS] [arxiv]

Moya Chen, Doris Xin, Damien Woods.
Parallel computation using active self-assembly.
Natural Computing, 14(2):225-250. 2015. Journal [arxiv]
Conference version: DNA19: The 19th International Conference on DNA Computing and Molecular Programming. Sept. 2013. Springer LNCS 8141:16-30. [short version]
(Moya won the Best Student Paper award!)

Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, Peng Yin.
Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time.
ITCS 2013: Innovations in Theoretical Computer Science. Berkeley, California, pages 353-354, Jan. 2013. Full paper: [pdf], [arxiv], [blurbification], [Slides]. ACM 2-page extended abstract: [ACM].


Theory: Small universal Turing machines, Rule 110, simple universal systems, Collatz

Tristan Stérin, Damien Woods
Hardness of Busy Beaver Value BB(15)
RP2024: 16th International Conference on Reachability Problems 2024. Springer LNCS 15050:120-137
arXiv version: [arXiv:2107.12475] [cs.LO] [in-browser simulator] [simulator source code] [bib] [blog post]

Tristan Stérin, Damien Woods
The Collatz process embeds a base conversion algorithm
RP2020: 14th International Conference on Reachability Problems. 2020. Springer LNCS 12448:131-147
[arXiv:2007.06979] [cs.DM]

D. Woods and T. Neary.
Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines. Fundamenta Informaticae, 138(1-2):251-258, 2015. [pdf]

T. Neary and D. Woods.
Maurice Margenstern's Contributions to the Field of Small Universal Turing Machines. In Andrew Adamatzky (ed.) Automata, Universality, Computation - Tribute to Maurice Margenstern, pages 117--126, 2015, Springer.

T. Neary, D. Woods, N. Murphy, R. Glaschick.
Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy.
Journal of Complexity. Oct, 2014. 30(5):634-646
[arXiv:1304.0053] [cs.CC]
Conference version: R. Glaschick, T. Neary, D. Woods, N. Murphy: Hasenjaeger's electromechanical small universal Turing machine is time efficient. Turing in Context II. Oct 10-12, 2012. Abstract, page 22. Brussels, Belgium.

T. Neary, D. Woods.
The complexity of small universal Turing machines: A survey.
SOFSEM 2012: 38th Intl. Conf. on Current Trends in Theory and Practice of Computer Science. Špindlerův Mlýn, Czech Republic. January, 2012. Springer LNCS 7147:385-405. [arxiv]
Older version: D. Woods, T. Neary, "The complexity of small universal Turing machines: A survey". Theoretical Computer Science 410(4-5):443-450, 2009. (Invited) [pdf]
Even older version: D. Woods, T. Neary, "The complexity of small universal Turing machines", CiE 2007: Conference of Computability in Europe, Siena, Italy, June 2007. Springer LNCS vol. 4497. S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (editors).

T. Neary, D. Woods.
Small weakly universal Turing machines.
FCT 2009 - 17th International Symposium on Fundamentals of Computation Theory, Wrocław, Poland. Springer LNCS, vol. 5699: 262-273. M. Kutylowski, M. Gebala, W. Charatonik (editors). [pdf], arXiv version: [arxiv] [cs.CC] July 2007

D. Woods, T. Neary.
Small semi-weakly universal Turing machines.
Journal version: Fundamenta Informaticae. 91:179-195 (2009). (Special issue for MCU.) [pdf] (Note that the pdf has incorrect page numbers)
Conference version: Machines, Computations, and Universality (MCU) 2007, Orléans, France. Springer LNCS, vol. 4664:303-315. J. Durand-Lose, M. Margenstern (editors). [pdf]

T. Neary, D. Woods.
Four small universal Turing machines.
Journal version: Fundamenta Informaticae. 91:123-144 (2009). (Special issue for MCU.) [pdf] (Note that the pdf has incorrect page numbers)
Conference version: Machines, Computations, and Universality (MCU) 2007, Orléans, France. Springer LNCS, vol. 4664:242-254 J. Durand-Lose, M. Margenstern (editors). [pdf]

D. Woods, T. Neary.
On the time complexity of 2-tag systems and small universal Turing machines.
FOCS - 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2006, Berkeley, California. pp 439-446. [pdf]

T. Neary, D. Woods.
P-completeness of cellular automaton Rule 110.
ICALP 2006 - International Colloquium on Automata Languages and Programming, Venice, Italy. Springer LNCS vol. 4051, part 1, pp 132-143. [pdf] [ps]

D. Woods, T. Neary.
Remarks on the computational complexity of small universal Turing machines.
MFCSIT 2006. Cork, Ireland. pp 334-338. [pdf]

T. Neary, D. Woods.
Small fast universal Turing machines
Theoretical Computer Science, 362(1-3): 171-195, 11 October 2006. [pdf]


Theory: Optical computing

D. Woods, T. J. Naughton
Optical computing: Photonic neural networks.
Nature Physics, News and Views, 8(4):257-259, April 2012. [pdf]

D. Woods, T. J. Naughton
Optical Computing.
Journal version: Applied Mathematics and Computation, 215(4): 1417-1430, October 2009. (Special issue on Physics and Computation) [pdf]
Conference version: Workshop on Physics and Computation, Vienna, August, 2008. Pre-proceedings published as CDMTCS Research Report 327 (July 2008). Invited. [pdf]

D. Woods, T. J. Naughton
Parallel and sequential optical computing.
International Workshop on Optical Supercomputing. Vienna, August 2008. Springer LNCS vol 5172, pp 70-86. [pdf]

T. J. Naughton, D. Woods
Optical Computing.
In R. Meyer ed., Encyclopedia of Complexity and System Science, Springer. 2009 (Invited survey chapter).

D. Woods
Optical computing and computational complexity.
UC'06 - Fifth International Conference on Unconventional Computation, York, UK 2006, Springer LNCS, vol 4135 , pp 27-40 [pdf] [ps], (invited.)

D. Woods
Upper bounds on the computational power of an optical model of computation.
ISAAC 2005 - The 16th Annual International Symposium on Algorithms and Computation, Sanya, Hainan, China, December 2005. Springer LNCS, vol 3827, pp 777-788. [pdf] [ps]

D. Woods, J. P. Gibson
Lower bounds on the computational power of an optical model of computation.
Journal version: Natural Computing, 7(1): 95-108. March 2008. Springer. [pdf]
Conference version: UC'05 - Fourth International Conference on Unconventional Computation, Sevilla, October 2005. Springer LNCS vol 3699, pp 237-250. [pdf] [ps]

D. Woods, J. P. Gibson
Complexity of continuous space machine operations.
CiE'05 - Computability in Europe 2005: New Computational Paradigms, Amsterdam, June 2005, S. B. Cooper, B. Löwe, and L. Torenvliet, Eds. Springer LNCS vol. 3526, pp 540-551. [pdf] [ps]

D. Woods, T. J. Naughton
An optical model of computation.
Theoretical Computer Science, 334(1-3): 227-258, April 2005. [pdf]

T. J. Naughton, D. Woods
On the computational power of a continuous-space optical model of computation.
MCU 2001 - Third International Conference on Machines, Computations and Universality 2001, Maurice Margenstern and Yurii Rogozhin, Eds., Chisinau, Moldova, May 2001. Springer LNCS vol. 2055, pp. 288-299. [pdf] [ps]


Theory: Computational complexity, membranes, Boolean circuits

N. Murphy, D. Woods
Uniformity is weaker than semi-uniformity for some membrane systems.
Fundamenta Informaticae. 134(1-2): 129-152. 2014. [arXiv]

N. Murphy, D. Woods
AND and/or OR: Uniform Polynomial-Size Circuits.
MCU 2013: Machines, Computations and Universality. Turlough Neary and Matthew Cook (Eds). Zürich, Switzerland, Electronic Proceedings in Theoretical Computer Science 128:150-166. [EPTCS]. Older version [arxiv] [cs.CC] Dec 2012

N. Murphy, D. Woods
Uniformity conditions in natural computing.
DNA 16 - The 16th International Conference on DNA Computing and Molecular Programming. Hong Kong, China, June 14-17, Preproceedings, 2010, pp. 109--120. (Early conference version of the above two papers.)
Niall got the Best Student Paper award!.

D. Woods, N. Murphy, M.J. Pérez-Jiménez, A. Riscos-Núñez
Membrane dissolution and division in P.
UC'09: Eighth International Conference on Unconventional Computation, Ponta Delgada (Azores), Portugal. Springer LNCS, vol 5715 , pp 268-282 [pdf]

N. Murphy, D. Woods
Uniformity: Uncovering the Frontier of Parallelism.
Proceedings of the 10th Workshop on Membrane Computing, Curtea de Argeş, Romania, 2009. Pages 556-560. [pdf] (A short survey highlighting some of our work.)

M.J. Pérez-Jiménez, A. Riscos-Núñez, A. Romero-Jiménez, D. Woods
Complexity: Membrane division, membrane creation.
The Oxford Handbook of Membrane Computing, Oxford University Press. Gh. Paun, G. Rozenberg, A. Salomaa (eds). 2009, Chapter 12, pp. 302-336.

N. Murphy, D. Woods
On acceptance conditions for membrane systems: characterisations of L and NL.
The Complexity of Simple Programs, Cork, Ireland, 6-7 december, 2008. Cork University Press, pp 225-242. [pdf] [arxiv] [cs.CC] Jun 2009.

N. Murphy, D. Woods
The computational power of membrane systems under tight uniformity conditions.
Natural Computing, 10(1): 613-631, 2011. [pdf] (Invited)
Conference version: N. Murphy, D. Woods. "A characterisation of NL using membrane systems without charges and dissolution", UC'08: Seventh International Conference on Unconventional Computation, Vienna, 2008. Springer LNCS, vol 5204 , pp 164-176 [pdf]

N. Murphy, D. Woods
Active membrane systems without charges and using only symmetric elementary division characterise P.
Proceedings of the 8th Workshop on Membrane Computing, 2007, Thessaloniki, Greece. Springer LNCS vol. 4860, pp 367-384. [pdf]

N. Murphy, T. J. Naughton, D. Woods, B. Henley, K. McDermott, E. Duffy, P. J. M. van der Burgt, N. Woods
Implementations of a model of physical sorting.
International Journal of Unconventional Computing, 4(1), pp 3-12, 2008. [pdf]
Conference version: Pre-proceedings of the workshop From Utopian to Genuine Unconventional Computers (part of UC'06), York, UK. Luniver Press, pp 79-99. [pdf]

N. Murphy, D. Woods, T. J. Naughton
Bio-Computation using Holliday junctions.
MFCSIT 2006. Cork, Ireland. pp 317-320. [pdf] [ps]

D. Woods, A. Trenaman
Simultaneous satisfaction of hard and soft timetable constraints for a university department using evolutionary timetabling.
Proceedings of Artificial Intelligence & Cognitive Science 1999, Cork, Ireland, September 1999, pp 1-7. [ps]


PhD thesis

D. Woods, "Computational Complexity of an optical model of computation" PhD Thesis, NUI Maynooth, 2005.


Some old technical reports, short conference abstracts, etc.