Subquadratic 3SUM

3SUM is a simple puzzle. You have a list of $n$ whole numbers, some positive and some negative. The puzzle asks if three of them add up to exactly 0. In the list $-7,-3,2,5,8,11$, the answer is yes, because $-7+2+5=0$.

The plain method tries every group of three. With 1,000 numbers, that is about 166 million groups. A better method sorts the list first. Then, for each number, it looks for a matching pair by moving in from both ends of the list.

Here is that method for $-7$. We need two numbers from the rest of the list that add up to 7. Start with the two ends of the list. If the sum is too big, drop the largest number. If it is too small, drop the smallest number.

Each number takes one pass through the list, so the work is about $n\times n=n^2$ steps. With 1,000 numbers, that is about one million steps. For decades, the only improvements saved small factors, far less than any fixed power of $n$.

The 3SUM hypothesis says that $n^2$ is essentially the limit. It says that no method takes $n^{1.99}$ steps, or $n^{2-\epsilon }$ for any fixed small number $\epsilon$, the Greek letter epsilon. A power does not have to be a whole number, and $n^{1.99}$ is a little less than $n^2$. A similar hypothesis says the same about $n^3$ for all-pairs shortest paths, the problem of finding the cheapest route between every pair of towns.

Researchers used these hypotheses as working assumptions. They showed that if some other problem had a fast method, then 3SUM would have one too. Many problems in geometry were explained in this way, such as checking if three out of many points lie on one straight line.

Josh Alman and Virginia Vassilevska Williams report that both hypotheses are false. Their method takes about $n^{1.9992}$ steps, for whole numbers no larger than a fixed power of $n$. Claude discovered the method, and the authors then simplified and extended it.

The saving is very small. With a billion numbers, $n^{1.9992}$ is only about 1.6% less than $n^2$. A count like this also leaves out a fixed multiplier, and the authors say that this multiplier is enormous. So the method is potentially impractical. What changes is the theory: $n^2$ is not the limit for 3SUM.

The method uses matrices. A matrix is a table of numbers. An operation called the matrix product combines two matrices into a third. The new method computes selected entries of that third matrix faster than computing them one by one. Researchers had already built conversions from 3SUM to tasks of this kind, to show that those tasks are hard. The same conversions now run as a fast method for 3SUM.