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.
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.
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
You may work in small groups (2~3 students) for all assignments (except scribing).
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.