COMP 590: Computational Complexity

Spring 2026
Instructor: Saba Eskandarian
Contact: saba@cs.unc.edu
TA To be announced
Class Meetings: Tues/Thurs 2-3:15pm, FB007
Office Hours: TBA
Links:
Syllabus
Course Schedule
Canvas
Anonymous Feedback

Course Description

Computation is a powerful tool that has reshaped human life and solved centuries-old problems. But what are its limits? Are there some technical problems that simply cannot be solved by a combination of more ingenuity and silicon? Do we live in a world where the very structure of information in the universe prohibits efficient solutions to certain computational problems?

Motivated by these questions, this course explores the theory of Computational Complexity, an area of computer science concerned with understanding how computational resources allow us to solve problems of greater and greater complexity. Picking up where COMP 455 leaves off -- the celebrated P versus NP problem -- we will study various classes of computational problems, focusing on the techniques used to reason about the relationships between them.

Topics covered include time and space complexity classes, circuit complexity, randomized complexity classes, interactive proofs, and hardness of approximation. Along the way, we will find that the world of computational complexity is full of surprises and unexpected results that challenge our mathematical intuitions and preconceived notions of computation, randomness, and proof.

Textbook: Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak

Assignments

Each student will act as a scribe for two lectures, preparing detailed notes in Latex for the content covered in their assigned class meetings. Each student will also give a presentation on a relevant topic of their choice that is not covered in the class lecture materials. A list of suggested topics is provided in the assignment directions, linked below. Finally, students will complete the four problem sets below. Unless otherwise specified, assignments are submitted on Canvas.