Fine-Grained Complexity 2

on YouTube ↗01h 03m

" summary

Shows a concrete reduction from orthogonal vectors to diameter that makes a 3/2‑approximation barrier precise: build vertices for sets and universe elements, connect set vertices to their elements and add a clique so instances with no disjoint pair have diameter 2 and those with a disjoint pair have diameter ≥3, so any subquadratic algorithm with factor <3/2 solves OV. Also traces dense‑graph equivalences via tropical (min+ ) matrix product to negative triangle and the APSP↔radius/median subcubic web, leaving diameter hardness as an open case.

AI-written summary · about

" chapters (12)

1. 0:00Fine-grained complexity intro
2. 1:29Takeaways from fine-grained complexity
3. 5:08Graph eccentricity definitions
4. 8:18Sparse graphs hardness
5. 12:20OV to diameter reduction
6. 22:08Diameter approximation updates
7. 26:07Dense graphs hardness
8. 30:04APSP to negative triangle
9. 43:15Negative triangle reductions
10. 55:46Open problems in radius/diameter
11. 59:16Directed vs undirected separations
12. 1:02:08Q&A