Preprocessed 3SUM for Unknown Universes with Subquadratic Space

In this paper we combine the techniques of two previously best known results in the field of preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ to achieve the first algorithm for preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ with unknown $C$ using subquadratic space.

First we consider the recent result of Kasliwal, Polak and Sharma [22], where in the case where $C$ is known at preprocessing, the authors obtain an algorithm with query time $\tilde{O}(n^{1.5})$ and $\tilde{O}(n^{1.5})$ space. This algorithm is achieved by sampling a random prime $p$ and computing the set of triples $a,b,c\in A\times B\times C$ that are not a $\mathrm{𝟥}𝖲𝖴𝖬$ solution, $a+b\ne c$, but mod p would look like one, i.e., $a+b{\equiv }_{p}c$. Such a triple is considered a false positive and the number of false positives is bounded by $O(\frac{n^3}{p})$.

Given the subsets $A^{\prime },B^{\prime },C^{\prime }$ at query time, the algorithm computes $A^{\prime }+B^{\prime }$ mod $p$ in $O(p\log p)$ time using the fast Fourier transform (FFT) - for every $c\in C$ it computes the number of pairs $(a,b)\in A^{\prime }\times B^{\prime }$ such that $a+b{\equiv }_{p}c$. It then goes over all stored false positives and for each false positive in $A^{\prime }\times B^{\prime }\times C^{\prime }$, subtracts one from the computed number of pairs in $A^{\prime }\times B^{\prime }$ that sum to the specified value of $c$ mod $p$. This leaves us with the number of pairs that truly sum up to $c$. The algorithm runs in time $\tilde{O}(p+\frac{n^3}{p})$, and so taking $p=O(n^{1.5})$ gives the desired query time and space.

In the case where $C$ is unknown at preprocessing, the authors use a similar approach of FFT and ruling out false positives. However, in this case, the algorithm stores a data structure that essentially saves the entire sumset $A+B$, which we will have to avoid in order to achieve subquadratic space.

The second result we consider is the concurrent works of Golovnev, Guo, Horel, Park and Vaikuntanathan [17] and Kopelowitz and Porat [23], where the authors construct an algorithm for the closely related problem of $\mathrm{𝟥}𝖲𝖴𝖬$-indexing. In this variant of the problem, we are given the sets $A$ and $B$ to preprocess, and at query time we receive a value $c$ and are asked if there exists a pair $a\in A,b\in B$ that sums to it. The question in this case regards the optimal tradeoff between query time and space. The key difference between $\mathrm{𝟥}𝖲𝖴𝖬$ indexing and preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ with unknown $C$ is that for the former, the query is about any pair of numbers in $A\times B$, whereas in the latter, the query asks to find a $\mathrm{𝟥}𝖲𝖴𝖬$ solution within a specific subset of $A$ and $B$. Thus, $\mathrm{𝟥}𝖲𝖴𝖬$-indexing cannot directly solve preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ with unknown $C$ and some additional tools are needed in order to apply $\mathrm{𝟥}𝖲𝖴𝖬$ indexing techniques to the problem of preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$.

To solve the $\mathrm{𝟥}𝖲𝖴𝖬$ indexing problem, Golovnev et al. [17] use a hashing argument combined with the cryptographic tool of Fiat-Naor function inversion [12]. This well known result gives a query-time/space tradeoff for the data structures problem of inverting a function, and has found recent algorithmic applications in areas including approximate nearest neighbor search [24], colinearity testing [1], and string indexing methods [5, 4]. Golovnev et al. consider the function $f:[|A|]\times [|B|]\to A+B$ defined by $f(i,j)=a_i+b_j(modp)$. Inverting this function is equivalent to finding a pair in $A\times B$ that sums to a given value (modulus $p$). However, Fiat-Naor function inversion on its own is insufficient for our problem, as it does not allow for restriction of the sources when multiple candidates exist, which we would need in the case when multiple pairs sum up to a given value but some of them are not in $A^{\prime }\times B^{\prime }$. Thus, this technique cannot be directly applied to the more general problem of preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$.

