Ph.D. in Algorithms, Combinatorics, and Optimization

To a great extent, the mathematics used by computer scientists and operations researchers overlap. 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 matching 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 is intended to fill this gap. It brings together the study of the mathematical structure of discrete objects and the design and analysis of algorithms in areas such as:

• Network Optimization
• Combinatorial Optimization
• Integer Programming
• Polyhedral Theory
• Computational Algebra
• Convex and Discrete Geometry
• Number Theory

Course Study

The coordinating committee has established a challenging core curriculum in analysis, algebra, probability, combinatorics, linear and integer programming, graph theory, convex optimization, algorithms, and complexity theory. For more information, see the separate brochure for the Algorithms, Combinatorics, and Optimization program, or go to the ACO homepage.

Please visit our Ph.D. Student Profiles page to view the profiles of our current doctoral candidates.

Requirements

The Coordinating Committee has established a challenging core curriculum in Analysis, Algebra, Probability, Combinatorics, Linear and Integer Programming, Graph Theory, Convex Optimization, Algorithms, and Complexity Theory.

Besides the core courses, a host of other courses are available for the students to take. Some examples are combinatorial optimization, graph coloring, matroid theory, convex polytopes, location theory, sequencing and scheduling, large scale OR, parallel algorithms, probabilistic analysis of algorithms, approximation algorithms, machine learning theory, cryptography, nonlinear programming, and constraint programming. In the event that a student has already mastered a core course at the graduate level when entering the program, another course from the same department may be substituted. Approval must be obtained from the ACO Coordinating Committee and is given on a case-by-case basis. In addition, the students are expected to participate in the weekly research seminar on Algorithms, Combinatorics, and Optimization.

As in all other areas of study, the first-year and second-year research papers are required of all doctoral students.

At the end of their third semester in residence, the students take a comprehensive qualifying examination based on the material in five core courses. At this stage (or earlier), they choose a faculty member to supervise their research and dissertation. Approximately a year before the expected graduation date, the student must make a thesis proposal before a thesis committee, composed of the advisor and two or more faculty members of the student's choosing. The final transition point is the thesis defense, which is presented before the same committee. To graduate, the students will also need some teaching experience and must demonstrate adequate programming skills.