3SUM, 3XOR, Triangles
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Shows a two-way quantitative reduction: if 3SUM runs in n^{1+ε} then triangle listing on m-edge graphs runs in about m^{4/3 - Θ(ε)}, and conversely Patrascu’s reduction gives the lower bound assuming 3SUM is quadratic. Key tools are deterministic reduction via combinatorial designs (constructing no-solution number sets in near-linear time) and a sparse-graph recursion with high-degree pruning that uses limited-dependence concentration to get the m^{4/3} bound; extension to 3XOR yields matching complexity in the extreme scenario.
AI-written summary · about