Winter 2026: Computability and Complexity (CSCC63)
Winter 2026: Computability and Complexity (CSCC63)
The question of which tasks can be performed efficiently is central to the human experience, since time and other resources are always in shortage.
The field of computational complexity studies the effects of limited resources: How does restricting the time, memory, and other resources available to algorithms affect their ability to perform tasks? This question is formulated and studied as generally as possible and with mathematical rigor, using well-defined abstract notions of algorithms, tasks, and resources.
This course will serve as an introduction to the field. Its goals include:
Learn models and methodologies used in computational complexity, including models for algorithms, computational tasks, and resources.
Learn basic definitions and results in computability theory, such as the universal machine, the halting problem, and the universal problem.
Learn basic definitions, questions, and results in computational complexity, such as complexity classes, hierarchy theorems, P vs NP, and NP-completeness.
Get a glimpse into a few advanced topics in computational complexity and cryptography, such as fine-grained complexity, interactive proof systems, pseudorandomness, one-way functions, and zero-knowledge.
In class I showed the slides on one projector, simultaneously showed relevant supplementary material on an adjacent projector, and used several large blackboards to give intuition and fill in missing details. This was an amazing setup. The blackboard is crucial (slides aren't enough and intuition is necessary for this course), but if I only had one projector, I could go back-and-forth between slides and supplementary materials on it.
Weekly tutorials were used to teach more examples of core content (e.g., examples of NP-complete problems, hardness of approximation, fine-grained reductions, computability reductions, etc.) or to solve exercise-type questions that help internalize the material.
Assignments were without grades, and without a deadline on submission, though it was expected that students follow new questions on a more-or-less weekly basis. The course had two midterms and a final exam.