Reducing 3SUM to Convolution-3SUM
Timothy M. Chan, Qizheng He · Society for Industrial and Applied Mathematics eBooks · 2019
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 log n)O(1) factor slowdown in the randomized case, and a logO(1) U factor slowdown in the deterministic case.