[photo by Stefan Langerman]

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

Erik Demaine

Research

• Papers
• Sculpture
• Videos
• Puzzles
• Software
• Movies: I appear in the documentaries Between The Folds about origami (which you can watch online) and The Man Who Saved Geometry about Coxeter
• CV in PostScript or PDF, last updated on August 12, 2010.
• I co-edit The Open Problems Project with Joseph Mitchell and Joseph O'Rourke
• 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 G. Abbott, Zachary Abel, Micah Adler, Oswin Aichholzer, Noga Alon, Greg Aloupis, Stephen Alstrup, Byoung Kwon An, Lars Arge, Esther Arkin, Boris Aronov, Will Arora, Tetsuo Asano, Mihai Bădoiu, Hari Balakrishnan, Devin Balkcom, Brad Ballinger, Ziv Bar-Joseph, Ilya Baran, George Barbastathis, Gill Barequet, MohammadHossein Bateni, Nadia M. Benbernou, Carl Bender, Michael Bender, David Benoit, Marshall Bern, Therese Biedl, Glencora Borradaile, Prosenjit Bose, Jonathan Bredin, Broňa Brejová, David Bremner, Ron Breukelaar, Gerth Brodal, Andrej Brodnik, Kevin Buchin, Maike Buchin, David Bunde, Michael A. Burr, Jonathan Buss, Sergio Cabello, Jason Cantarella, Jean Cardinal, Svante Carlsson, Eowyn Čenek, Timothy M. Chan, David Charlton, Kailiang Chen, Barry Cipra, Stelian Ciurea, Austin Clements, Richard Cole, Sébastien Collette, Robert Connelly, Carmen Cortés, David Dalrymple, Mirela Damian, David DeHaan, Martin L. Demaine, Ajay Deshpande, Satyan Devadoss, Vida Dujmović, Muriel Dulieu, Christian Duncan, Alan Edelman, Dania El-Khechen, Dotan Emanuel, David Eppstein, Jeff Erickson, Ruy Fabila-Monroy, Martin Farach-Colton, Uriel Feige, Sándor Fekete, Thomas Fevens, Amos Fiat, Jeremy T. Fineman, Samuel Fiorini, Robin Flatland, Rudolf Fleischer, Fedor Fomin, Ian Foster, Aviezri Fraenkel, Greg Frederickson, Erich Friedman, Shmuel Gal, Blaise Gassend, Neil Gershenfeld, Mohammad Ghodsi, David Gifford, Lukasz Golab, Mordecai Golin, Alexander Golynski, Francisco Gomez-Martin, Forrest Green, Scott Greenwald, Joachim Gudmundsson, Gregory Gutin, MohammadTaghi Hajiaghayi, Angéle Hamel, Dion Harmon, George Hart, Vi Hart, Nicholas J. A. Harvey, Elliot Hawkes, Barry Hayes, Robert A. Hearn, Michael Hoffmann, Susan Hohenberger, Bryan Holland-Minkley, Markus Holzer, Hendrik Jan Hoogeboom, Joseph Horton, John Hugg, Ferran Hurtado, John Iacono, Hayley Iben, Shinji Imahori, Nicole Immorlica, Piotr Indyk, Mashhood Ishaque, Takehiro Ito, Tommi Jaakkola, Lars Jacobsen, Thouis Jones, Gwenaël Joret, Marcin Kamiński, Daniel Kane, Craig Kaplan, Dmitriy A. Katz, Ken-ichi Kawarabayashi, Carl Kesselman, Sangbae Kim, Taejung Kim, James King, Philip N. Klein, Ara Knaian, Christian Knauer, Stephen Kobourov, Scott D. Kominers, Goran Konjevod, Duks Koschitz, Walter A. Kosters, Evangelos Kranakis, Hannes Krasser, Danny Krizanc, Jason Ku, Eric Kuo, Gad M. Landau, Robert J. Lang, Arthur Langerman, Stefan Langerman, Sylvain Lazard, Tom Leighton, Charles E. Leiserson, Ben Leong, Vitus Leung, David Liben-Nowell, Jeffrey Lindy, Barbara Liskov, Ching-Hao Liu, Alejandro López-Ortiz, Anna Lubiw, Hamid Mahini, Andrea Mantler, Dániel Marx, James McLurkin, 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, John A. Ochsendorf, Timo von Oertzen, Aviv Ovadya, Shayan Oveisgharan, Mark Overmars, Rasmus Pagh, A. Laurie Palmer, Belén Palop, Christos H. Papadimitriou, Jun-geun Park, Irena Pashchenko, Mihai Pǎtraşcu, Per-Olof Persson, Cynthia Phillips, Val Pinciu, Guillaume Poirier, Sheung-Hung Poon, Dan R. K. Ports, Eric Price, Gregory N. 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, Maria Saumell, Amin S. Sayedi-Roshkhar, Peter Schmidt-Nielsen, André Schulz, Nils Schweer, Robert T. Schweller, Daria Schymura, Carlos Seara, Robert Sedgewick, Saurabh Sethia, Kathryn Seyboth, Arlo Shallit, Jonah Shallit, Martha Sideri, Anastasios Sidiropoulos, Steven Skiena, Michiel Smid, Marc Snir, Jack Snoeyink, Michael Soss, Diane Souvaine, Nathan Srebro, Sampalli Srinivas, Ulrike Stege, Paul Stellman, Ileana Streinu, Tomohiro Tachi, Satoshi Takahashi, Hiroto Tanaka, Corina E. Tarnita, Perouz Taslakian, Siamak Tazari, Seth Teller, Sachio Teramoto, Dimitrios Thilikos, Mikkel Thorup, Csaba D. Tóth, Godfried Toussaint, Daniela Tulone, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Jorge Urrutia, Helena Verrill, Jérôme Vervier, Tomáš Vinař, Ming-wei Wang, Oren Weimann, Sue Whitesides, Terry Winograd, Andrew Winslow, David Wood, Robert Wood, Stefanie Wuhrer, Vincent Yeung, Zhong You, Morteza Zadimoghaddam, Norbert Zeh, Mariano Zelke, Xiao Zhou, Jack Zito.

