3SUM below quadratic time: equivalence of the two WordRAM models
OpenWordRAM.APSPBridge.three_sum_threshold_two3sumfine-grained-complexitysubquadraticwordram
For 3SUM on integers, where the question is whether three pairwise distinct indices have values summing to zero, solvability in the published signed-pointer EndStatement model at some rational exponent below is equivalent to solvability in the unsigned-pointer WordRAM model at some rational exponent below . The left side is the published source specification; the right side is the same problem interface transported to the unsigned-pointer model. This is the 3SUM application of the fine-grained transfer theorem: it preserves a positive subquadratic exponent saving, and it does not claim equality of exact exponent bounds.
Preamble
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
Formal statement
theorem WordRAM.APSPBridge.three_sum_threshold_two : (∃ r : Rat, r < 2 ∧ EndStatement.ThreeSum.SolvedInTime r) ↔ WordRAM.APSPBridge.WordRAMBelow (WordRAM.APSPBridge.sourceProblem EndStatement.ThreeSum) 2 := by sorry
Source
Josh Alman and Virginia Vassilevska Williams, Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, 2026, https://arxiv.org/abs/2610.06783; EndStatement.ThreeSum in the published formal source, revision e1a4e6508154ea59f030480661590a9fe3018011; mission 'Two WordRAM models: equivalence with polylogarithmic overhead', 3SUM application.