To combine these techniques, we treat the values in the set $A+B$ differently based on their multiplicity, i.e., the number of pairs in $A,B$ that sum to each value. We call a value $c$ a heavy hitter if it has multiplicity at least $n^{\delta }$ and denote by $\tilde{C}$ the set of all heavy hitters. Note that since every value in $\tilde{C}$ has more than $n^{\delta }$ different pairs that sum to it, we can bound the size of the set by $|\tilde{C}|=O(n^{2-\delta })$. To handle the heavy hitters, we apply the techniques of [22] and precompute the false positives mod $p$ in $A\times B\times \tilde{C}$. Using a standard argument we can show that the number of such false positives can be bounded by $O(\frac{n^{4-\delta }}{p})$.

Next, we handle the non-heavy hitters. We divide our input set $A$ into $\mathrm{\ell }=\tilde{O}(n^{\delta })$ parts $A_1,\mathrm{\dots },A_{\mathrm{\ell }}$. By doing this multiple times, we can guarantee that with high probability, for every value $c\in A+B$ with multiplicity , in at least one of the instances there are no two pairs $(a_1,b_1),(a_2,b_2)\in A\times B$ that sum to $c$ and fall into the same part in the partition, i.e., no $i$ satisfies $a_1,a_2\in A_i$. We now preprocess a Fiat-Naor inversion on each $A_i\times B$ independently, adjusting the function $f(a,b)=a+b$ slightly so that we can use a version of Fiat-Naor with a better time/space tradeoff than the general case used in [17].

Given the sets $A^{\prime },B^{\prime },C^{\prime }$ at query time, we compute $A^{\prime }+B^{\prime }$ mod $p$ using FFT. Now, for any heavy hitter $c\in C^{\prime }\cap \tilde{C}$, we rule out the false positives in $A^{\prime }\times B^{\prime }$ that sum to $c$ mod $p$ and are left with the number of pairs that sum to $c$ exactly. For every non-heavy hitter $c\in C^{\prime }\setminus \tilde{C}$, we query each Fiat-Naor instance to find a pair $(a,b)\in A_i\times B$ that sums to $c$ if such a pair exists. We then check if $(a,b)\in A^{\prime }\times B^{\prime }$ and if so return the triple $a,b,c$. Since each pair that sums to $c$ falls in a distinct Fiat-Naor instance, this process will scan all such pairs and find one in $A^{\prime }\times B^{\prime }$ if one exists.

The space requirements of our algorithm are dominated by the $\tilde{O}(n^{\delta })$ instances of Fiat-Naor function inversion data structures and the set of $O(\frac{n^{4-\delta }}{p})$ false positives for heavy hitters. By balancing the values of $\delta ,p$ we obtain a tradeoff between query time and space, achieving subquadratic space for any query time greater than $n^{1.5+\mathrm{\Omega }(1)}$.

We first recall the following inequalities.

We present two key tools used in preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ below as lemmas. Attributed to folklore, these lemmas were presented explicitly in [22].

We briefly note that computing the multiset of $A+B$ mod $p$ can be reduced to polynomial multiplication of two degree $p$ polynomials, which can be quickly computed via FFT (see [22] for a detailed proof). Given the ease of sumset computation for a small modulus, a natural obstacle that arises in preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ is the occurrence of false positives, i.e., triplets of the form $(a,b,c)\in A\times B\times C$ such that $a+b{\equiv }_{p}c$ but $a+b\ne c$. The following lemma bounds the number of such false positives.

The proof (see [22]) proceeds by a counting argument, with the key observation that only ${\log }_r(2U)$ of the primes in the range $[r,2r]$ can divide $|a+b-c|$. We observe by Markov’s inequality that at least $1/2$ of the primes in this range must have at most $O(|A||B||C|\log U/r)$ false positives.

