Preprocessed 3SUM for Unknown Universes with Subquadratic Space

Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan +1

We consider the classic 3SUM problem: given sets of integers $A,B,C$, determine whether there is a tuple $(a,b,c)\in A\times B\times C$ satisfying $a+b+c=0$. The 3SUM…