Erik 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 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 recent origami documentary Between the Folds, 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 New York, and the Renwick Gallery in the Smithsonian.
-I am interested in most areas of research in mathematics and computer science broadly connected to algorithms. Particular interests 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
-In the past, I’ve been interested in the following areas (now I would take a more algorithmic slant):
-Programming languages: Concurrent programming, translation
-Parallel and supercomputing: MPI and PVM, parallel computer simulation
-Scientific computing: Sparse matrix computation, finite element method
Martin L. (Marty) Demaine (born 1942) is an artist and mathematician, the Angelika and Barton Weller artist in residence at the Massachusetts Institute of Technology. Demaine attended Medford High School in Medford, Massachusetts. After studying glassblowing in England, he began his artistic career by blowing art glass in New Brunswick in the early 1970s. The Demaine Studio, located in Miramichi Bay and later at Opus Village in Mactaquac, was the first one-man glass studio in Canada, part of the international studio glass movement. Demaine’s pieces from this period are represented in the permanent collections of half a dozen major museumsincluding the Canadian Museum of Civilization and the National Gallery of Canada. Since joining MIT, Demaine has begun blowing glass again, as an instructor at the MIT Glass Lab; his newer work features innovative glassblowing techniques intended as a puzzle to his fellow glassblowers. Martin Demaine is the father of MIT Computer Science professor and MacArthur Fellow Erik Demaine; in 1987 (when Erik was six) they together founded the Erik and Dad Puzzle Company which distributed puzzles throughout Canada. Erik was home-schooled by Martin, and although Martin never received any higher degree than his high school diploma, his home-schooling catapulted Erik to a B.S. at age 14 and a Ph.D. and MIT professorship at age 20, making him the youngest professor ever hired by MIT.The two Demaines continue to work closely together and have many joint works of both mathematics and art, including three pieces of mathematical origami in the permanent collection of the Museum of Modern Art New York; their joint mathematical works focus primarily on the mathematics of folding and unfolding objects out of flat materials such as paper and on the computational complexity of games and puzzles. Martin and Erik are also featured in the movie Between the Folds, a documentary on modern origami.
Demaine is a citizen of both Canada and the United States.