Threesomes, degenerates, and love triangles

The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial Opn2q-time algorithm is optimal and over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies Ωpn2q lower bounds on numerous problems in computational geometry and a variant of the conjecture implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. In this paper we refute the 3SUM conjecture. We prove that the decision tree complexity of 3SUM is Opn3{2?log nq and give two subquadratic 3SUM algorithms, a deterministic one run-ning in Opn2{plog n { log log nq2{3q time and a randomized one running in Opn2plog log nq2 { log nq time with high probability. Our results lead directly to improved bounds for k-variate lin-ear degeneracy testing for all odd k ě 3. The problem is to decide, given a linear function fpx1,..., xkq “ α0 `ř1ďiďk αixi and a set A Ă R, whether 0 P fpAkq. We show the decision tree complexity of this problem is Opnk{2?log nq. Finally, we give a subcubic algorithm for a generalization of the pmin,`q-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in weighted graphs. We give a depth-Opn5{2?log nq decision tree for this problem, as well as an algorithm running in time Opn3plog log nq2 { log nq.