Doctoral Program in ACO

Carnegie Mellon University has taken the initiative of offering an interdisciplinary Ph.D program in Algorithms, Combinatorics, and Optimization. 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 ACO 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.

Questions about the ACO program can be addressed to any member of the ACO faculty.

Requirements

More information on specific courses can be found in the home departments:

• The Computer Science Department (Algorithms and Complexity group)
• The Department of Mathematical Sciences (Discrete Mathematics group)
• The Tepper School of Business (Operations Research group)

Courses

All ACO students will be required to take 2 semester CS classes, 2 semester Math classes, and the equivalent of 2 semester Tepper classes (i.e 4 mini classes). Also required is 1 probability class.

• • The 2 CS classes will include Algorithms (15-750), plus one additional theoretical class chosen from the following courses.
    
    • • 15-850 Advanced Algorithms
      • 15-855 Computational Complexity Theory
      • 15-857 Analytical Performance Modeling of Computer Systems
      • 15-859 Special Topics in Theory: Advances in Coding Theory
      • 15-859 Special Topics in Theory: Algorithmic Superpower Randomization
      • 15-859 Special Topics in Theory: Spectral Graph Theory and The Laplacian Paradigm
      • 15-896 Algorithms, Games, and Networks

• • The 2 Math classes will include Discrete Math (21-701), plus one additional math class from the following courses:
    
    • • 21-610 Algebra
      • 21-720 Measure and Integration
      • 21-737 Probabilistic Combinatorics
      • 21-738 Extremal Combinatorics

• • The 4 Tepper mini classes will include Linear Programming (47-834), Convex Optimization (47-851), Integer Programming (47-830) as required classes, plus one more mini from the following courses:
    
    • • 47-835 Graph Theory
      • 47-836 Networks and Matchings
      • 47-831 Advanced Integer Programming
      • 47-862 Constraint Programming
      • 47-xxx Combinatorial Optimization

Students who are based in the Tepper School are required to complete two additional mini classes from the Tepper school.

• • The 1 probability class will include one of: Probability (21-721), Probability Theory and Stoch Processes I (36-753), or Analytical Performance Modeling (15-857).

Students who are based in the Department of Mathematical Sciences with a start date on or after July 1, 2024 are required to complete the course requirements by the end of their 6th semester.

Qualifying Exam

Every ACO student will be required to take the same Qualifying Exam. This exam will be given in January after the student's 3rd semester. The exam will contain 1 question on Algorithms, 1 question on Discrete Math, 1 question on Linear Programming, 1 question on Convex Optimization, 1 question on Integer Programming. Please see http://aco.math.cmu.edu/ACO_CSD_qual_reqs.html for specific exam requirements for Computer Science Department ACO students.

Research

Research is obviously a big component of the ACO program. Each department has different research expectations, as well as policies, for when students should find research advisors. You should talk with your department head to understand the research expectations for your department.

Weekly Research Seminar

During your participation in the Algorithms, Combinatorics, and Optimization program, you are expected to participate in the weekly ACO research seminar. You are also expected to take advanced courses in the area of your research in addition to the course requirements listed above.

Dissertation

Regardless of your home department, by the end of the third semester (if not earlier), you must choose a faculty member to supervise your research and dissertation. As an ACO student, you will be subject to an annual review by the ACO faculty who will judge whether the thesis work is proceeding satisfactorily. The procedures for forming a thesis committee, completing a thesis proposal, and defending the thesis are governed by the rules of the student's home department.

Teaching and Programming Skills

To graduate, you will need some teaching experience, and all students must demonstrate programming skills. (For every student, a faculty member, approved by the student's advisor, must attest that the student has adequately demonstrated programming skills.)