Erik D. Demaine

Research interests

Publications

• A method for building self-folding machines

  Science · 2014 · https://doi.org/10.1126/science.1252610

• Self-folding with shape memory composites

  Soft Matter · 2013 · https://doi.org/10.1039/c3sm51003d

• Programmable matter by folding

  Proceedings of the National Academy of Sciences · 2010 · https://doi.org/10.1073/pnas.0914069107

• On the complexity of reconfiguration problems

  Theoretical Computer Science · 2010 · https://doi.org/10.1016/j.tcs.2010.12.005

• An optimal decomposition algorithm for tree edit distance

  ACM Transactions on Algorithms · 2009 · https://doi.org/10.1145/1644015.1644017

• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity

  Graphs and Combinatorics · 2007 · https://doi.org/10.1007/s00373-007-0713-4

• Geometric Folding Algorithms

  Cambridge University Press eBooks · 2007 · https://doi.org/10.1017/cbo9780511735172

• The Bidimensionality Theory and Its Algorithmic Applications

  The Computer Journal · 2007 · https://doi.org/10.1093/comjnl/bxm033

• Geometric Folding Algorithms: Linkages, Origami, Polyhedra

  Journal · 2007

• Logarithmic Lower Bounds in the Cell-Probe Model

  SIAM Journal on Computing · 2006 · https://doi.org/10.1137/s0097539705447256

• Correlation clustering in general weighted graphs

  Theoretical Computer Science · 2006 · https://doi.org/10.1016/j.tcs.2006.05.008

• Deploying sensor networks with guaranteed capacity and fault tolerance

  Journal · 2005 · https://doi.org/10.1145/1062689.1062729

• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs

  Journal of the ACM · 2005 · https://doi.org/10.1145/1101821.1101823

• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

  Theoretical Computer Science · 2005 · https://doi.org/10.1016/j.tcs.2005.05.008

• Mobile-assisted localization in wireless sensor networks

  Journal · 2005 · https://doi.org/10.1109/infcom.2005.1497889

• Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries

  Discrete & Computational Geometry · 2005 · https://doi.org/10.1007/s00454-004-1152-0

• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs

  ACM Transactions on Algorithms · 2005 · https://doi.org/10.1145/1077464.1077468

• Representing Trees of Higher Degree

  Algorithmica · 2005 · https://doi.org/10.1007/s00453-004-1146-6

• Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring

  Journal · 2005 · https://doi.org/10.1109/sfcs.2005.14

• Anchor-Free Distributed Localization in Sensor Networks

  DSpace@MIT (Massachusetts Institute of Technology) · 2003

• Frequency Estimation of Internet Packet Streams with Limited Space

  Lecture notes in computer science · 2002 · https://doi.org/10.1007/3-540-45749-6_33

• Cache-oblivious B-trees

  Journal · 2002 · https://doi.org/10.1109/sfcs.2000.892128

• Adaptive set intersections, unions, and differences

  Journal · 2000 · https://doi.org/10.5555/338219.338634

Current projects

No projects listed.