Fine-Grained Complexity 3
summary
Shows simple reductions that turn OV/3OV/OMv assumptions into tight dynamic lower bounds: single-source reachability, SCC count and diameter each get nd = n^{1+o(1)} sparse-instance constructions with n stages and d = n^{o(1)} edge updates per stage so total work is n^{2+o(1)} unless update/query time is near linear. Gives concrete separations: undirected connectivity admits log n · (log log n)^2 updates while directed s,t reach still sits at ~n^{1.41} (matrix multiplication), and distinguishing diameter 3 vs 4 collapses to 3OV hardness.
AI-written summary · about