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 Patrascu [STOC 2010], which was later improved by Kopelowitz, Pettie, and Porat [SODA 2016] with an O(log n) 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 log~(O(1)) U factor slowdown in the deterministic case.