CS 764: Computational Complexity

University of Waterloo, Winter 2026

Gold lever excapement watch by John Leroux (1785) by the Science Museum, London / CC BY 4.0

Overview

Computational Complexity aims to explore the ultimate limits of what computers can do when they have bounded resources.

This course will give an overview of some of the main themes that have emerged from this line of research. We will do so by seeing some of the foundational results in complexity theory, examining some of the unexpected connections to different areas of mathematics, and discussing a few of the many open problems in the area.

Many of our in-class discussions will be focussed on the standard model of Turing machines. However, since much of modern complexity theory deals with other models of computation, each participant in the class will also choose an area of specialization in which they will explore the main themes of the course in more depth.

Suggested Areas of Specializations

Here is a partial list of possible choices for the specializations:

Non-uniform models of computation

• Communication Complexity
• Query Complexity (also known as decision tree complexity)
• Circuit Complexity
• Formula Complexity

Uniform models of computation

• Fine-Grained Complexity
• Fixed-Parameter Complexity
• Hardness of Approximation

Alternative models of computation

• Complexity of Streaming Algorithms
• Complexity of Sublinear-Time Algorithms
• Algebraic Circuit Complexity
• Proof Complexity
• Massively Parallel Computation
• Distributed Computation (LOCAL/CONGEST models)
• Polynomial Degree Complexity

Tentative List of Topics

Some of the main themes that we will explore through the lens of computational complexity in this class include the following:

• Time Complexity
• Space Complexity
• Computing with Some Help
• Verification
• Interactive Computation
• Uniform vs. Non-Uniform Computational Models
• Randomness
• Hardness Amplification
• Complexity Trade-Offs

Components of the Course

The course contains three main components:

• In-class discussions. The course delivery will include a number of different formats. On top of more traditional lectures, we will also have a number of different activities throughout the term, including group problem-solving sessions, readings of original materials, and ongoing discussions.

• Journal. In lieu of standard homework assignments or examinations, each participant in the class will keep a research/study journal keeping a record of their learning and discoveries within their specialization area and beyond.

• Research Project. The final component of the course will be a research project on one of the open problems related to each participant’s area of specialization.