Improved Time-Space Tradeoffs for 3SUM-Indexing

In this paper, we analyze a preprocessing variant of 3SUM, known as 3SUM-Indexing. This variant was first defined by Demaine and Vadhan [11] in an unpublished note, and then reconsidered by Goldstein, Kopelowitz, Lewenstein and Porat [16].

In the 3SUM-Indexing problem, the input is an array of positive integers $A=\{a_0,\mathrm{\dots },a_{n-1}\}$. An algorithm $𝒜$ for the problem is a pair $𝒜=({𝒜}_0,{𝒜}_1)$, where ${𝒜}_0$ is the preprocessing algorithm and ${𝒜}_1$ is the online algorithm. The preprocessing algorithm ${𝒜}_0$ receives $A$ as input and outputs a data structure of length $S$ bits.¹¹1One can also define the problem by allowing ${𝒜}_0$ to output $S$ words of size poly-logarithmic in $n$. Since we ignore such poly-logarithmic factors in this paper, we consider these definitions equivalent. The online algorithm ${𝒜}_1$ receives as input an integer challenge $y$ and has access to the bits of the data structure output by ${𝒜}_0$. Its goal is to output a pair $(i,j)\in {[n]}^2$ such that $a_i+a_j=y$, if such a pair exists, and $\perp$ otherwise. In the cell-probe model, the time complexity of ${𝒜}_1$ (denoted by $T$) is only measured by the number of data structure bits that it queries. One can also consider other computational models which account for the actual runtime of ${𝒜}_1$ (e.g., in the RAM model) or the preprocessing time.

There are two trivial algorithms for 3SUM-Indexing: the first one stores $A$ sorted, while on input $y$, ${𝒜}_1$ searches this array for $y-a_i$ for each $i\in [n]$. This algorithm has $S=\tilde{O}(n)$ and $T=\tilde{O}(n)$ (where the $\tilde{O}$ notation suppresses factors poly-logarithmic in the input length). The second algorithm stores the sorted sumset $A+A=\{a_i+a_j\mid (i,j)\in {[n]}^2\}$, while on input $y$, ${𝒜}_1$ searches this sumset. The second algorithm has $S=\tilde{O}(n^2)$ and $T=\tilde{O}(1)$.

Consequently, [11, 16] formulated three conjectures:

These conjectures are in ascending order of strength:

In terms of lower bounds, Demaine and Vadhan proved that any 1-probe data structure for 3SUM-Indexing requires space $\tilde{\mathrm{\Omega }}(n^2)$, and left the case of $T>1$ open. Then [17] proved that for every non-adaptive algorithm that uses space $S$ and query time $T$ and solves 3SUM-Indexing, it holds that $S=\tilde{\mathrm{\Omega }}(n^{1+1/T})$. More recently, Chung and Larsen [8] proved similar bounds for adaptive algorithms. All these lower bounds assume the data structure consists of $S$ words of size $\tilde{O}(1)$. Since proving super-logarithmic query-time bounds for static data structures even with space $S=O(n)$ is a major open problem, the lower bounds of [8] are essentially the best possible (barring a significant breakthrough).

From the algorithmic side, Conjecture 3 was refuted by Kopelowitz and Porat [22] and by [17] using the same techniques. Specifically, [22, 17] describe an algorithm for 3SUM-Indexing with $T=\tilde{O}(n^{\delta })$ and $S=\tilde{\mathrm{\Omega }}(n^{2-\delta /3})$. The algorithm is based on the classical Fiat-Naor algorithm [14] for the Function Inversion problem, where the goal is to invert an efficiently computable function $f:[N]\to [N]$ by a two-phase algorithm: a preprocessing algorithm for $f$ that outputs an advice string of length $S$ bits, and an online algorithm that receives a challenge $y\in [N]$ and finds $x\in [N]$ such that $f(x)=y$ after making $T=\tilde{O}(N^3/S^3)$ queries to $f$. In the case of 3SUM-Indexing, by hashing, we may essentially assume that the input $a_0,\mathrm{\dots },a_{n-1}$ satisfies $a_i\in [n^2]$ for every $i\in [n]$. We then define the function $f:[n^2]\to [n^2]$ by $f(i,j)=a_i+a_j$ and apply the Fiat-Naor algorithm to $f$.

