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