Academics

• Academic family
  • Current PhD students:
    • Timothy Abbott (on leave)
    • Nadia Benbernou
    • Jelani Nelson (cosupervised with Piotr Indyk)
    • Morteza Zadimoghaddam
  • Completed PhD students:
    • Oren Weimann (now a postdoc at Weizmann Institute of Science)
      Thesis: Accelerating Dynamic Programming (2009)
    • Mihai Pătraşcu (now a Senior Member of Technical Staff at AT&T Labs — Research)
      Thesis: Lower Bound Techniques for Data Structures (2008)
    • 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 Visiting Research Scholar 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 an Assistant Professor at Northwestern University)
      Thesis: Computing with Strategic Agents (2005)
    • David Liben-Nowell (now an Assistant Professor at Carleton College)
      Thesis: An Algorithmic Approach to Social Networks (2005)
  • Completed Master's students:
    • Timothy Abbott (now a PhD student at MIT)
      Thesis: Generalizations of Kempe's Universality Theorem (2008)
    • Greg Price (now a PhD student at MIT)
      Thesis: A Pseudopolynomial Algorithm for Alexandrov's Theorem (2008)
    • Katherine Lai (now a PhD student at Cornell)
      Thesis: Complexity of Union-Split-Find Problems (2008)
  • Academic "parents" (PhD co-advisors): Anna Lubiw and Ian Munro
  • More detailed genealogy
• Undergraduate advisor since September 2002
• Teaching:
  • 6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2010, formerly 6.885, Fall 2007, Fall 2004)
  • SP.268: The Mathematics of Toys and Games
  • 6.851: Advanced Data Structures (Spring 2010, Spring 2007; formerly 6.897, Spring 2005, Spring 2003)
  • 6.046/18.410: (New) Design and Analysis of Algorithms (Fall 2009)
  • 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.096: Knot Language: Recreating Inca Quipu/Khipu (IAP 2007)
  • 6.046/18.410/SMA5503: (Old) 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
• URL: http://erikdemaine.org/
• PGP public key
• Work 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
  • Video games
• I write a bimonthly column for the Amateur Press Alliance imagiro devoted to origami.
• Permanent collections:
  Computational Origami, Museum of Modern Art (MoMA), New York, USA, 2008
  • 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, Greece, Hungary, India, Ireland, 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