Damien Woods
Caltech

Damien


News!

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.

I'm a Senior Research Fellow in Computing and Mathematical Sciences, and The Molecular Programming Fellow at Caltech. I work in the research groups of Erik Winfree and Shuki Bruck. I'm in the Department of Computing and Mathematical Sciences and affiliated with the Center for the Mathematics of Information. Email: woodscaltech.edu

Publications by topic:

Small universal Turing machines, Rule 110 & other simple universal systems
Optical computing
Computational complexity and biological computing
Active self-assembly, movement and molecular robots
Intrinsic universality in self-assembly

Current students:

Joy Hui. SURF 2013, visitor 2014, Harvard College (co-mentored with Erik Winfree)
Dhiraj Holden. SURF 2013, Caltech (co-mentored with Erik Winfree)

Former postdoc visitor:

Pierre-Etienne Meunier. Summer 2013. Co-hosted with Erik Winfree

Former PhD students:

Turlough Neary. Small universal Turing machines. NUI Maynooth Computer Science. PhD awarded: 2008. Examiners: Maurice Margenstern, James Power. Co-supervised by Paul Gibson

Niall Murphy. Uniformity conditions for membrane systems: uncovering complexity below P. NUI Maynooth Computer Science. PhD awarded: 2010. Examiners: Petr Sosík, Philippe Moser. Co-supervised by Tom Naughton.

Former undergraduate students:

Moya Chen. SURF 2012, EE, Caltech (co-mentored with Erik Winfree)
Doris Xin. Senior Thesis 2012, CS, Caltech (co-mentored with Erik Winfree)
Felix Zhou. SURF 2012, University of Cambridge, UK (co-mentored with Erik Winfree, David Doty)
Zibo Chen. SURF, BIOMOD 2011, National University of Singapore (co-mentored with Erik Winfree, Lulu Qian, Niranjan Srinivas)
Shayan Doroudi. SURF, BIOMOD 2011, Caltech (co-mentored with Erik Winfree, Lulu Qian, Niranjan Srinivas)
Greg Izatt. SURF, BIOMOD 2011, Caltech (co-mentored with Erik Winfree, Lulu Qian, Niranjan Srinivas)
Yae Lim Lee. SURF, BIOMOD 2011. Caltech EE (co-mentored with Erik Winfree, Lulu Qian, Niranjan Srinivas)
Sarah Wittman. SURF, BIOMOD 2011 (co-mentored with Erik Winfree, Lulu Qian, Niranjan Srinivas)
Turlough Neary. Final year thesis, BSc. NUI Maynooth CS

Current funding:

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

Conferences (PC member/invited speaker):

DNA20 2014, DCFS 2014, UCNC 2014, Heterotic Comp, MCU 2013, DNA19, UCNC 2013, DNA18 (tutorial), OSC 2012, Automata 2011, DNA17 (co-chair), LATA 2011, PC 2011, TCS 2010, UC 2010, OSC 2010, DCM 2009, OSC '09, CRPC '09, UC '08, PC '08, OSC '08, MCU '07, UC '07, LNPC '07, MFCSIT '06, UC '06 (workshop). I was one of the co-chairs of Complexity of Simple Programs 2008, the proceedings of which are here, and a follow-on journal special issue is availiable here (TCS, vol 142, issue 1-2).


I attended the BIOMOD 2011 Jamboree, and co-mentored the Caltech BIOMOD team, see the other teams here.

I previously worked in the Research Group on Natural Computing at the University of Seville and the Cork Complex Systems Lab (CCSL) in University college Cork. Before that I was at the Boole Centre For Research in Informatics and the School of Mathematics. I did my PhD at the Department of Computer Science at NUI Maynooth.


Small universal Turing machines, Rule 110 & other simple universal systems

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. To appear.
arXiv version: 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]


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]


Computational complexity and biological computing

N. Murphy, D. Woods. "Uniformity is weaker than semi-uniformity for some membrane systems".
Fundamenta Informaticae. Accepted.

N. Murphy, D. Woods. "AND and/or OR: Uniform Polynomial-Size Circuits".
Machines, Computations and Universality. In Turlough Neary and Matthew Cook: Proceedings Machines, Computations and Universality 2013 (MCU 2013), Zürich, Switzerland, Electronic Proceedings in Theoretical Computer Science 128, pp. 150-166. [EPTCS]. Slightly 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. In Gh. Paun, G. Rozenberg, A. Salomaa (eds.) The Oxford Handbook of Membrane Computing, Oxford University Press, 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" (Invited journal version) Natural Computing, 10(1): 613-631, 2011. [pdf]
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]


Active self-assembly, movement and molecular robots

[α] = Alphabetical author order

[α] 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. Accepted

Moya Chen, Doris Xin, Damien Woods.
Parallel computation using active self-assembly.
Journal version: Natural Computing. Accepted. [arxiv]
Conference version: DNA19: The 19th International Conference on DNA Computing and Molecular Programming. Sept. 2013. Springer LNCS 8141, pages 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, January 10-12, 2013. Full paper: [pdf], [arxiv], [blurbification]. ACM 2-page extended abstract: [ACM].


Intrinsic universality in self-assembly

[α] = Alphabetical author order

[α] 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] [cs.CC] Dec 2012

[α] 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]

Damien Woods.
Intrinsic universality and the computational power of self-assembly.
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, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods.
The two-handed tile assembly model is not intrinsically universal.
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] [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]

[α] 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]



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.



Some links: Carrick Castles, A course on cybernetics.