CS 354: Topics in Intractability: Unfulfilled Algorithmic Fantasies (Spring 2019)

Instructor: Aviad Rubinstein (aviad at cs)

Location and Time: Monday and Wednesday 3:00 PM - 4:20 PM at STLC 115

Course Assistant: Josh Brakensiek (jbrakens at cs)

Office Hours: Wednesday 1:45-2:45, Gates 464.

Piazza: Sign up here.

Gradescope: Access code 9ZYD22.

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 other 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.


Use this link to submit feedback anytime to the instructor. This is independent of Stanford's official course evaluations.


Students taking the course for CR are required to scribe one lecture. Please use this template.

Students taking the course for a letter grade are required to scribe one lecture + a convex combination of the following.

You may work in small groups (2~3 students) for all assignments (except scribing).

Please contact Aviad ASAP when you have a sense of which of those you plan to do.

Tentative Schedule

Week 1: Query Complexity.

Week 2: Communication Complexity.

Week 3: PPAD and friends.

Weeks 4-5: Unique Games Hardness.

Week 6-7: Average case complexity.

Week 8: Exponential Time Hypothesis.

Week 9-10: Strong Exponential Time Hypothesis and fine-grained complexity.