The research area of Algorithms and Computational Complexity focuses on the development, analysis, and classification of algorithms—step-by-step procedures for solving problems—and the study of the resources they require, such as time and memory. Algorithms are essential to computer science, providing efficient methods to solve a wide range of problems, from sorting and searching to complex tasks like network routing and data encryption. Researchers in this area aim to design optimal algorithms that minimize computational resources while ensuring correctness, scalability, and adaptability to different problem settings.
Computational complexity examines the inherent difficulty of computational problems by categorizing them into complexity classes based on how efficiently they can be solved. For example, problems in the class P can be solved in polynomial time, while those in NP are problems for which solutions can be verified quickly, but finding the solution may not be efficient. The most famous open question in this area, P vs NP, asks whether every problem that can be verified quickly can also be solved quickly. Complexity theory also explores the limits of computation, identifying which problems are intractable or unsolvable and studying the relationships between various complexity classes. This research is crucial for understanding what can be computed in practice and influences fields like cryptography, optimization, and artificial intelligence.
Faculty
Rajeev Alur
Anindya De
Brett Hemenway
Sampath Kannan
Michael Kearns
Sanjeev Khanna
Robin Pemantle
Tal Rabin
Aaron Roth
Rakesh Vohra
