![[Erik Demaine lecturing in Halloween costume, 2007.]](images/halloween2007_small.jpg "Halloween 2007 lecture in 6.885: Geometric Folding Algorithms")
[photo by Martin Demaine]
Erik Demaine
![[Inversion]](images/inversion_small.gif)
MacArthur Fellow
—
Alfred P.
Sloan Research Fellow
Esther and Harold E. Edgerton Professor
Associate Professor
of Electrical
Engineering and Computer Science
Member of the
Computer Science and
Artificial Intelligence Lab
in the
Theory of Computation group,
specifically
Algorithms
Massachusetts Institute of Technology
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
- Undergraduate advisor since September 2002
- Teaching at MIT:
- Refer to my CV for committees etc.
Contact Information
Personal Information
- Hobbies:
- 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
Last updated June 2, 2008 by
Erik Demaine.
