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.

We are delighted that Bernhard Haeupler will be joining us as a new faculty member in Fall 2014!

Splay Tree picture
Faculty
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.

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.

Combinatorial optimization, Graph theory, integer programming.

Theory of security, privacy and cryptography.

Massive data sets, parallel computation, electronic commerce.

Combinatorics, Graph Theory, Randomness.

Algorithms, especially for Scheduling and Power management

Mechanism Design, Game Theory, Auctions.

Computational Biology.

Theory of Computation, symbolic computation.

Postdocs and Visitors
computational topology, computational geometry, algorithms

Algorithms, approximation algorithms, average-case complexity

Students
(advised by Ryan O'Donnell)

(advised by Manuel Blum and Anupam Datta)

(advised by Mor Harchol-Balter)

(advised by Anupam Gupta)

(advised by Avrim Blum and Ariel Procaccia)

(advised by Venkat Guruswami)

(advised by Avrim Blum and Frank Pfenning)

(advised by Ariel Procaccia)

(advised by Avrim Blum and Anupam Gupta)

(advised by Guy Blelloch)

(advised by Manuel Blum and Anupam Gupta)

(advised by Venkat Guruswami and Gary Miller)

(advised by Venkat Guruswami)

(advised by Gary Miller)

(advised by Anupam Gupta and Ryan O'Donnell)

(advised by Ryan O'Donnell)

(advised by Venkat Guruswami)

(advised by Gary Miller)

(advised by Venkat Guruswami and Ryan O'Donnell)

Alumni
MIT

Princeton (Postdoc)

Or Sheffet (2013)
Berkeley Simons Center

Lawrence Berkeley Labs

Eric Blais (2012)
MIT (Simons postdoc)

Princeton (Simons postdoc)

Princeton (postdoc)

IBM Research

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)
U.Penn

Yi Wu (2010)
Purdue

Todd Phillips (2009)
Google

David Abraham (2009)
Google

Viswanath Nagarajan (2009) (ACO Tepper)
IBM T.J.Watson Research Center

Caltech

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)
CMU

Nina Balcan (2008)
Georgia Tech.

Barbara Anthony (2008) (ACO Math)
Southwestern University

AT&T Research

Google

Vineet Goyal (2008) (ACO Tepper)
Columbia IEOR

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

Facebook

Stanford

Ryan Williams (2007)
Stanford

Benoit Hudson (2007)
TTI Chicago

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

Adam Weirman (2007)
CalTech

University of Puerto Rico

Google

Lea Kissner (2006)
Google

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)
Google

Shuchi Chawla (2005)
University of Wisconsin (Madison)

Facebook

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)
Google

Google

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)
Akonite

Georgia Tech

Dafna Talmor (1997)
Intel

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

MIT

University of Southern California

Georgia Tech.

Graduate Theory Courses scheduled for Fall 2011
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).

lists of papers