Topics in Intractability: Unfulfilled Algorithmic Fantasies
Lecture
Main Campus
Course Description
Over the past 45 years, understanding NP-hardness has been an amazingly useful tool for algorithm designers. This course will expose students to additional ways to reason about obstacles for designing efficient algorithms. Topics will include unconditional lower bounds (query- and communication-complexity), total problems, Unique Games, average-case complexity, and fine-grained complexity. Prerequisites: CS 161 or equivalent. CS 254 recommended but not required.
CS 354
Units: 3
See When It's Offered opens a new window opens in a new tab
Typically Offered
Not Available
Grading Basis
Letter or Credit/No Credit
Class Level
Graduate
Instructional Mode
In Person
Gen Ed Requirement(s)
None