Algorithms and Computational Complexity at CMU

CMU has a strong and diverse group in Algorithms and Complexity Theory. The goals of the group are, broadly speaking, to provide a mathematical understanding of fundamental issues in Computer Science, and to use this understanding to produce better algorithms, protocols, and systems. Research interests include data structures, algorithm design, complexity theory, parallel algorithms and languages, machine learning theory, cryptography and security, on-line algorithms and scientific computing. Our Algorithms and Complexity group maintains strong ties to other areas, such as computer systems, programming languages, and artificial intelligence, and we welcome students who have a combination of theoretical and application-oriented research interests. See also the ACO Program Home Page and the ALAddIN home page.

Faculty not shown: L.Blum, Harchol-Balter, Lafferty, Maggs, Miller, O'Donnell, Rudich, Sleator.

Faculty

Guy Blelloch	Parallel algorithms and languages.
Avrim Blum	Machine learning, approximation and on-line algorithms, AI planning.
Lenore Blum	Real-number models of computation.
Manuel Blum	Cryptography, Complexity Theory, Program Checking.
Alan Frieze (Math)	Average case analysis of algorithms, combinatorics.
Anupam Gupta	Approximation algorithms, metric embeddings, network algorithms.
Mor Harchol-Balter	Scheduling theory, queuing theory, networks, heavy-tailed analysis.
John Lafferty	Speech and natural language processing, statistical learning algorithms, information theory.
Bruce Maggs	Parallel algorithms and architectures, computer networks.
Gary Miller	Algorithm design, parallel algorithms, scientific computing.
Ryan O'Donnell	Complexity Theory, Algorithms.
R. Ravi (Tepper School)	Approximation algorithms, combinatorial optimization, computational biology.
Steven Rudich	Complexity theory, cryptography, combinatorics.
Danny Sleator	Data structures, algorithms, parsing.

Visitors and Postdocs

Ioannis Koutis	Scientific Computation
Danny Segev	Algorithms and Combinatorics
David Tolliver	Scientific Computation
Ryan Williams	Complexity, algorithms

Other postdocs and visitors in the recent past included Susanne Albers (from U. Freiburg), MohammadTaghi Hajiaghayi (now at MIT), Jason Hartline (now at Microsoft Research), Jon Kleinberg (from Cornell University), Stefano Leonardi (from University of Rome La Sapienza), Adam Meyerson (now at UCLA), Harald Räcke (now at the University of Warwick), and Vijaya Ramachandran (from UT Austin).

Affiliated Faculty and Friends

Luis von Ahn	Human Computation
Tom Bohman	Combinatorics, Graph theory, Random graphs.
Gerard Cornuejols	Combinatorial optimization, Graph theory, integer programming.
Anupam Datta	Theory of security, privacy and cryptography
Phil Gibbons	Massive data sets, parallel computation, electronic commerce.
Oleg Pikhurko	Extremal (hyper)graphs and Ramsey theory, Combinatorics.
Tuomas Sandholm	Mechanism Design, Game Theory, Auctions.
Russell Schwartz	Computational Biology.
Dawn Song	Computer security and applied cryptography.
Richard Statman	Theory of Computation, symbolic computation.

Students

David Abraham	Algorithms
Barbara Anthony	Approximation Algorithms
Nina Balcan	Machine learning theory, Algorithmic Game Theory, and Algorithms
Eric Blais	Complexity Theory
Hubert Chan	Metric embeddings, algorithms
Jon Derryberry	Data Structures, Auction Theory, Algorithms
Michael Dinitz	Algorithms, metric embeddings, complexity theory, graph theory
Sam Ganzfried	Algorithms, AI, Combinatorics
Daniel Golovin	Approximation algorithms
Vineet Goyal	Approximation algorithms
Benoît Hudson	Computational Geometry
Katrina Ligett	Algorithms, Learning Theory
Viswanath Nagarajan	Approximation algorithms
Todd Phillips	Computational Geometry and Meshing
Aaron Roth	Computational game theory
Mugizi Robert Rwebangira	Machine learning, graph-based learning algorithms
Don Sheehy	Algorithms, Computational Geometry
Mohit Singh	Approximation algorithms
Srinath Sridhar	Algorithms, Computational Biology
Kanat Tangwongsan	Computational Geometry, Distributed Systems
Virginia Vassilevska	Graph Theory, Algorithms
Shobha Venkataraman	Computer security, MDPs, Bayes nets, Mechanism design
Maverick Woo	Data structures for search engines, graph theory

Recent Graduates

Seminars

This master list includes Theory Seminars, ACO Seminars and Theory lunch.

Projects with home pages

ALAddIN: Algorithms, Adaptation, and Dissemination.
SANGRIA: Parallel geometric and numerical algorithms for simulating blood flow.
Graphplan: graph-algorithm based AI planning.
Link Grammar: an English parser based on a new theory of syntax.
SCANDAL: implementation of parallel algorithms.
PSCICO: Parallel Scientific Computing.

Graduate Courses

15-750 Algorithms Core (Every Spring)
15-853 Algorithms in the Real World (Every Fall)
15-854 Approximation and Online Algorithms (Fall 05) [ S00 ]
15-855 Complexity Theory (Every other Fall - even years)
15-859 Computational Geometry (Fall 04) [ F03, F01 ]
15-892 Foundations of Electronic Marketplaces (Fall 05) [ F03 ]
15-859 Machine Learning Theory (Spring 06) [ S02 | S02 | S98 ]
15-859 Mathematical Games (Spring 05) [ F01]
15-859 Metric Methods (Fall 03)
15-849 Performance Modeling (Fall 03)
33-658 Quantum Computing (Spring 06) [ S02 ]
15-859 Randomized Algorithms (Fall 04) [ F98 ]
Random Graphs (Spring 06)
15-859 Scientific Computing and Spectral Methods (Fall 05) [ S03, F00 ]
21-801 Sampling, Counting and Rapidly Mixing Markov Chains (Spring 01)
Web Structures and Algorithms (Fall 04)
47-863 Computational Biology (Spring 01)
11-767 Information Theory and Machine Learning (Fall 00)

Back to the Computer Science Department Page
Maintained by Avrim Blum, Anupam Gupta, and Don Sheehy.

Last updated September, 2007.