Graduate degree programs in algorithms, combinatorics and optimization are usually found at the doctoral level in the U.S. and are interdisciplinary in nature. Students generally take courses from areas like computer science and mathematics and may need to fulfill additional doctoral requirements, like qualifying exams and research seminars. Learn more about specific course topics and other requirements for the degree below.
Information for Doctor of Philosophy in Algorithms, Combinatorics and Optimization
Doctor of Philosophy (PhD) degree programs in algorithms, combinatorics and optimization usually require a dissertation and may require students to acquire programming skills and/or teaching experience throughout the program. Students in these programs are often able to pick and choose from various courses in optimization, computer science and mathematics, but here we discuss a few of the common course topics for these programs.
Students typically take a course that explores the probabilistic methods and techniques for a range of discrete mathematics and combinatorics. These courses may include foundational concepts in algorithms, expectation, variance and random graph theory. Other specific topics for these courses may include correlation inequalities, martingale concentration, Markov chains, branching processes and coupling.
PhD students in the field may take one or more courses that cover various topics in algebra. Usually these topics fall within linear and abstract algebra and continue to build off of knowledge that should have been gained in undergraduate-level algebra courses. Students in these courses may explore topics in matroids, finite fields, matrix groups, vector spaces, the Nielsen-Schreier theorem and the Jacobson radical.
Students generally take at least one course that focuses on algorithms, but may be paired with similar topics, such as computability. These courses generally train students how to design and program algorithms for a wide range of problems, like algebraic or combinatorial problems. Specific topics in these courses may include binomial heaps, NP-Completeness, probability, computational geometry, graph algorithms and splay trees.
Students in these programs may take a general course that explores graph theory and/or take a specialized course that may focus on a particular area of the field, such as spectral graph theory. Typically, topics in these courses are then applied to problems in computer science and operations research in order to create effective algorithms. Students may discuss topics in connectivity, perfect graphs, Ramsey theory, numerical linear algebra, low stretch trees and more.
Computational Complexity Theory
Courses in computational complexity theory may be offered at an introductory level. Students in these courses might explore current research findings in the field, as well as techniques and methods. These courses may discuss topics such as reducibility, complexity classes, completeness, hierarchy theorems, interactive proofs and pseudorandomness.
Common Entrance Requirements
Students wishing to apply to PhD programs in algorithms, combinatorics and optimization usually get to choose which department to apply through out of several choices from each institution. For example, some schools may allow students to apply to the mathematics, business or computer science department, while others schools may offer the program through their departments of computing, mathematics or industrial and systems engineering. Because of these options, application requirements vary, but may include materials like transcripts, GRE scores, GRE mathematics subject test, a personal statement, and/or letters of recommendation. Despite application differences, most of these programs are competitive and students will likely need to demonstrate strong academic skills.
Students can earn a PhD in algorithms, combinatorics and optimization after completing coursework in the field and a dissertation. They often have additional responsibilities, like teaching and attending research seminars, which must also be completed.