The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis
summary
Establishes an O(n^3) optimal algorithm for Andersen-style inclusion-based pointer analysis and a matching Ω(n^3) lower bound for even on-demand queries via a reduction from triangle detection, so cubic is unavoidable in general; shows that under witness bounds the problem drops to Õ(n^ω) time (ω < 2.373) using matrix-multiplication based transitive-closure and a new D1 reachability algorithm running in n^ω log^2 n via successive doubling and layering; proves P-completeness generally and NC parallelizability under polylog witness bounds.
AI-written summary · about