Theory@CS.CMU

Carnegie Mellon University has a strong and diverse group in Algorithms and Complexity Theory. We try 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.

Our Algorithms and Complexity group maintains strong ties to other areas, such as computer systems, programming languages, and artificial intelligence, and we welcome students who have a combination of theoretical and application-oriented research interests. See the ACO Program home page (old page here) for the inter-disciplinary program in Algorithms, Combinatorics and Optimization.



Upcoming Seminars

(subscribe to the theory-announce mailing list here)

    

CMU Theory in the News

Jason Li, undergrad Zhiyang He, and collaborator Magnus Wahlstrom awarded best paper at ESA 2021
Alum Goran Zuzic co-winner of PODC 2021 Dissertation Award
Nina Balcan awarded Simons Investigator Award 2021
Isaac Grosof, Ziv Scully, and Mor Harchol-Balter awarded ACM SIGMETRICS 2021 Best Paper Award
Guy Blelloch receives 2021 Babbage Award from the IEEE Computer Society
Daniel Anderson and Guy Blelloch receive SPAA 2021 Best Paper Award
Emre Yolcu, Scott Aaronson, and Marijn Heule in MIT Tech Review about automated approach to the Collatz conjecture
Venkatesan Guruswami and David Woodruff awarded Simons Investigator Awards for 2020
Alums Naama Ben-David and Laxman Dhulipala runner-ups for SCS 2020 Best Dissertation Award

Faculty

The ordering of people on this page is randomized (as opposed to ordering alphabetically). Click here to read about biases due to alphabetical ordering.



Faculty Emeritus, or on Leave

(in random order)



Affiliated Faculty and Friends

(in random order)



Postdocs and Visitors

(in random order)




Students

(in random order)


Jackson Abascal

Jackson Abascal

(advised by Venkatesan Guruswami and Pravesh Kothari)

Magdalen Dobson

Magdalen Dobson

(advised by Guy Blelloch)

Justin Raizes

Justin Raizes

(advised by Vipul Goyal)

Yifan Song

Yifan Song

(advised by Vipul Goyal)

Yuanhao Wei

Yuanhao Wei

(advised by Guy Blelloch)

Jalani Williams

Jalani Williams

(advised by Weina Wang)


Alumni

(in reverse chronological order of Ph.D. dates)


Timothy Zhu

Timothy Zhu


Ph.D. 2021

Jeremiah Blocki

Jeremiah Blocki

Purdue
Ph.D. 2014

Ljubomir Perkovic

Ljubomir Perkovic


Ph.D. 1998