[photo by William Plowman]

“Computational Origami” by Erik and Martin Demaine, part of the Museum of Modern Art permanent collection

Erik Demaine

Research

• Papers
• Videos
• Puzzles
• Software
• CV in PostScript or PDF, last updated on August 3, 2008.
• I co-edit The Open Problems Project with Joseph Mitchell and Joseph O'Rourke
• I co-organize (and cofounded) the MIT Algorithmic Open Problem Session.
• 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 co-authors: Timothy Abbott, Zachary Abel, Micah Adler, Oswin Aichholzer, Noga Alon, Greg Aloupis, Stephen Alstrup, Lars Arge, Esther Arkin, Boris Aronov, Will Arora, Mihai Bădoiu, Hari Balakrishnan, Devin Balkcom, Brad Ballinger, Ziv Bar-Joseph, Ilya Baran, George Barbastathis, MohammadHossein Bateni, Nadia M. Benbernou, Carl Bender, Michael Bender, David Benoit, Marshall Bern, Therese Biedl, Prosenjit Bose, Jonathan Bredin, Broňa Brejová, David Bremner, Ron Breukelaar, Gerth Brodal, Andrej Brodnik, Kevin Buchin, Maike Buchin, David Bunde, Jonathan Buss, Sergio Cabello, Jason Cantarella, Jean Cardinal, Svante Carlsson, Eowyn Čenek, Timothy Chan, David Charlton, Barry Cipra, Stelian Ciurea, Austin Clements, Richard Cole, Sébastien Collette, Robert Connelly, Carmen Cortés, Mirela Damian, David DeHaan, Erik D. Demaine, Martin L. Demaine, Ajay Deshpande, Satyan Devadoss, Vida Dujmović, Christian Duncan, Alan Edelman, Dania El-Khechen, Dotan Emanuel, David Eppstein, Jeff Erickson, Martin Farach-Colton, Uriel Feige, Sándor Fekete, Thomas Fevens, Amos Fiat, Samuel Fiorini, Robin Flatland, Rudolf Fleischer, Fedor Fomin, Ian Foster, Aviezri Fraenkel, Greg Frederickson, Erich Friedman, Shmuel Gal, Blaise Gassend, Mohammad Ghodsi, David Gifford, Lukasz Golab, Mordecai Golin, Alexander Golynski, Francisco Gomez-Martin, Joachim Gudmundsson, Gregory Gutin, MohammadTaghi Hajiaghayi, Angéle Hamel, Dion Harmon, George Hart, Vi Hart, Nicholas J. A. Harvey, Barry Hayes, Robert A. Hearn, Michael Hoffmann, Susan Hohenberger, Bryan Holland-Minkley, Markus Holzer, Hendrik Jan Hoogeboom, Joseph Horton, Ferran Hurtado, John Iacono, Hayley Iben, Nicole Immorlica, Piotr Indyk, Mashhood Ishaque, Takehiro Ito, Tommi Jaakkola, Lars Jacobsen, Thouis Jones, Gwenaël Joret, Daniel Kane, Craig Kaplan, Dmitriy A. Katz, Ken-ichi Kawarabayashi, Carl Kesselman, Taejung Kim, James King, Christian Knauer, Stephen Kobourov, Scott D. Kominers, Duks Koschitz, Walter A. Kosters, Evangelos Kranakis, Hannes Krasser, Danny Krizanc, Eric Kuo, Arthur Langerman, Stefan Langerman, Sylvain Lazard, Charles E. Leiserson, Ben Leong, Vitus Leung, David Liben-Nowell, Jeffrey Lindy, Barbara Liskov, Alejandro López-Ortiz, Anna Lubiw, Hamid Mahini, Andrea Mantler, Dániel Marx, Henk Meijer, Antonio Mesa, Friedhelm Meyer auf der Heide, Joseph Mitchell, Bojan Mohar, Mohammad Moharrami, Pat Morin, Shay Mozes, J. Ian Munro, Jelani Nelson, Ilan Newman, Paul Nijjar, Naomi Nishimura, Takao Nishizeki, Richard Nowakowski, James O'Brien, Joseph O'Rourke, Timo von Oertzen, Shayan Oveisgharan, Mark Overmars, Rasmus Pagh, A. Laurie Palmer, Belén Palop, Irena Pashchenko, Mihai Pǎtraşcu, Per-Olof Persson, Cynthia Phillips, Guillaume Poirier, Dan R. K. Ports, Eric Price, Nissanka Priyantha, Claude-Guy Quimper, Eynat Rafalin, Prabhakar Ragde, Rajeev Raman, Venkatesh Raman, Suneeta Ramaswami, S. Srinivasa Rao, David Rappaport, Theis Rauhe, Ares Ribó, Steven Robbins, Tom Rodgers, Benjamin Rossman, Günter Rote, Daniela Rus, Vera Sacristán, Mohammad R. Salavatipour, Sanjay E. Sarma, Amin S. Sayedi-Roshkhar, André Schulz, Robert T. Schweller, Robert Sedgewick, Saurabh Sethia, Anastasios Sidiropoulos, Steven Skiena, Michiel Smid, Marc Snir, Jack Snoeyink, Michael Soss, Diane Souvaine, Nathan Srebro, Sampalli Srinivas, Ulrike Stege, Paul Stellman, Ileana Streinu, Satoshi Takahashi, Corina E. Tarnita, Perouz Taslakian, Seth Teller, Sachio Teramoto, Dimitrios Thilikos, Mikkel Thorup, Csaba D. Tóth, Godfried Toussaint, Daniela Tulone, Ryuhei Uehara, Jorge Urrutia, Helena Verrill, Tomáš Vinař, Ming-wei Wang, Oren Weimann, Sue Whitesides, Terry Winograd, David Wood, Stefanie Wuhrer, Vincent Yeung, Morteza Zadimoghaddam, Xiao Zhou, Jack Zito.

