Reproduce “Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Josh Alman, Virginia Vassilevska Williams
The authors introduce a deterministic algorithm that computes selected entries of a thin matrix product without computing the full product or each entry separately. It recursively multiplies rectangular matrices and prunes work for unrequested outputs. It gives 3SUM in O(n^1.9992) and directed APSP in O(n^2.9995) for polynomially bounded integers in the word-RAM model, asymptotic bounds rather than measured speedups.
Key insights
- The savings come from bounding the union of recursive multiplication terms needed across requested outputs, rather than calculating each output independently.
- A faster algorithm for a lopsided triangle problem can propagate through existing reductions to improve several problems traditionally used to establish conditional lower bounds.
- The improvements are restricted: they do not refute SETH, standard OMv, Orthogonal Vectors, or the stated k-SUM hypotheses for k ≥ 4, and do not cover balanced All-Edges Sparse Triangle.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.