Event: 3SUM is Subquadratic

The 3SUM problem is to decide, given a set of N real numbers, whether any three of them sum to zero. A simple algorithm solves 3SUM in O(N^2) time and it has long been conjectured that this is the best possible.

The significance of the 3SUM problem does not lie with its practical applications (roughly zero) but with the long list of problems in computational geometry that are reducible from 3SUM. Some examples include deciding whether a point set contains 3 colinear points, calculating the area of the union of a set of triangles, and determining whether one convex polygon can be placed within another
convex polygon. If 3SUM requires N^2 time then all 3SUM-hard problems require N^2 time. More recently Patrascu gave many conditional lower bounds on triangle enumeration and dynamic data structures that rely on the hardness of 3SUM over the integers.

In this talk I'll present a non-uniform (decision-tree) algorithm for 3SUM that performs only N^{3/2} comparisons and a uniform 3SUM algorithm running in O(N^2/polylog(N)) time. This result refutes the 3SUM conjecture and casts serious doubts on the optimality of many O(N^2) geometric algorithms.

Joint work with Allan Gronlund. To appear in FOCS 2014. A full manuscript is available at arXiv:1404.0799.