Recovery Beats Storage: Improved Space for Preprocessed 3SUM

Amir Carmel, Yakov Kosoburd, Robert Krauthgamer

The 3SUM problem asks, given sets $A,B,C$ of integers, whether there exist $a\in A$ and $b\in B$ whose sum belongs to $C$. In the preprocessed variant with unknown $C$, one preproc…