The Strong 3SUM-INDEXING Conjecture is False
Tsvi Kopelowitz Ely Porat
cs.DS




 ]Tsvi Kopelowitz
 ]Ely Porat
[ ]Bar-Ilan University, Ramat Gan, Israel
[ ]





The Strong 3SUM-INDEXING Conjecture is False
    [
    
============================================

empty



In the  problem the goal is to preprocess two lists of elements from U,  A=(a_1,a_2,…,a_n) and B=(b_1,b_2,...,b_n), such that given an element c∈ U one can quickly determine whether there exists a pair (a,b)∈ A × B where a+b=c.
Goldstein et al. [WADS'2017] conjectured that there is no algorithm for  which uses n^2-Ω(1) space and n^1-Ω(1) query time. 

We show that the conjecture is false by reducing the  problem to the problem of inverting functions, and then applying an algorithm of Fiat and Naor [SICOMP'1999] for inverting functions.





§ INTRODUCTION

In the  problem the input is three sets A, B and C, each containing n elements from a universe U that is closed under addition, and the goal is to establish whether there exists a triplet (a,b,c)∈ A× B× C such that a+b=c.
The  conjecture, which states that there is no algorithm in the RAM model that solves  in n^2-Ω(1) time <cit.>, is one of the most popular conjectures used for proving conditional lower bounds on the time cost of various algorithmic problems <cit.>.


Together with Goldstein and Lewenstein in <cit.>, we considered an online variant of the  problem, which we called the
 problem.
In the  problem the goal is to preprocess two lists of elements from U,  A=(a_1,a_2,…,a_n) and B=(b_1,b_2,...,b_n), such that given an element c∈ U one can quickly determine whether there exists a pair (a,b)∈ A × B where a+b=c.
One straightforward algorithm for solving the  problem is to store the sums of all pairs of values in A × B. The space usage of this algorithm is O(n^2) and the query time is O(1) (using a hash table).
Another straightforward algorithm is to separately sort A and B, and answer a query in O(n) time by scanning A forward and B backwards. The space usage of this second algorithm is O(n) words.
In <cit.> we argued that it is unclear how one can do better than these algorithms, which led us to introduce the following conjecture regarding the  problem.

Strong  Conjecture: There is no solution for the  problem with n^2-Ω(1) space and n^1-Ω(1)  query time.





  
Our results.
In this paper we design an algorithm for the  problem, which is summarized in the following theorem, and refutes the strong  conjecture.


For any 0<δ<1 there exists an algorithm that solves the  problem whose space usage is O(n^2-δ/3) words and the cost of a query is O(n^δ) time.


Notice that if δ = 3/4 then the space usage is n^1.75 while the query time is n^0.75, thereby refuting the  conjecture.



  
Related work.
Independently from our work, Golovnev et al. <cit.> discovered a similar algorithm for the  problem.




§ THE ALGORITHM



  
.
To prove Theorem <ref> we prove a more general theorem for the  problem, where the goal is to preprocess k-1 lists of elements A_1,A_2,…,A_k-1∈ U^n where A_i = (a_i,1, a_i,2, …, a_i,n), such that given an element c∈ U one can quickly determine whether there exists (x_1,x_2,…,x_k-1)∈ A_1× A_2 ×⋯× A_k-1 such that ∑_i=1^k-1x_i=c.
Notice that Theorem <ref> implies Theorem <ref> when k=3.



For any 0<δ<1 and a constant natural k, there exists an algorithm that solves the  problem whose space usage is O(n^k-1-δ/3) words and the cost of a query is O(n^δ) time.







The algorithm has two main ingredients:
a carefully constructed function f:[n]^k-1→ [n]^k-1
and a data structure for inverting f.

Let A_1+A_2+⋯+A_k-1= {∑_j=1^k-1x_j|(x_1,x_2,…,x_k-1)∈ A_1× A_2×⋯× A_k-1}.




  
The function f.
Let g:[n]^k-1→ U be defined as g(i_1,i_2,…,i_k-1) = ∑_j=1^k-1a_j,i_j.
Let h:U→ [n]^k-1 be a function which maps elements from U to k-1 indices.
The function f is defined as f(i_1,i_2,…,i_k-1) = h(g(i_1,i_2,…,i_k-1)).
The role of f is to provide a mechanism for efficiently moving from k indices (i_1,i_2,…,i_k-1) to k indices (i'_1,i'_2,…,i'_k-1) = f(i_1,i_2,…,i_k-1).











  
Inverting f.
The key observation that the algorithm leverages is that when given c∈ U during query time, if there exist k-1 indices (i_1,i_2,…,i_k-1) ∈ A_1× A_2×⋯× A_k-1 such that ∑_j=1^k-1a_j,i_j = c, then 
    f(i_1,i_2,…,i_k-1) = h(g(i_1,i_2,…,i_k-1)) = h(∑_j=1^k-1a_j,i_j) = h(c).

Thus, if the answer to the  query c is “yes" then there exists i_1,i_2,…,i_k-1∈ [n] such that (i_1,i_2,…,i_k-1) ∈ f^-1 (h(c)).



In order to compute f^-1, the algorithm uses a result by Fiat and Naor <cit.> which is summarized by the following theorem[We remark that the algorithm of Fiat and Naor in <cit.> is randomized, while the version of the algorithm stated in Theorem <ref> is deterministic. The difference is due to the unlimited preprocessing time which allows to convert the algorithm of <cit.> into a deterministic algorithm.].



  For any function f:D→ D where |D|= N and for any choice of values  (S,T) such that T· S^3 = N^3, there exists an algorithm for inverting f that uses Õ(S) words of space and inverts f in Õ(T) time.


In our setting, N=n^k-1, and so if the query time is T=Θ̃(n^δ) for some 0<δ <1, then the space usage can be chosen to be  
    S=(N^3/T)^1/3 = Θ̃(n^k-1-δ/3) .




  
Dealing with large pre-images.
The inversion algorithm of Fiat and Naor returns only one of the elements in f^-1.
Thus, if the Fiat and Naor algorithm returns (i_1,i_2,…,i_k-1) ∈ f^-1 (h(c)), we cannot guarantee that ∑_j=1^k-1a_j,i_j = c even if the answer to the query is “yes".
Nevertheless, notice that if h is chosen so that for any z,z'∈ A_1+A_2+⋯+A_k-1, we have h(z) h(z'), then we are guaranteed that if the answer to the query is “yes" then the size of f^-1(c) is one[Notice that there could be several elements in [n]^k that map through g to some c∈ U. However, for the purpose of solving  it suffices to consider only one of those elements.].
  Unfortunately, in general storing such a function h requires too much space.
So instead, suppose h is a pair-wise independent function, and so for x,y∈ U where x y we have [h(x)=h(y)]=1/n^k-1.
Moreover, the function h is stored in O(k)=O(1) words of space.
An element z∈ A_1+A_2+⋯+A_k-1 is said to be h-singleton if for any z'∈ A_1+A_2+⋯+A_k-1 where z z we have h(z) h(z').
From the properties of pair-wise independent functions, there are Ω(n^k-1) h-singleton elements.
Thus, if c is h-singleton then there is only one element in f^-1(c).

Now, if instead of choosing one h function the algorithm repeats the process O(log n) times with functions h_1,h_2…,h_O(log n), then with high probability each z∈ A_1+A_2+⋯+A_k-1 is a h_ℓ-singleton for some 1≤ℓ≤ O(log n). Notice that since the algorithm is allowed to have a large preprocessing time, the algorithm can select the functions  h_1,h_2…,h_O(log n) while deterministically guaranteeing that each z∈ A_1+A_2+⋯+A_k-1 is a h_ℓ-singleton for some ℓ≤ O(log n).


Finally, the algorithm constructs f_ℓ = h_ℓ(g(i_1,i_2,…,i_k-1)) for 1≤ℓ≤ O(log n), and for each f_ℓ the algorithm preprocesses f_ℓ using the Fiat and Naor algorithm.
Given a query c, the algorithm computes f_ℓ^-1(c) for all 1≤ℓ≤ O(log n), and for each
(i_1,i_2,…,i_k-1)=f_ℓ^-1(c) the algorithm computes g(i_1,i_2,…,i_k-1) in O(k)=O(1) time. If g(i_1,i_2,…,i_k-1)=c at least once, then the algorithm returns “yes".
However, if g(i_1,i_2,…,i_k-1) c for all 1≤ℓ≤ O(log n) then the algorithm answers “no".

Finally, using O(log n) functions implies that if the query time is T=Õ(n^δ) then the space usage is S=Õ(n^k-1-δ/3).



 §.§ Random Instances of 

For the  problem, even random inputs are considered to be hard.
However, for , our algorithm obtains faster bounds for random instances.
The reason for this improvement is that the tradeoff cost of the algorithm of Fiat and Naor <cit.> is reduced to T· S^2 = N^2 whenever the function f is random[See the discussion in Section 3 of <cit.>.], and since in our case f(i_1,i_2,…,i_k-1) depends on the values of a_1,i_1,a_2,i_2,…, a_k-1,i_k-1 which are all random elements, we obtain the following theorem.




For any 0<δ<1 there exists an algorithm that solves the  problem on a uniformly random instance whose space usage is O(n^k-1-δ/2) words and the cost of a query is O(n^δ) time.



Notice that, for , if δ = 3/4 then the space usage of the algorithm for random instances  is n^1.625 while the query time is n^0.75.

















































































§ ACKNOWLEDGMENTS

This research is supported by ISF grants no. 824/17 and 1278/16 and by an ERC grant MPM under the EU's Horizon 2020 Research and Innovation Programme (grant no. 683064).


plain






