Improved exponents for 3SUM and APSP from triangles in sparse lopsided graphs
A sorry-free Lean 4 formalization of improved running-time exponents for 3SUM, Exact Triangle, the (min,+)-product and all-pairs shortest paths (APSP), on the word RAM of the published formalization (anthropics/formal-math, 3sum-apsp) of the paper of Alman and Vassilevska Williams, "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs" (arXiv:2610.06783). That paper gives deterministic algorithms for 3SUM in time O(n^1.9992) and for the (min,+)-product and APSP in time O(n^2.99942), through Exact Triangle in time O(n^(3 - 0.0017)). The project analyzes the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-10-08-000003
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-08-000003/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-08-000003/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'