uwloo

CS 764Computational Complexity

Units
0.50
Level
Graduate
Faculty
Mathematics
Subject
Computer Science

When it runs

  1. F24
  2. W25
  3. S25
  4. F25
  5. W26
  6. S26
  7. F26
  8. W27
  9. S27

Ran in 1 of the last 7 terms. Winter 2027: not on the schedule. Spring 2027: schedule not out yet.

Further exposure to the classification of problems based on their computational requirements and to mathematical tools designed to explore the structural consequences of such classifications. Topics include relativization, alternation, provably intractable problems, feasible parallel computation; fixed-parameter tractability and the W-hierarchy; Kolmogorov complexity, including algorithmic and algorithmic prefix complexity and their applications.

Prerequisites

None listed.

Antirequisites

  • Not completed nor concurrently enrolled in any of the following:
    • CS664 - Computational Complexity Theory (0.50)

Leads to

No course lists it as a requisite.

Resources

Around the web

Found by uwloo’s link finder, which checks that each page names CS 764.

Suggest a resource.

Discussed on r/uwaterloo

One post or comment in 1 thread mentions CS 764, January 2021 to December 2024. Quoted word for word, newest first; each reply sits under the post and the comment that started its branch. Search r/uwaterloo for newer posts.

Winter 2021

Check it elsewhere for Fall 2026

Calendar versions

Graduate Calendar

Older Graduate Calendars

In 42 terms, Fall 2006 to Winter 2024