The Fine-Grained Complexity of CFL Reachability
summary
Classifies exact polynomial exponents for CFL reachability under standard fine-grained conjectures (BMM, k-Clique, APSP, 3SUM): shows Dyck-2 Ω(n^{2.5}) lower bound via a reduction that encodes edge integers as bracketed line‑graph gadgets across five vertex copies and relies on monochromatic‑triangle hardness, proves many CFLs either force matrix‑multiplication‑level cost or admit linear/quadratic algorithms (join‑inducing vs join‑free), gives a nonregular example solvable in n^{ω+3/2}, and proves Andersen’s pointer analysis m^3 lower bound for sparse graphs.
AI-written summary · about