Erik D. Demaine

Home * People * Erik D. Demaine

[ Demaines, Spight and Conway [1] Erik D. Demaine,

a Canadian American mathematician, computer scientist and professor of computer science at Massachusetts Institute of Technology and member of the Theory of Computation group at MIT Computer Science and Artificial Intelligence Laboratory. His research interests include data structures such as binary search trees, the mathematics of paper folding as well as combinatorial game theory. Mathematical origami artwork by Erik and his father Martin L. Demaine was part of the Design and the Elastic Mind exhibit at the Museum of Modern Art in 2008 [2].

Selected Publications#

[3] [4]

1998 …#

• Erik D. Demaine (1998). Protocols for Non-Deterministic Communication over Synchronous Channels. IPPS/SPDP 1998
• Erik D. Demaine, Martin L. Demaine, Anna Lubiw (1998). Folding and Cutting Paper. JCDCG 1998
• Erik D. Demaine, Martin L. Demaine (1998). Planar Drawings of Origami Polyhedra. GD 1998, Lecture Notes in Computer Science, Vol. 1547, Springer
• Erik D. Demaine (1998). C to Java: Converting Pointers into References. Concurrency: Practice and Experience, Vol. 10, Nos. 11-13
• Erik D. Demaine, J. Ian Munro (1999). Fast Allocation and Deallocation with an Improved Buddy System. FSTTCS 1999, Lecture Notes in Computer Science, Vol. 1738, Springer [5]

2000 …#

• Erik D. Demaine, Martin L. Demaine, David Eppstein (2000). Phutball Endgames are Hard. arXiv:cs/0008025 [6]
• Erik D. Demaine (2000). Folding and Unfolding Linkages, Paper, and Polyhedra. JCDCG 2000, Lecture Notes in Computer Science, Vol. 2098, Springer
• Erik D. Demaine (2001). Folding and Unfolding. Ph.D. thesis, University of Waterloo, advisors Anna Lubiw, James Ian Munro
• Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer (2002). Solitaire Clobber. CG 2002
• Erik D. Demaine, Susan Hohenberger, David Liben-Nowell (2003). Tetris is Hard, Even to Approximate. COCOON 2003, slides as Tetris is Hard: An Introduction to P vs NP (pdf)
• Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter Kosters, David Liben-Nowell (2004). Tetris is hard, even to approximate. International Journal of Computational Geometry & Applications, Vol. 14
• Erik D. Demaine, Martin L. Demaine (2004). Fold-and-Cut Magic. in Tribute to a Mathemagician. A K Peters
• Erik D. Demaine, Martin L. Demaine (2004). Sliding-Coin Puzzles. in Tribute to a Mathemagician. A K Peters
• Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pătrașcu (2007). Dynamic Optimality—Almost. SIAM Journal on Computing, Vol. 37, No. 1 [7]
• Robert A. Hearn, Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters

2010 …#

• Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Pătrașcu (2012). Picture-Hanging Puzzles.. arXiv:1203.3602
• Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan (2013). Combining Binary Search Trees. arXiv:1304.7604
• Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno (2014). Folding a Paper Strip to Minimize Thickness. arXiv:1411.6371
• Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Virginia Vassilevska Williams (2017). Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy. arXiv:1711.07960
• Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, Jayson Lynch (2018). Losing at Checkers is Hard. arXiv:1806.05657
• Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman (2019). Belga B-trees. arXiv:1903.03560
• Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno (2019). Reconfiguring Undirected Paths. arXiv:1905.00518

External Links#

• Erik Demaine
• Erik Demaine from Wikipedia
• Erik Demaine - The Mathematics Genealogy Project

References#

1. ↑ Erik Demaine (left) with Martin Demaine (center) and Bill Spight (background) watch John Conway (foreground) do a card trick at Workshop on Combinatorial Game Theory at Banff International Research Station, June, 2005, Photo by Thane Plambeck, June 21 2005, Erik Demaine from Wikipedia
2. ↑ Computational Origami (2008): Curved-Crease Sculpture by Erik and Martin Demaine
3. ↑ Erik Demaine’s Papers
4. ↑ dblp: Erik D. Demaine
5. ↑ Buddy memory allocation from Wikipedia
6. ↑ Phutball from Wikipedia
7. ↑ Tango tree from Wikipedia

Up one level