We note that the set of false positives $F≔\{(a,b,c)\in A\times B\times C:a+b{\equiv }_{p}c\wedge a+b\ne c\}$ can be constructed in $O(|A||B|+|C|+r+|F|)$ time (see the preprocessing step under Theorem $3$ of [22]). This will be $O(n^2+|F|)$ time for the case that $|A||B|,|C|,r=O(n^2)$, as we have in Section 3. See [14, Lemma 3.2] for a deterministic variant of Lemma 6.

The main technique used for $\mathrm{𝟥}𝖲𝖴𝖬$ indexing has been function inversion. Function inversion is a widely studied data structures problem in cryptography [12, 18, 9, 19]. The goal is to give an optimal tradeoff curve between time $T$ and space $S$ for a data structure inverting a function $f:[N]\to [N]$ with pre-processing time $\tilde{O}(N)$. $T$ bounds the number of queries to $f$ as well as the online computation upon a query. Fiat and Naor [12] present a randomized data structure offering a general tradeoff curve of $T{S}^3=\tilde{O}(N^3)$, which was recently improved [18] to $T{S}^2\max (S,T)=\tilde{O}(N^3)$ (our algorithm, however, performs function inversion on the regime in which these two curves are equivalent). Below, we describe the more specific tradeoff provided by Fiat-Naor function inversion for functions with bounded in-degree.

We now prove the following corollary, which exactly describes the regime in which our algorithm performs function inversion. The proof utilizes a hashing argument of [17] as well as the more specific Fiat-Naor tradeoff for bounded in-degree functions.

Let $\delta >0,r>1$ be parameters to be set later. We begin by handling the values of $A+B$ with multiplicity greater than $n^{\delta }$. Define the set of heavy hitters as follows.

As every element in $\tilde{C}$ has $\ge n^{\delta }$ pairs in $A\times B$ that sum to it, we can bound the size of the set by $|\tilde{C}|\le n^{2-\delta }$. We repeat the following algorithm in parallel $\log n$ times in both the preprocessing and query phases.

We can construct $F$ in time $\tilde{O}(n^2+|F|)$ and using Lemma 6 with $R=n^r$, bound the size of $F$ by $\tilde{O}(\frac{n^2\cdot |\tilde{C}|}{p})\le \tilde{O}(n^{4-\delta -r})$. In total, this preprocessing step stores the sets $\tilde{C}$ and $F$, using space $\tilde{O}(n^{2-\delta }+n^{4-\delta -r})$.

We note that at query time, our algorithm does not read the entire set $F$, but only the false positives $F^{\prime }\subseteq F$ such that their $c$ value is in $C^{\prime }$,

For any $c\in \tilde{C}\cap C^{\prime }$, if there exists a pair $(a,b)\in A^{\prime }\times B^{\prime }$ that sums to $c$, then $H[c]$ will be greater than the number of triples $(a,b,c)$ in $F$ that have $c$ as their third coordinate with $(a,b)\in A^{\prime }\times B^{\prime }$. This is because $H[c]$ counts all triples $(a,b,c)$ with $(a,b)\in A^{\prime }\times B^{\prime }$ where $a+b{\equiv }_{p}c$, which includes any triples in $F$ with first two coordinates from $A^{\prime }\times B^{\prime }$ and third coordinate $c$ as well as at least one true (non-false-positive) sum $(a,b,c)$. Hence, the algorithm will output “yes” on any such value $c\in \tilde{C}\cap C^{\prime }$.

By Lemma 6, we can bound the size of $F^{\prime }$ by $\tilde{O}(\frac{n^2\cdot |\tilde{C}\cap C^{\prime }|}{p})\le \tilde{O}(n^{3-r})$. By Markov’s inequality, our algorithm can run in $\tilde{O}(n^{3-r})$ time and scan all of $F^{\prime }$ with constant probability and so repeating this $\log n$ times will guarantee success with high probability. Thus, the total runtime of this query algorithm is $\tilde{O}(n^r+n^{3-r})$.