The Fiat-Naor based algorithm of [22, 17] is currently the best known algorithm for 3SUM-Indexing. Recently, Bille et al. [4] proved that well-studied problems in data structures (specifically, Gapped String Indexing and Jumbled Indexing) reduce to 3SUM-Indexing. Thus, the algorithm of [22, 17] is used to obtain the best known algorithms for these problems. The 3SUM-Indexing problem has also inspired more applications of the Fiat-Naor algorithm to related data structure problems [3, 1]. Given the extensive research involving 3SUM-Indexing and its variants, it is natural to ask whether it is possible to exploit the structure of the problem to improve the Fiat-Naor based algorithm of [22, 17]. This question was posed explicitly in [17, Open Question 2] and [28, Lecture 14].

We also mention the recent improvement of the Fiat-Naor algorithm for Function Inversion by [18]. Unfortunately, this improvement is in a restricted parameter range, and when applied to 3SUM-Indexing, the algorithm of [18] is outperformed by the trivial algorithm with $S=\tilde{O}(n),T=\tilde{O}(n)$.

Looking at the open question of [17] from a broader perspective, we recall that the Fiat-Naor algorithm was originally designed to invert “unstructured” cryptographic one-way functions. The fact that it gives the best known time-space tradeoff for a broad spectrum of structured problems [10, 22, 17, 3, 4, 2, 24] is surprising. Quoting [2]:

It is a striking fact that, for each of these problems (3SUM-Indexing, Collinearity Indexing, Gapped String Indexing), the best known space-time trade-offs are achieved using such a general tool as the Fiat-Naor inversion scheme.

More generally, the Function Inversion problem has found major applications across multiple areas such as cryptanalysis [19, 5, 6, 26, 25], circuit and data structure lower bounds [29, 10, 12], algorithms [22, 17, 3, 4, 2, 24], information theory [12], and most recently even meta-complexity [23, 20]. On the other hand, we are not aware of any previous application-dependent improvement of the Fiat-Naor scheme. Thus, finding such improvements is an interesting research topic. Informally, the challenge is due to the unique data structure used by the Fiat-Naor algorithm, which is built by iterating the function we wish to invert. Such iterations seem to destroy most properties that can be exploited to optimize the algorithm (e.g., iterating a function represented by a low-degree polynomial quickly increases its degree).

In this paper, we improve the best known time-space tradeoff for 3SUM-Indexing [22, 17] for the parameter range $n^{3/2}\ll S\ll n^{7/4}$. In particular, we obtain the first application-dependent improvement of the Fiat-Naor scheme.

Specifically, we prove the following theorem.

Our time-space tradeoff is compared to the previously best known one in Figure 1. In particular, for $S=n^{5/3}$, we obtain $T=\tilde{O}(n^{5/6})$, while the previous best algorithm was the trivial one, which obtains $T=\tilde{O}(n)$.

We remark that the runtime of the online algorithm ${𝒜}_1$ in our algorithm in the standard RAM model is linear in its number of queries to the data structure, up to poly-logarithmic factors. Moreover, the runtime of the preprocessing algorithm ${𝒜}_0$ is $\tilde{O}(n^2)$. (An algorithm with truly subquadratic preprocessing time $\tilde{O}(n^{2-\epsilon })$ would refute the 3SUM conjecture.)

We further apply a variant of our algorithm to the kSUM-Indexing problem, introduced in [17]. In this problem, the input of the preprocessing algorithm is an array of positive integers $A=\{a_0,\mathrm{\dots },a_{n-1}\}$, and the online algorithm for an integer challenge $y$ finds $(i_1,\mathrm{\dots },i_{k-1})\in {[n]}^{k-1}$ such that $a_{i_1}+\mathrm{\dots }+a_{i_{k-1}}=y$. kSUM-Indexing is a preprocessing version of kSUM and a natural generalization of 3SUM-Indexing.

