Theory

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.

Events in Theory

Computer Science Thesis Proposal

September 27, 2023

The Kikuchi Matrix Method: Algorithms for “Beyond Average-Case” CSPs

Algorithms, Combinatorics and Optimization Seminar

September 14, 2023

h-vector inequalities for weak maps of matroids

News in Theory, Artificial Intelligence

Sandholm Earns AAAI Award for Artificial Intelligence That Benefits Humanity

Thursday, February 2, 2023

Tuomas Sandholm, a professor in Carnegie Mellon University's School of Computer Science, will receive the AAAI Award for Artificial Intelligence for the Benefit of Humanity to recognize his contributions to the design and implementation of

Friday, November 4, 2022

A Computer Science Department team received the George Nicholson Prize in Operations Research, which recognizes the best student-written paper at the 2022 Institute for Operations Research and the Management Sciences (INFORMS) annual meeting. Ziv Scully

Last	First	Professional Title	Available To Advise?
Acar	Umut	Associate Professor	✔
Balcan	Maria	Professor	✔
Beckmann	Nathan	Associate Professor	✔
Blelloch	Guy	Professor	✔
Blum	Manuel	University Professor Emeritus	✖
Gupta	Anupam	Professor	✔
Harchol-Balter	Mor	Professor	✔
Jain	Aayush	Assistant Professor	✔
Kolter	Zico	Associate Professor	✔
Kothari	Pravesh	Assistant Professor	✔
Miller	Gary	Professor Emeritus	✖
O'Donnell	Ryan	Professor	✔
Rudich	Steven	Professor	✔
Sandholm	Tuomas	Angel Jordan University Professor of Computer Science	✔
Schwartz	Russell	Professor, Affiliated Faculty	✔
Shah	Nihar	Associate Professor	✔
Shi	Elaine	Associate Professor	✔
Sleator	Daniel	Professor	✔
Vinayak	Rashmi Korlakai	Associate Professor	✔
Wang	Weina	Assistant Professor	✔
Woodruff	David	Professor	✔

Subscribe to Theory