Tutorial on Fine-grained Complexity

Course materials

Return to the Tutorial's webpage>>


Full video playlist
Lecture slides & videos
  • Introduction to Fine-Grained Complexity (Amir Abboud)  [slides]  [video]
  • Day 1 - Lecture 2: 3SUM Hypothesis and Equivalent Formulations (Amir Abboud)  [slides]  [video]
  • Day 1 - Lecture 3: 3SUM: Hardness of Convolution 3SUM and Triangle Listing (Nick Fischer) [slides]  [video]
  • Day 1 - Bird's View Lecture 1: 3SUM-Hardness of Geometric Problems (Nick Fischer)  [slides]  [video]
  • Day 2 - Lecture 4: APSP Hypothesis (Nick Fischer): [slides]  [video]
  • Day 2 - Lecture 5: APSP-Hardness of Negative Triangle Detection (Nick Fischer)  [slides]  [video]
  • Day 2 - Lecture 6: APSP-Hardness of Zero Triangle (Amir Abboud)  [slides]  [video]
  • Day 2 - Bird's View Lecture 2: APMF vs. APSP (Amir Abboud)  [slides]  [video]
  • Day 3 - Lecture 7: Algorithms for k-SAT (Nick Fischer) [slides]  [video]
  • Day 3 - Lecture 8: Lower Bounds under ETH and SETH (Amir Abboud)  [slides]  [video]
  • Day 3 - Lecture 9: Orthogonal Vectors Hypothesis (Amir Abboud) [slides]  [video]
  • Day 3 - Bird's View Lecture 3: Fine-Grained Lower Bounds for Dynamic Graph Problems (Amir Abboud) [slides]  [video]
  • Day 4 - Lecture 10: SETH-Hardness of LCS (Amir Abboud): [slides]  [video]
  • Day 4 - Lecture 11: Hardness of Approximation in P, Part 1 (Nick Fischer): [slides Parts 1 & 2]  [video]
  • Day 4 - Lecture 12: Hardness of Approximation in P, Part 2 (Nick Fischer): [slides Parts 1 & 2]  [video]
  • Day 4 - Bird's View Lecture 4: Barriers for Fine-Grained Reductions (Nick Fischer) [slides]  [video]
  • Day 5 - Lecture 13: Recent Developments in Fine-Grained Complexity  (Amir Abboud)  [slides]  [video]

Return to the Tutorial's webpage>>