Topics in Intractability: Unfulfilled Algorithmic Fantasies
Download as PDF
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.
Grading Basis
ROP - Letter or Credit/No Credit
Min
3
Max
3
Course Repeatable for Degree Credit?
No
Course Component
Lecture
Enrollment Optional?
No
Does this course satisfy the University Language Requirement?
No
Programs
CS354
is a
completion requirement
for:
- (from the following course set: )
- (from the following course set: )
- (from the following course set: )