15-855 Graduate Computational Complexity Theory

12 units, Carnegie Mellon University

The overarching goal is for students to learn the foundational aspects of structural complexity theory developed in the period 1970-2010. Students should learn the foundational relationships between time, space, and nondeterminism in computational complexity. Students will learn about circuit classes, how they relate to uniform models of computation, tools for proving circuit lower bounds, and also reasons why proving lower bounds are difficult. Students will be exposed to the pervasive role of randomness in complexity theory, even in the proof of purely deterministic results. By the end of the course, students will be able to study and contribute to cutting-edge research in computational complexity theory.

Prerequisites: none listed

Offered: Fall 2026

Courseweave needs JavaScript to show sections, workloads and planning tools.