Carnegie Mellon University 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, as well as identify the inherent limitations of efficient computation. Research interests include data structures, algorithm design, complexity theory, coding theory, parallel algorithms and languages, machine learning theory, cryptography and security, computational aspects of economics, online algorithms, and scientific computing.

The faculty routinely offer advanced courses on various topics in the frontier of research in theoretical computer science (there are typically 2-3 such courses every semester). We also have a very active schedule of research seminars, including a weekly theory seminar, ACO seminar, and theory lunch (which is run by our graduate students): see the seminars' page for the schedule.

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 for the inter-disciplinary program in Algorithms, Combinatorics and Optimization.

Splay Tree picture
Machine learning, computational aspects in economics and game theory, algorithms.

Parallel algorithms and languages.

Machine learning, approximation and on-line algorithms, AI planning.

Real-number models of computation.

Cryptography, Complexity Theory, Program Checking.

Average case analysis of algorithms, random graphs, combinatorics.

Cryptography, security, complexity theory

Approximation algorithms, metric embeddings, network algorithms.

Coding theory, Approximation Algorithms and Hardness of Approximations, Complexity Theory.

Scheduling theory, queuing theory, networks, heavy-tailed analysis.

Algorithms, Distributed Algorithms, Network Coding

Algorithm design, spectral graph theory, computational geometry, topological inference, parallel algorithms, scientific computing.

Complexity Theory, Algorithms.

Algorithmic game theory, Computational social choice

Approximation algorithms, combinatorial optimization, computational biology.

Complexity theory, cryptography, combinatorics.

Data structures, algorithms, parsing.

Machine learning, high-dimensional inference, sparse coding, evolving graphs, convex optimization.

Affiliated Faculty & Friends
Human Computation.

Combinatorics, Graph theory, Random graphs.

Combinatorics, graph theory, discrete geometry

Combinatorial optimization, Graph theory, integer programming.

Theory of security, privacy and cryptography.

Massive data sets, parallel computation, electronic commerce.

Combinatorics, Graph Theory, Randomness.

probabilistic combinatorics, combinatorical game theory, graph theory, and discrete geometry

Algorithms, especially for Scheduling and Power management

Mechanism Design, Game Theory, Auctions.

Computational Biology.

Theory of Computation, symbolic computation.

Postdocs and Visitors
Randomized algorithms, dimension reduction, coding theory

Clustering, high-dimensional data, data streams, dynamic flows

(advised by Ryan O'Donnell)

(advised by Ryan O'Donnell)

(advised by Guy Blelloch)

(advised by Venkat Guruswami and Gary Miller)

(advised by Guy Blelloch)

(advised by Mor Harchol-Balter)

(advised by Guy Blelloch)

(advised by Anupam Gupta)

(advised by Avrim Blum and Ariel Procaccia)

(advised by Bernhard Haeupler)

(advised by Venkat Guruswami)

(advised by Anupam Gupta)

(advised by Bernhard Haeupler)

(advised by Bernhard Haeupler)

(advised by Manuel Blum and Anupam Gupta)

(advised by Guy Blelloch)

(advised by Ariel Procaccia)

(advised by Bernhard Haeupler)

(advised by Nina Balcan)

(advised by Anupam Gupta and Ryan O'Donnell)

(advised by Venkat Guruswami)

(advised by Gary Miller)

(advised by Ryan O'Donnell)

(advised by Bernhard Haeupler)

John Wright (2016)
MIT (Postdoc)

U Penn (Postdoc)

EPFL (Postdoc)

Harvard (Postdoc)

Nisarg Shah (2016)
U. Toronto

Carol Wang (2015)
National University of Singapore (Postdoc)

Yuan Zhou (2014)

Julian Shun (2014)
Berkeley (Miller Fellow)

Ankit Sharma (2014)
Solvvy and MPI

Microsoft Research (Postdoc)

Georgia Tech.


Or Sheffet (2013)
U. Alberta

Lawrence Berkeley Labs

Eric Blais (2012)
U. Waterloo

Microsoft Research (India)

UIUC (postdoc)

Mahidol University

Don Sheehy (2011)
INRIA (Paris)

Varun Gupta (2011)
University of Chicago School of Business and Google Research

Mike Dinitz (2010)
Johns Hopkins University

Rocket Fuel Inc.

Aaron Roth (2010)

Yi Wu (2010)

Todd Phillips (2009)

David Abraham (2009)

Viswanath Nagarajan (2009) (ACO Tepper)
University of Michigan


Karl Wimmer (2009) (ACO Math)
Duquesne University

Pall Melsted (2009) (ACO Math)

Prasad Chebolu (2009) (ACO Math)
Liverpool University (postdoc)

Howard University

Maverick Woo (2009)

Nina Balcan (2008)
Georgia Tech.

Barbara Anthony (2008) (ACO Math)
Southwestern University

AT&T Research


Vineet Goyal (2008) (ACO Tepper)
Columbia IEOR

Mohit Singh (2008) (ACO Tepper)
Microsoft Research and McGill University



Ryan Williams (2007)

Benoit Hudson (2007)
TTI Chicago

Hubert Chan (2007) (CS & ACO)
University of Hong Kong

Adam Weirman (2007)

University of Puerto Rico


Lea Kissner (2006)

Konstantin Andreev (2006) (ACO Math)
Cygma Financial

Google (Pittsburgh)

Abie Flaxman (2006) (ACO Math)
University of Washington

Juan Vera (2006) (ACO Math)
University of Waterloo

Dan Blandford (2005)

Shuchi Chawla (2005)
University of Wisconsin (Madison)


Luis von Ahn (2005)
Carnegie Mellon

Umut Acar (2004)
Carnegie Mellon

Nick Hopper (2004)
University of Minnesota

Amitabh Sinha (2004) (ACO Tepper)
University of Michigan (Ann Arbor)

Ke Yang (2004)


Nikhil Bansal (2003)
TU Eindhoven

Jochen Konemann (2003) (ACO Tepper)
University of Waterloo

Ojas Parekh (2003) (ACO Tepper)
Emory University

John Langford (2002)
Microsoft Research (NYC)

Adam Kalai (2001)
Microsoft Research (New England)

Carl Burch (2000)
Hendrix College

Goran Konjevod (2000) (ACO Tepper)
Arizona State University

Federal University of Rio de Janeiro

Andrea Richa (1998)
Arizona State University

Endeca (Chief Scientist)

Yuri Smirnov (1997)

Georgia Tech

Dafna Talmor (1997)

University of California (Berkeley)

Yahoo Research

Keith Gremban (1996)

Anja Feldmann (1995)
Technical University of Berlin

NASA Langley Research Center

Jeff Jackson (1995)
Duquesne University

Jiri Sgall (1994)
Charles University (Prague)

Mike Molloy (1994) (ACO Math)
University of Toronto

James Aspnes (1992)
Yale University

AT&T Research

Colin Cooper (1989) (ACO Math)
King's College (London)

Lyle McGeoch (1987)
Amherst College

Amherst College

Andrew Appel (1985)
Princeton University

University of Chicago and IIT Bombay


University of Southern California

Georgia Tech.

Graduate Theory Courses scheduled for Spring 2017
Previous Semester Theory Courses
Useful Theory-related Links
talks of interest to the algorithms and complexity crowd

Wednesdays at noon

Thursday afternoons

Add yourself to the mailing list using this form
(You needn't bother creating a password if you don't want to).