Next we handle the non-heavy hitters. Let $\eta >0$ be a parameter to be set later. Define $\mathrm{\ell }=\lceil n^{\delta }\log n\rceil$. We repeat the following algorithm in parallel $4\log n$ times in both the preprocessing and query phases.

Note that since all values of $A,B$ are positive, $f$ is an injective function on pairs $(a,b)$ such that $a+b\in \tilde{C}$. In total, we store $\tilde{O}(n^{\delta })$ instances of a Fiat-Naor data structure, as well as $|\tilde{C}|$ values of the universe $[2U]$. Thus, this preprocessing step uses expected $\tilde{O}(n^{2-\delta }+n^{2-\eta +\delta })$ space.

In total, for every $c\in C^{\prime }\setminus \tilde{C}$ we perform $\tilde{O}(n^{\delta })$ calls to query a Fiat-Naor function inversion data structure for a total query time of $\tilde{O}(n\cdot n^{\delta }\cdot n^{2\eta -2\delta })=\tilde{O}(n^{1+2\eta -\delta })$.

The following two claims show the correctness of this stage of the algorithm. First we show that the functions $f_i$ do in fact have low in-degree, justifying our use of Corollary 8.

Combining the two algorithms above, given two sets $A,B$ we preprocess them to obtain the data structure for the heavy hitters and non-heavy hitters cases. This uses a total space of $\tilde{O}(n^{2-\delta }+n^{4-\delta -r}+n^{2-\eta +\delta })$.

Upon query, given $A^{\prime },B^{\prime },C$, we perform the two query algorithms described above to handle $C^{\prime }\cap \tilde{C}$ and $C^{\prime }\setminus \tilde{C}$ separately, for a total query time of $\tilde{O}(n^r+n^{3-r}+n^{1+2\eta -\delta })$.

Setting $\eta =\frac{1}{2}+\frac{\epsilon }{3},r=\frac{3}{2}+\epsilon ,\delta =\frac{1}{2}-\frac{\epsilon }{3}$ we get a query time of $\tilde{O}(n^{1.5+\epsilon })$ using space $\tilde{O}(n^{2-2\epsilon /3})$.

The preprocessing time is dominated by constructing $\tilde{C}$, in $\tilde{O}(n^2)$ time, constructing $F$ in $\tilde{O}(n^2+|F|)=\tilde{O}(n^2)$ time, and constructing $\tilde{O}(n^{\delta })$ instances of a Fiat-Naor function inversion data structure each in time $\tilde{O}(n^{2-\delta })$. Thus, in total, our algorithm takes $\tilde{O}(n^2)$ preprocessing time.

The only known lower bounds for function inversion [25, 10, 15] give that the space $S$ and query time $T$ must satisfy

While a matching upper bound is only known for random permutations [19], it is conceivable that a construction achieving this bound might be possible for arbitrary functions as no higher lower bounds are known.

Using a hypothetical optimal function inversion data structure achieving $ST=N$, just by plugging into our construction, we would obtain for every $\epsilon \in [0,1/2]$, a data structure for preprocessed $\mathrm{𝟥}𝖲𝖴𝖬$ with unknown $C$ with

space $n^{2-\epsilon }$ and query time $n^{1.5+\epsilon }$.

A brute-force query algorithm would solve $\mathrm{𝟥}𝖲𝖴𝖬$ on each query without the need for preprocessing. This would achieve space $O(n)$ (just store $A$ and $B$) and query time $O(n^2)$³³3One can also shave off polylog factors as in [3].. Interpolating between this and the space-$n^2$ and query-$n^{1.5}$ trade-off of [22], one might hope to be able to achieve for every $\epsilon \in [0,1/2]$,

space $n^{2-2\epsilon }$ and query time $n^{1.5+\epsilon }$.

Unfortunately, even with optimal function inversion, our construction doesn’t achieve such a result. Either new ideas are needed, or perhaps there is some limitation to achieving such a tradeoff.

Our approach can be useful for other potential problems with preprocessing, beyond $\mathrm{𝟥}𝖲𝖴𝖬$. We give $\mathrm{𝟥}𝖷𝖮𝖱$ as an example.

