3SUM is Subquadratic – University of Copenhagen

3SUM is Subquadratic

Talk by Seth Pettie, Associate Professor University of Michigan

Abstract

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.

This is joint work with Allan Gronlund. A manuscript is available at arXiv:1404.0799.

Seth Pettie is a professor of computer science at the University of Michigan, Ann Arbor.  He received his Ph.D. in 2003 from the University of Texas at Austin and was an Alexander von Humboldt postdoctoral fellow at the Max Planck Institute for Computer Science in Saarbruecken, Germany.