The Strong 3SUM-INDEXING Conjecture is False

Abstract

In the 3SUM-Indexing problem the goal is to preprocess two lists of elements from $U$, $A=(a_1,a_2,\dots ,a_n)$ and $B=(b_1,b_2,...,b_n)$, such that given an element $c\in U$ one can quickly determine whether there exists a pair $(a,b)\in A\times B$ where $a+b=c$. Goldstein et al.~[WADS'2017] conjectured that there is no algorithm for 3SUM-Indexing which uses $n^{2-\Omega (1)}$ space and $n^{1-\Omega (1)}$ query time. We show that the conjecture is false by reducing the 3SUM-Indexing problem to the problem of inverting functions, and then applying an algorithm of Fiat and Naor [SICOMP'1999] for inverting functions.

Cited by in corpus (2)

• Tight Quantum Time-Space Tradeoffs for Function Inversion
• Data Structures Meet Cryptography: 3SUM with Preprocessing