In the $\mathrm{𝟥}𝖷𝖮𝖱$ problem, one is given three $n$-sized sets of binary strings $A,B,C\subseteq {\{0,1\}}^d$. We want to know whether there exist $a\in A,b\in B,c\in C$ such that $a\oplus b\oplus c=0$. $\mathrm{𝟥}𝖷𝖮𝖱$ can be solved in $O(n^2)$ time deterministically and, with randomness, in expected time $O(n^2{(\log \log n)}^2/{\log }^{2}n)$ [11]. It is conjectured (e.g., [20]) that $n^{2-o(1)}$ time is necessary.

Analogous to $\mathrm{𝟥}𝖲𝖴𝖬$, we can define the preprocessed $\mathrm{𝟥}𝖷𝖮𝖱$ with unknown $C$ problem as: Given $A,B\subseteq {\{0,1\}}^d$, preprocess them so that the following query can be supported efficiently: given $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ and $C\subseteq {\{0,1\}}^d$, decide if there exist $a\in A^{\prime },b\in B^{\prime },c\in C$ such that $a\oplus b\oplus c=0$.

We can obtain essentially the same trade-off for $\mathrm{𝟥}𝖷𝖮𝖱$ as for $\mathrm{𝟥}𝖲𝖴𝖬$ for this preprocessed version, just by simulating some key steps of the $\mathrm{𝟥}𝖲𝖴𝖬$ algorithm with $\mathrm{𝟥}𝖷𝖮𝖱$ primitives.

The first primitive we need to simulate is instance reduction with a small number of false positives. For $\mathrm{𝟥}𝖲𝖴𝖬$ this was, given some $p$, to efficiently compute $A+Bmodp$ (with multiplicities) and also to pick $p$ so that the number of false positives is small.

While XORing vectors mod a prime is not defined, Jafargholi and Viola [20] provided an analogous tool for $\mathrm{𝟥}𝖷𝖮𝖱$. They defined linear hash functions that take a vector $a\in {\{0,1\}}^d$ to a vector $h(a)\in {\{0,1\}}^{\mathrm{\ell }}$ for some choice . This is essentially achieved by random linear combinations of the vector components. Because of linearity, if $a\oplus b\oplus c=0$, we also have $h(a)\oplus h(b)\oplus h(c)=0$. Jafargholi and Viola [20] showed that the expected number of false positives is $O(n^3/2^{\mathrm{\ell }})$. Thus, effectively, we can think of $p:=2^{\mathrm{\ell }}$.

For $\mathrm{𝟥}𝖲𝖴𝖬$ we use the FFT to compute $A+Bmodp$ (with multiplicities) in $\tilde{O}(p)$ time. For $\mathrm{𝟥}𝖷𝖮𝖱$ one can use the Walsh-Hadamard transform to compute for all $c\in {\{0,1\}}^{\log p}$ the number of pairs $(a,b)\in A\times B$ such that $c=a\oplus b$, i.e., the number of $\mathrm{𝟥}𝖷𝖮𝖱$ solutions that $c$ is part of. The running time is $O(p\log p)$ using the fast folklore recursive algorithm to compute the transform on vectors of length $\log p$.

The rest of our algorithm (Fiat-Naor and Walsh-Hadamard instead of FFT) can be simulated for $\mathrm{𝟥}𝖷𝖮𝖱$ exactly as for $\mathrm{𝟥}𝖲𝖴𝖬$, and hence we obtain a trade-off of space usage $\tilde{O}(n^{2-2\epsilon /3})$ and query time $\tilde{O}(n^{1.5+\epsilon })$ after quadratic time preprocessing, for preprocessed $\mathrm{𝟥}𝖷𝖮𝖱$ with unknown $C$.

The approach can be used for other problems, provided the problems admit analogues of instance size reduction (like mod $p$) with bounded false positives and of the FFT for computing for every $c$ in the range, the number of solutions in the reduced instance that use $c$.