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 unfolding, linkages, 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