Prof. Erik D Demaine

Professor of Computer Science and Engineering
Margaret MacVicar Faculty Fellow

Primary DLC

Department of Electrical Engineering and Computer Science

MIT Room: 32-G680

Areas of Interest and Expertise

Theory of Computation
Discrete and Computational Geometry
Data Structures
Algorithms and Their Analysis: Adaptive Computation, Graph Algorithms, String Matching, Randomized Algorithms
Complexity Theory: Hardness, Approximation Algorithms, Parameterized Complexity
Combinatorics: Discrete Mathematics, Graph Theory, Combinatorial Game Theory
Biology: Protein Folding and Protein Design
Network and Mobile Computing
Computational Archaeology
Algorithms and Data Structures<br>Discrete and Computational Geometry, Particularly Folding<br>Graph Algorithms and Graph Minors<br>Combinatorial Games, Puzzles, and Magic
Big Data

Research Summary

Professor Demaine does his research in the Computer Science and Artificial Intelligence Laboratory (CSAIL), where he is a member of the Theory of Computation group. Professor Demaine's research centers around algorithms, data structures, and geometry.

The Demaine lab focuses on problems that span the mathematics and computer science boundary. We are interested in abstract geometry problems related to folding and bending that have practical applications in manufacturing (sheet metal fabrication) and biology (protein-folding).

Folding and unfolding is an exciting area of geometry. It is attractive in the way that problems and even results can be easily understood, with little knowledge of mathematics or computer science, yet the solutions are difficult and involve many sophisticated techniques. The general sort of problem considered is how a particular object (e.g., linkage, piece of paper, polyhedron, or protein) can be reconfigured or folded according to a few constraints, which depend on the object being folded and the problem of interest. In particular, we are interested in efficient algorithms for characterizing foldability, and finding efficient folding processes, or in proving that such algorithms are impossible.

Recent Work