Fine-Grained Complexity 4
summary
Covers fine grained hardness for k‑clique detection and listing, gives the fastest known upper bounds using fast matrix multiplication (assume ω = 2 so k‑clique detection via reductions to triangles runs in n^{2k/3} time and triangles in n^{ω}), shows triangle listing algorithms with runtime m^{4/3} and m·T^{1/3} when listing T triangles, and gives a randomized reduction from Exact‑Triangle (weights shifted by x and y_u) that produces O(n) triangle‑listing instances with degree ≈√n to prove an m^{4/3} bound under the exact‑triangle hypothesis.
AI-written summary · about