Carnegie Mellon University

Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics, and Optimization (ACO). This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group), and the Department of Mathematical Sciences (Discrete Mathematics group).

The mathematics used by computer scientists and operations researchers overlap to a large extent. The boundaries between Operations Research and Computer Science have become blurred. Important new theories and whole fields, like polyhedral combinatorics, have been and are being developed jointly by computer scientists, operations researchers, and applied mathematicians who consider themselves a little bit of both. Presentations of new results on graphs and matroid theory can be heard at Operations Research conferences, while papers on linear programming, network flows, and matchings in graphs are frequently presented at Computer Science conferences. The mathematical content of the papers has become greater and more diverse. Yet, in spite of this, few Ph.D students graduate with an equally solid knowledge of all three areas.

The Ph.D program in Algorithms, Combinatorics, and Optimization at Carnegie Mellon is intended to fill this gap. The program brings together the study of the mathematical structure of discrete objects and the design and analysis of algorithms in areas such as graph theory, combinatorial optimization, integer programming, polyhedral theory, computational algebra, geometry, and number theory.

Below is the list of expert faculty who will serve in the key areas of teaching within the ACO program.

Mathematical Sciences Faculty

Thomas Bohman

Extremal Combinatorics...

Profile

Boris Bukh

Combinatorial geometry, combinatorial number theory...

Profile

Florian Frick

Geometric and topological methods...

Profile

Alan Frieze

Average case analysis of algorithms, combinatorics...

Profile

Po-Shen Loh

Probabilistic and Extremal Combinatorics, and applications to Theoretical Computer Science...

Profile

Wesley Pegden

Combinatorics, Abelian Sandpile problem...

Profile

Computer Science Faculty

Nina Balcan

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

Profile

Guy Blelloch

Parallel algorithms and languages...

Profile

Manuel Blum

Complexity Theory, cryptography, program checking...

Profile

Anupam Gupta

Approximation algorithms, metric embeddings, network algorithms...

Profile

Venkatesan Guruswami

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

Profile

Bernard Haeupler

Design and analysis of combinatorial algorithms, distributed algorithms, information theory...

Profile

Mor Harchol-Balter

Queueing theory, stochastic modeling, probability theory, heavy-tailed workloads, Web servers, networking...

Profile

Gary Miller

Algorithm design, parallel algorithms, scientific computing...

Profile

Ryan O'Donnell

Complexity theory, analysis of boolean functions, approximation hardness...

Profile

Ariel Procaccia

Computational game theory, mechanism design, and computational social choice...

Profile

Steven Rudich

Complexity theory, cryptography, combinatorics...

Profile

Tuomas Sandholm

Market design, game theory, optimization (integer programming, search, stochastic optimization...)

Profile

Daniel Sleator

Data structures, algorithms, parsing...

Profile

Operations Research Faculty

Gérard Cornuéjols

Combinatorial optimization, graph theory, integer programming...

Profile

John Hooker

Operations research techniques in logic, artificial intelligence...

Profile

Fatma Kılınç-Karzan

Convex optimization, large-scale algorithms, decision making under uncertainty...

Profile

Benjamin Moseley

Design, analysis and evaluation of algorithms...

Profile

Javier Peña

Theory and algorithms for convex optimization, numerical analysis...

Profile

R. Ravi

Approximation algorithms, combinatorial optimization, computational biology...

Profile

Michael Trick

Computational integer and combinatorial optimization, applications in sports and the social sciences...

Profile

Willem Van Hoeve

Combinatorial optimization; constraint programming; mathematical programming; integration of constraint programming and mathematical programming...

Profile