PI
Core/Dual

Erik Demaine

Professor

Phone

253-6871

Room

32-G680

Erik Demaine is a Professor in Computer Science at MIT. 

Demaine's research interests range throughout algorithms, from data structures for improving web searches to the geometry of understanding how proteins fold to the computational difficulty of playing games. He received a MacArthur Fellowship ("genius grant") as a “computational geometer tackling and solving difficult problems related to folding and bending—moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter”.

He appears in the origami documentaries Between the Folds and NOVA's The Origami Revolution. He cowrote a book about the theory of folding (Geometric Folding Algorithms), and a book about the computational complexity of games (Games, Puzzles, and Computation).

Together with his father Martin, his interests span the connections between mathematics and art, including curved-crease sculptures in the permanent collections of the Museum of Modern Art in New York, and the Renwick Gallery in the Smithsonian.

His research areas include:

  • Discrete and computational geometry: Folding and unfoldinglinkages, robotics, motion planning, dissections, simple polygonizations
  • Data structures: Dynamic data structures, succinct encodings of data structures, memory management, cache-efficient and disk-efficient data structures, average-case data structures, text indexing
  • Algorithms and their analysis: Adaptive computation, graph algorithms, string matching, randomized algorithms, approximation algorithms, fixed-parameter algorithms, streaming algorithms
  • Complexity theory: Hardness (NP, PSPACE, EXPTIME, EXPSPACE, …), parameterized complexity
  • Combinatorics: Discrete mathematics, graph theory (matchings, minors, treewidth, …), combinatorial game theory
  • Biology: Protein folding, protein design (member of the MIT Computational and Systems Biology Initiative)
  • Network and mobile computing: Location (Cricket and RFID), sensor networks (SLAM)
  • Computational archaeology/anthropology: khipu

Research Areas

Groups

News

Origami anything

In a 1999 paper, Erik Demaine — now a CSAIL principal investigator, but then an 18-year-old PhD student at the University of Waterloo, in Canada — described an algorithm that could determine how to fold a piece of paper into any conceivable 3-D shape. It was a milestone paper in the field of computational origami, but the algorithm didn’t yield very practical folding patterns. Essentially, it took a very long strip of paper and wound it into the desired shape. The resulting structures tended to have lots of seams where the strip doubled back on itself, so they weren’t very sturdy.

Popular Science Spotlights Erik Demaine

Popular Science featured the work of CSAIL Principal Investigator and Professor Erik Demaine this month in an article called, "The Genius Who Played for a Living." From his hiring as MIT's youngest professor to his work with paper folding and programmable matter, the article spotlights the motivation and inspiration for all of Demaine's work.