[photo by Donna Coveney]

“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 October 20, 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 G. 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, 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, Barry Cipra, Stelian Ciurea, Austin Clements, Richard Cole, Sébastien Collette, Robert Connelly, Carmen Cortés, Mirela Damian, David DeHaan, 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, John Hugg, Ferran Hurtado, John Iacono, Hayley Iben, 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, Taejung Kim, James King, Philip N. Klein, Christian Knauer, Stephen Kobourov, Scott D. Kominers, Duks Koschitz, Walter A. Kosters, Evangelos Kranakis, Hannes Krasser, Danny Krizanc, Eric Kuo, Gad M. Landau, Robert J. Lang, Arthur Langerman, Stefan Langerman, Sylvain Lazard, 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, 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, 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, Amin S. Sayedi-Roshkhar, André Schulz, Nils Schweer, Robert T. Schweller, Daria Schymura, Robert Sedgewick, Saurabh Sethia, Kathryn Seyboth, 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, Satoshi Takahashi, 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, Yushi Uno, Jorge Urrutia, Helena Verrill, Jérôme Vervier, Tomáš Vinař, Ming-wei Wang, Oren Weimann, Sue Whitesides, Terry Winograd, David 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)
  • Completed PhD students:
    • Oren Weimann (now a postdoc at Weizmann Institute of Science)
      Thesis: Accelerating Dynamic Programming (2009)
    • Mihai Pătraşcu (now a postdoc at IBM Almaden, then a researcher 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 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 an Assistant Professor at Northwestern Univeristy)
      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:
  • 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, 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