More About Erik Demaine  

Short Biography

Erik Demaine is a Professor in Computer Science at the Massachusetts Institute of Technology. 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 origami documentaries Between the Folds and NOVA's The Origami Revolution, 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.

Research Interests

• 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
• My research is almost all collaborative. My favorite style of collaborative research is supercollaboration.
• I co-edit The Open Problems Project with Joseph Mitchell and Joseph O'Rourke

A Few Personal Details

My favorite award: Tetris Master

• Hobbies:
  • Improv comedy/theater
  • Glassblowing
  • Origami (paper folding)
  • Juggling ("intermediate")
  • Magic, particularly with cards
  • String figures
  • Video games
  • Programming
• Countries I've visited (airports don't count): Argentina, Austria, Barbados, Belgium, Canada, Chile, China (Hong Kong, Macau, and Mainland), Czech Republic, Denmark, England, Finland, France, Germany, Greece, Hungary, Iceland, India, Ireland, Israel, Italy, Japan, Korea, Luxembourg, Mexico, The Netherlands, Norway, Peru, Slovakia, Spain, Sweden, Switzerland, Taiwan, Thailand, United Arab Emirates, United States, Vatican City. [Map]
• Birthplace: Halifax, Nova Scotia, Canada
• Birthdate: February 28, 1981