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

Faculty
Machine learning, computational aspects in economics and game theory, algorithms.

Parallel algorithms and languages.

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

Algorithms, the Sum-of-Squares method, Extended Formulations

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.

Statistics, machine learning, information theory, game theory, social choice theory

Data structures, algorithms, parsing.

Coding theory, Information theory, Computer systems and networks

Applied probability and stochastic systems with applications to data centers, cloud computing, and privacy-preserving data analytics

Data streams, dimensionality reduction, machine learning, numerical linear algebra, sparse recovery.

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.

Algorithms, scheduling, distributed computing, machine learning, combinatorial optimization.

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

Algorithms, especially for Scheduling and Power management

Mechanism Design, Game Theory, Auctions.

Computational Biology.

Postdocs and Visitors
real algebraic geometry, discrete and convex geometry, optimization, connections to algorithms and complexity

additive combinatorics and theoretical computer science

codes, property testing, and applications of group theory to computer science, graph theory and the analysis of boolean functions

Students
(advised by Umut Acar and Guy Blelloch)

(advised by Venkatesan Guruswami and Pravesh Kothari)

(advised by Ryan O'Donnell)

(advised by Pravesh Kothari and David Woodruff)

(advised by Guy Blelloch)

(advised by Mor Harchol-Balter)

(advised by Gary Miller)

(advised by Guy Blelloch)

(advised by Guy Blelloch)

(advised by Anupam Gupta and Ariel Procaccia)

(advised by Ariel Procaccia)

(advised by Mor Harchol-Balter)

(advised by Guy Blelloch)

(advised by Bernhard Haeupler)

(advised by David Woodruff)

(advised by David Woodruff)

(advised by Ariel Procaccia)

(advised by Nina Balcan and Ameet Talwalkar)

(advised by Anupam Gupta)

(advised by Anupam Gupta and Bernhard Haeupler)

(advised by Venkatesan Guruswami)

(advised by Vipul Goyal)

(advised by Venkat Guruswami)

(advised by Nina Balcan and Tuoas Sandholm)

(advised by Ryan O’Donnell)

(advised by Ryan O’Donnell)

(advised by Vipul Goyal)

(advised by Venkat Guruswami and Bernhard Haeupler)

(advised by Venkat Guruswami)

(advised by Mor Harchol-Balter)

(advised by Bernhard Haeupler)

(advised by Nina Balcan)

(advised by Vipul Goyal)

(advised by Guy Blelloch)

(advised by Nina Balcan and Tuomas Sandholm)

(advised by Bernhard Haeupler)

(advised by Gary Miller)

(advised by Guy Blelloch and David Woodruff)

(advised by Guy Blelloch)

(advised by Mor Harchol-Balter and Weina Wang)

(advised by Weina Wang)

(advised by Pravesh Kothari and Ryan O'Donnell)

(advised by Ryan O'Donnell)

(advised by Bernhard Haeupler)

Alumni
Princeton and IAS (Postdoc)

Yihan Sun (2019)
University of California, Riverside (UCR)

Yan Gu (2018)
University of California, Riverside (UCR)

Google

Cornell

Sahil Singla (2018)
Princeton and IAS (Postdoc)

Colin White (2018)

Euiwoong Lee (2017)
Simons and NYU (Postdoc)

Amherst College

David Witmer (2017)

Shen Chen Xu (2017)
Facebook

John Wright (2016)
MIT (Postdoc)

Georgia Tech.

Google

OpenAI

Nisarg Shah (2016)
U. Toronto

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

Yuan Zhou (2014)
Indiana U.

Julian Shun (2014)
MIT

Ankit Sharma (2014)
Google

Purdue

Georgia Tech.

Rutgers

Or Sheffet (2013)
U. Alberta

Lawrence Berkeley Labs

Eric Blais (2012)
U. Waterloo

Microsoft Research (India)

Ekonomi ve Teknoloji Üniversitesi, Ankara, Turkey

Mahidol University

Don Sheehy (2011)
University of Connecticut

Varun Gupta (2011)
University of Chicago School of Business

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)
University of Michigan

Hebrew U.

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

Ryan Williams (2007)
MIT

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 2019
Previous Semester Theory Courses
Courses from Spring 2017

Useful Theory-related Links
talks of interest to the algorithms and complexity crowd

Wednesdays at noon

Thursday afternoons (and subscribe to mailing list)

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