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.

Feedback

Evaluation

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

• Homework:
  • Supplement to the lectures.
  • Posted weekly, but due 2~3 week later.
• Class project:
  • Short report summarizing your progress--or attempted progress--on novel research.
  • Permitted to combine with other research / course project.
• Wikipedia editing:
  • Create, make significantly edit, or translate a Wikipedia entry on any topic related to the course.
  • See instructor for suggested topics, advice, etc.

Tentative Schedule

Week 1: Query Complexity.

• Source: Symmetry and approximability of submodular maximization problems by Vondrak.
• Homework 1, due at the start of class on Monday, April 15.
• Scribe notes: Lecture 1 and Lecture 2.

Week 2: Communication Complexity.

• Source: Communication complexity of approximate Nash equilibria by Babichenko and Rubinstein.
• Homework 2, due at the start of class on Monday, April 22.
• Scribe notes: Lecture 3 and Lecture 4.

Week 3: PPAD and friends.

• Source: The Complexity of Computing a Nash Equilibrium by Daskalakas, Goldberg and Papadimitriou.
• Source: Settling the complexity of computing two-player Nash equilibria by Chen, Deng and Teng
• Source: PPP-Completeness with Connections to Cryptography by Sotiraki, Zampetakis and Zirdelis.
• Homework 3, due at the start of class on Monday, April 29.
• Scribe notes: Lecture 5 and Lecture 6.

Weeks 4-5: Unique Games Hardness.

• Source: Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? by Khot, Kindler, Mossel and O'Donnell.
• Source: Vertex cover might be hard to approximate to within 2 - eps by Khot and Regev
• Homework 4, will be done in class (Lecture 10) on Wednesday, May 1.
• Scribe notes: Lecture 7 and Lecture 8 and Lecture 9.

Week 6-7: Average case complexity.

• Source: Complexity Theoretic Lower Bounds for Sparse Principal Component Detection by Berthet and Rigollet.
• Source: Complexity Theoretic Limitations on Learning Halfspaces by Daniely.
• Source: Average-case Hardness lecture notes and survey by Regev.
• Homework 5 is due Monday, May 27.
• Scribe notes: Lecture 11 and Lecture 12 and Lecture 13 and Lecture 14.

Week 8: Exponential Time Hypothesis.

• Source: Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph by Manurangsi.
• Homework 6 is due Wednesday, June 5 (extended!).
• Scribe notes: Lecture 15 and Lecture 16.

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

• Source: On the Complexity of k-SAT by Impagliazzo and Paturi.
• Source: A new algorithm for optimal 2-constraint satisfaction and its implications by Williams.
• Source: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) by Backurs and Indyk.
• Source: Subcubic Equivalences Between Path, Matrix, and Triangle Problems by Williams and Williams.
• Scribe notes: Lecture 17 and Lecture 19. Lecture 18 was based on these lecture notes.