Fast Combinatorial 3SUM breaks BMM
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Claim: a combinatorial 3SUM algorithm running in N^{3/2 - ε} would yield a subcubic combinatorial Boolean matrix multiplication algorithm, so under the conjecture that combinatorial BMM needs n^{3 - o(1)} time there is no combinatorial 3SUM in n^{3/2 - ε}. The reduction packs n×n matrix edges into three sets via hash-to-sum encoding, runs 3SUM on inputs of size N = n^2, and recovers witnesses using a K-by-K grid batching (choose K ≈ n^{1/3}) plus recursive witness search. The construction succeeds with high probability.
AI-written summary · about