Fine Grained Complexity
summary
Motivation and concrete claims: 3SUM conjecture states 3SUM requires n^2−o(1) on n integers, orthogonal vectors resists n2−o(1) algorithms for d≈log^2 n, and all-pairs shortest paths requires n^3−o(1) for polyweight graphs. Dynamic problems use OMv/OuMv (the OMv conjecture: n^3−o(1)) to show triangle-counting lower bounds: n updates each causing O(n) edge changes gives an n^3 barrier, parity and average-case (Erdos–Rényi) counting reductions extend hardness, and zero-triangle ties to APSP and 3SUM.
AI-written summary · about