Once again, we focus on the parameter regime with sub-linear time.

We remark that there is a trivial algorithm for kSUM-Indexing with $S=\tilde{O}(n^{k-2})$ and $T=\tilde{O}(n)$, while an application of the Fiat-Naor algorithm [17] gives $S=\tilde{O}(n^{k-1-\delta /3})$ and $T=\tilde{O}(n^{\delta })$. Our algorithm is better than the previous algorithms in the range $n^{k-1.5}\ll S\ll n^{k-1.25}$. We further note that there are other trivial algorithms for kSUM-Indexing in the regime of super-linear $T$, and that our algorithm can be easily extended to this regime too (as done in [17] by taking larger values of $\delta$).

Next, we adapt our algorithm to the kXOR-Indexing problem. In kXOR-Indexing, the input to be preprocessed is an array of $n$ vectors in ${\{0,1\}}^{\mathrm{\ell }}$. Then, given a query vector $y\in {\{0,1\}}^{\mathrm{\ell }}$, the goal is to check if there are $(k-1)$ input vectors whose XOR is $y$.

As an additional application, we use the reduction of Bille et al. [4] from the Jumbled Indexing problem to 3SUM-Indexing, and conclude an immediate improvement for it as well.

In the Jumbled Indexing problem (also known as Histogram Indexing), the input to be preprocessed is a string $S$ of length $n$ over an alphabet $\mathrm{\Sigma }$. Given a query histogram $h\in {\mathbb{Z}}_{\ge 0}^{|\mathrm{\Sigma }|}$ (i.e., the number of occurrences of each letter from $\mathrm{\Sigma }$), the task is to check if $S$ contains a substring whose histogram matches $h$.

In the case of the binary alphabet $|\mathrm{\Sigma }|=2$, Cicalese et al. [9] gave an efficient algorithm with $S=O(N)$ and $T=O(1)$ solving Jumbled Indexing. For larger alphabets, Kociumaka, Radoszewski, and Rytter [21] designed an algorithm that solves Jumbled Indexing in space $S=\tilde{O}(n^{2-{\delta }^{\prime }})$ and time $T=\tilde{O}(n^{(2|\mathrm{\Sigma }|-1){\delta }^{\prime }})$. Then, Chan and Lewenstein [7] improved the bound to $S=\tilde{O}(n^{2-{\delta }^{\prime }})$ and $T=\tilde{O}(n^{(|\mathrm{\Sigma }|+1){\delta }^{\prime }/2})$ by utilizing algorithms for a variant of 3SUM. Finally, [4] used a reduction from Jumbled Indexing to 3SUM-Indexing, together with the 3SUM-Indexing algorithm of [22, 17], resulting in an upper bound of $S=\tilde{O}(n^{2-{\delta }^{\prime }/3})$ and $T=\tilde{O}(n^{{\delta }^{\prime }})$. This bound improves on the previous bounds for all alphabets of size $|\mathrm{\Sigma }|>5$. We further improve algorithms for Jumbled Indexing, achieving $S=\tilde{O}(n^{2.5-\delta })$ and $T=\tilde{O}(n^{\delta })$. This algorithm outperforms [4] for all $n^{3/2}\ll S\ll n^{7/4}$, and it improves on [7] for all $|\mathrm{\Sigma }|>1+1/{\delta }^{\prime }$.

Recall that the best known worst-case time-space tradeoff for 3SUM-Indexing is $T{S}^3=\tilde{O}(n^6)$. It was derived in [22, 17] by applying the Fiat-Naor tradeoff to the function $f(i,j)=a_i+a_j$ (one may assume that $f:[n^2]\to [n^2]$ by standard hashing techniques). Moreover, there is a trivial time-space tradeoff of $T=S=\tilde{O}(n)$, while clearly $S=\tilde{\mathrm{\Omega }}(n)$ must hold for any algorithm that succeeds answering all the queries. Thus, the only relevant parameter range is $T\ll n$ (and $S=\tilde{\mathrm{\Omega }}(n)$). Consequently, the improvement of [18] to the Fiat-Naor tradeoff (effective only when $S\ll T$) is not directly applicable to 3SUM-Indexing.

