Subcubic Certificates for CFL Reachability
summary
Claims existence of O(n^2) certificates for both yes and no instances of Dyck-2/CFL reachability, where positive certificates use grammar-based compression of paths and negative certificates are matrix inequalities over the boolean semiring. Certificates are verified in matrix-multiplication time (with randomized checks that can be near-quadratic in practice). The work builds explicit matrix-based invariants, proves soundness and completeness, and shows this rules out fine-grained reductions from SAT that would beat the cubic barrier unless NSETH fails.
AI-written summary · about