EdusalsaDiscover Your Stanford

CS 354

Topics in Intractability: Unfulfilled Algorithmic Fantasies

  • Not Offered

3 units

Letter or Credit/No Credit

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.

Course Prequisites

Sign Up

To save CS 354 to your course bucketlist

Already Have An Account? Log In