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 accepting applications for a postdoc position! Click on the Openings link below for details.

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

Machine learning and high dimensional data analysis, statistical learning theory.

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

Complexity Theory, Algorithms.

Approximation algorithms, combinatorial optimization, computational biology.

Complexity theory, cryptography, combinatorics.

Data structures, algorithms, parsing.

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.

Extremal (hyper)graphs and Ramsey theory, Combinatorics.

Algorithms, especially for Scheduling and Power management

Mechanism Design, Game Theory, Auctions.

Computational Biology.

Theory of Computation, symbolic computation.

Postdocs and Visitors
Parallel Computation

Spectral graph theory, Combinatorial Scientific Computing, Parameterized Algorithms, Numerical Linear Algebra.

Hardness of approximations, PCPs, learning theory, metric embeddings and integrality gaps.

Scientific Computation

Computational Geometry, Mesh Generation, and Scientific Computing

Students
Machine learning theory

Complexity Theory

Computational Geometry, Claytronics

Data Structures, Auction Theory, Algorithms

Network Algorithms, graph theory, algorithms

Scheduling theory

Approximation Algorithms

Network Science

Computational game theory, Privacy

Machine learning theory

Algorithms, Computational Geometry, Computational Topology

Parallel algorithms

Complexity theory

Computational Geometry, Distributed Systems

Computational Biology, Scientific Computing, Inverse Problems

Complexity theory

Alumni
Todd Phillips (2009)
CMU (postdoc)

David Abraham (2009)
Google

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

Cornell University (postdoc)

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

Caltech (postdoc)

Vineet Goyal (2008) (ACO Tepper)
MIT (postdoc)

Mohit Singh (2008) (ACO Tepper)
McGill University

Facebook

IAS (postdoc)

Ryan Williams (2007)
IBM Almaden (Raviv Fellow)

Benoit Hudson (2007)
TTI Chicago

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

Adam Weirman (2007)
CalTech

CMU (postdoc)

Google

Lea Kissner (2006)
Google

Konstantin Andreev (2006) (ACO Math)
Cygma Financial

Google (Pittsburgh)

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

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

Dan Blandford (2005)
Google

Shuchi Chawla (2005)
University of Wisconsin (Madison)

Google

Luis von Ahn (2005)
Carnegie Mellon

Umut Acar (2004)
TTI Chicago

Nick Hopper (2004)
University of Minnesota

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

Ke Yang (2004)
Google

Brown University (postdoc)

Nikhil Bansal (2003)
IBM T.J.Watson Research Center

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

Ojas Parekh (2003) (ACO Tepper)
Emory University

John Langford (2002)
Yahoo 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.

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

Wednesdays at noon

Thursday afternoons

lists of papers

Simons Postdoctoral Fellowship in Theoretical Computer Science

The Simons Foundation has awarded Carnegie Mellon a Postdoctoral Fellowship in Theoretical Computer Science for the two-year period Fall 2010 through Summer 2012. Applicants must have received a PhD in the academic year immediately preceding the fellowship (i.e. 2009-2010). Postdoctoral Fellows will have opportunity to work with all members of the Algorithms and Complexity group at CMU. In addition to salary, fellows will receive a $7,000/year travel/equipment research budget.

Applications (CV and research statement) as well as recommendation letters should be sent to Marilyn Walgora at mwalgora [at] cs.cmu.edu. Please include the words "Simons Postdoctoral Fellowship" in the header.

For full consideration, applications should be received by February 28, 2010.