The classical rigorous algorithm for the Function Inversion problem due to Fiat and Naor [14] solves the problem in space $S$ and time $T$ as long as $S^{3}T=\tilde{\mathrm{\Omega }}(N^3)$.

We will also use another version of this algorithm for Function Inversion that performs better for $T\gg S$.

We stress that the online algorithms of Theorems 10 and 11 run in time $T$ in the RAM model, but the algorithm of Theorem 11 assumes shared randomness. [18, Section 6] proves that Theorem 11 can be implemented without shared randomness at the expense of having computationally unbounded preprocessing and a non-uniform online algorithm (as opposed to a RAM online algorithm). In Theorem 16, we show that in our application, the need for shared randomness can be completely eliminated with no impact on the parameters or the running time of the preprocessing and online algorithms by simply including the shared random string as part of the preprocessed advice.

We will use the following lemma, which applies standard techniques to amplify the success probability of a weak function inversion algorithm.

A few remarks about the definition of kSUM-Indexing are in order.

Next, we define other data structure problems we are considering in this paper. In order to define the Jumbled Indexing problem, we first need to define the histogram of a string $S\in {\mathrm{\Sigma }}^n$ over an alphabet $\mathrm{\Sigma }$. The histogram of $S$ is a vector $h\in {\mathbb{Z}}_{\ge 0}^{|\mathrm{\Sigma }|}$, where the $i$th coordinate of $h$ is the number of occurrences of the $i$th character of the alphabet $\mathrm{\Sigma }$ in the string $S$.

• $\mathrm{■}$

  For $k\ge 3$, the kXOR-Indexing problem is a variant of kSUM-Indexing where the addition is replaced by XOR. The kXOR-Indexing problem takes as input a list of $n$ vectors $A=(a_0,\mathrm{\dots },a_{n-1})\in {({\{0,1\}}^{\mathrm{\ell }})}^n$. For a query $b\in {\{0,1\}}^{\mathrm{\ell }}$, the task is to output a tuple $(i_1,\mathrm{\dots },i_{k-1})\in {[n]}^{k-1}$ such that $a_{i_1}\oplus \mathrm{\dots }\oplus a_{i_{k-1}}=b$ if such a tuple exists, and to output $\perp$ otherwise.

• $\mathrm{■}$

  For $n\le m$, the $\text{3SUM-Indexing}(n,m)$ problem is a variant of 3SUM-Indexing where the two input lists may have different lengths. The $\text{3SUM-Indexing}(n,m)$ problem takes as input a list of $n$ non-negative integers $A=(a_0,\mathrm{\dots },a_{n-1})\in {\mathbb{Z}}_{\ge 0}^n$ and a list of $m$ non-negative integers $B=(b_0,\mathrm{\dots },b_{m-1})\in {\mathbb{Z}}_{\ge 0}^m$. For a query $b\in {\mathbb{Z}}_{\ge 0}$, the task is to output a pair $(i,j)\in [n]\times [m]$ such that $a_i+b_j=b$ if such a pair exists, and to output $\perp$ otherwise. For $n=m$, $\text{3SUM-Indexing}(n,m)$ is simply the 3SUM-Indexing problem.

• $\mathrm{■}$

  The Jumbled Indexing problem takes as input a string $S$ of length $n$ over an alphabet $\mathrm{\Sigma }$. For a query histogram $h\in {\mathbb{Z}}_{\ge 0}^{|\mathrm{\Sigma }|}$, the task is to output 1 if there exists a substring of $S$ with histogram $h$, and to output 0 otherwise.

We will use the following efficient reduction from Jumbled Indexing to 3SUM-Indexing shown by [4] (the reduction was also implicitly used in [7]).