Reducing 3SUM to Convolution-3SUM

Given a set S of n numbers, the 3SUM problem asks to determine whether there exist three elements a, b, c ∈ S such that a + b + c = 0. The related Convolution-3SUM problem asks to determine whether there exist a pair of indices i, j such that A[i] + A[j] = A[i + j], where A is a given array of n numbers. When the numbers are integers, a randomized reduction from 3SUM to Convolution-3SUM was given in a seminal paper by Pǎtraşcu [STOC 2010], which was later improved by Kopelowitz, Pettie, and Porat [SODA 2016] with an O(logn) factor slowdown. In this paper, we present a simple deterministic reduction from 3SUM to Convolution-3SUM for integers bounded by U . We also describe additional ideas to obtaining further improved reductions, with only a (log logn) factor slowdown in the randomized case, and a log U factor slowdown in the deterministic case.