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).
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
The goal of the Theory of Computation CoR is to study the fundamental strengths and limits of computation as well as how these interact with mathematics, computer science, and other disciplines.
Theory research at CSAIL covers a broad spectrum of topics, including algorithms, complexity theory, cryptography, distributed systems, parallel computing and quantum computing.
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 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.