Academics

• Academic family
  • Current PhD students:
    • Nadia Benbernou
    • Jelani Nelson
    • Mihai Pătraşcu
    • Oren Weimann
  • Completed PhD students:
    • Dion Harmon (now at New England Complex Systems Institute)
      Thesis: New Bounds on Optimal Binary Search Trees (2006)
    • Bob Hearn (cosupervised with Gerald Sussman, now a post-doc at Dartmouth College)
      Thesis: Games, Puzzles, and Computation (2006)
    • MohammadTaghi Hajiaghayi (now a Senior Researcher at AT&T Labs — Research)
      Thesis: The Bidimensionality Theory and Its Algorithmic Applications (2005)
    • Nicole Immorlica (cosupervised with David Karger, now a post-doc at CWI)
      Thesis: Computing with Strategic Agents (2005)
    • David Liben-Nowell (now an Assistant Professor at Carleton College)
      Thesis: An Algorithmic Approach to Social Networks (2005)
  • Academic "parents" (PhD co-advisors): Anna Lubiw and Ian Munro
  • More detailed genealogy
• Undergraduate advisor since September 2002
• Teaching:
  • MADALGO Summer School on Cache-Oblivious Algorithms, Aarhus, Denmark, August 18–21, 2008 (including lecture notes)
  • 6.006: (New) Introduction to Algorithms (Spring 2008)
  • 6.885: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2007, Fall 2004)
  • 6.851: Advanced Data Structures (Spring 2007; formerly 6.897, Spring 2005, Spring 2003)
  • 6.096: Knot Language: Recreating Inca Quipu/Khipu (IAP 2007)
  • 6.046/18.410/SMA5503: Introduction to Algorithms (Fall 2006, Fall 2005 including videos of lectures, also on OpenCourseWare; Spring 2004; Fall 2002; and Fall 2001 including videos of lectures, also on OpenCourseWare)
  • Junkyard Art: The Art of Recycling (IAP 2005)
  • 4.491: Form-Finding and Structural Optimization: Gaudi Workshop (Fall 2004)
    Formerly 4.493: 3-D Design Tools for Equilibrium: Exploring Gaudi's World (Spring 2004)
  • Building with Books (IAP 2004)
  • 6.854: Advanced Algorithms (Fall 2003)
  • EEF Summer School on Massive Data Sets, Aarhus, Denmark, June 27–July 1, 2002 (including lecture notes)
• Refer to my CV for committees etc.

Contact Information

• Name: Erik D. Demaine
• Email: edemaine@mit.edu
• PGP public key
• Office phone number: (+1) 617-253-6871
• Fax number: (+1) 617-258-8682
• MIT office: 32-G680 (near Kendall/MIT Station on the Boston Subway (MBTA) red line)
• Administrative assistant: Patrice Macaluso (32-G568, 617-253-3037, macaluso at csail.mit.edu)
• Mailing address:
  

  Erik Demaine
  MIT Computer Science and Artificial Intelligence Laboratory
  32 Vassar Street
  Cambridge, Massachusetts 02139
  USA

Personal Information

• Hobbies:
  • Improv comedy/theater
  • Glassblowing
  • Origami (paper folding)
  • Juggling ("intermediate")
  • Magic, particularly with cards
  • String figures
  • Programming
• I write a bimonthly column for the Amateur Press Alliance imagiro devoted to origami.
• Permanent collections:
  • Hyparhedra, Southwestern College, Winfield, Kansas, USA, 1999
  • Topological puzzles, Elliott Avedon Museum and Archive of Games, University of Waterloo, Ontario, Canada, 1987.
• 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, Hungary, India, Israel, Italy, Japan, Korea, Luxembourg, Mexico, The Netherlands, Peru, Spain, Switzerland, United States, Vatican City. [Map]
• Birthplace: Halifax, Nova Scotia, Canada
• Birthdate: February 28, 1981