The Algorithms Group

Images from 6.046 class notes, E. Demaine Images from 6.046 class notes, E. Demaine Images from 6.046 class notes, E. Demaine Images from 6.046 class notes, E. Demaine

*Further details can be found on faculty and students' web pages. Links to these pages are under the people section.

Examples of current & recent projects include:

Instance-Optimal Algorithms for Black-Box Curve Manipulation
Ilya Baran, Erik D. Demaine

Folding and Unfolding in Computational Geometry
Erik D. Demaine and Martin L. Demaine

(Fixed Parameter) Algorithms for Graphs Excluding a Minor
Erik D. Demaine, Mohammad Taghi Hajiaghayi

Algorithmic Combinatorial Game Theory
Erik D. Demaine, Martin L. Demaine, Robert A. Hearn, Susan Hohenberger, David Liben-Nowell

Cache-Oblivious Data Structures
Erik D. Demaine

Estimating Trends in an Internet Packet Stream Using Little Memory
Erik D. Demaine, Alejandro L´opez-Ortiz, J. Ian Munro

Expander-based Constructions of Efficient Error-correcting Codes
Piotr Indyk and Venkatesan Guruswami (with a great help from Madhu Sudan)

Research in Algorithms for Geometric Pattern Matching
Piotr Indyk and Nitin Thaper

Approximate Algorithms for High-dimensional Geometric Problems
Piotr Indyk and Mihai Badoiu

Sublinear Algorithms for Massive Data Sets
Piotr Indyk and S. Muthukrishnan

Applied Algorithms
D. R. Karger, J. Feldman, D. Liben-Nowell, M. Minkoff, M. Ruhl, N. Srebro

Maximum Likelihood Markov Hypertrees
N. Srebro, D. Karger, Percy Liang, T. Jaakkola

Finding Maximum Flows in Undirected Graphs
David Karger and Matthew Levine

Profit-making under uncertainty
Avrim Blum, Shuchi Chawla, David Karger, Terran Lane, Adam Meyerson, and Maria Minkoff

Network design under uncertainty
David Karger and Maria Minkoff

Searching in Peer-to-Peer Networks
David R. Karger, Matthias Ruhl

Computational Models for Massive Data Sets
Matthias Ruhl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan

Algorithms for Decoding Turbo Codes and LDPC Codes
Jon Feldman, David Karger and Martin Wainright

Consistent Load Balancing Via Spread Minimization
Robert Kleinberg and Tom Leighton

Optimal Outlier Removal in High-Dimensional Spaces
John Dunagan, Santosh Vempala

How to cluster data
Santosh Vempala, Adrian Vetta, Grant Wang

Combinatorial Optimization
Alantha Newman, John Dunagan, Santosh Vempala, Adrian Vetta

Fast algorithms via Random walks
Santosh Vempala



Massachusetts Institute
of Technology
77 Massachusetts Avenue
Cambridge, MA 02139