How Hard is it to Find (Honest) Witnesses?
Isaac Goldstein∗1 , Tsvi Kopelowitz†2 , Moshe Lewenstein‡1 and Ely
Porat1
1

Bar-Ilan University
{goldshi,moshe,porately}@cs.biu.ac.il
University of Michigan
kopelot@gmail.com

2

arXiv:1706.05815v1 [cs.DS] 19 Jun 2017

Abstract
In recent years much eﬀort was put into developing polynomial-time conditional lower bounds for
algorithms and data structures in both static and dynamic settings. Along these lines we suggest
a framework for proving conditional lower bounds based on the well-known 3SUM conjecture.
Our framework creates a compact representation of an instance of the 3SUM problem using
hashing and domain speciﬁc encoding. This compact representation admits false solutions to
the original 3SUM problem instance which we reveal and eliminate until we ﬁnd a true solution.
In other words, from all witnesses (candidate solutions) we ﬁgure out if an honest one (a true
solution) exists. This enumeration of witnesses is used to prove conditional lower bound on
reporting problems that generate all witnesses. In turn, these reporting problems are reduced to
various decision problems. These help to enumerate the witnesses by constructing appropriate
search data structures. Hence, 3SUM-hardness of the decision problems is deduced.
We utilize this framework to show conditional lower bounds for several variants of convolutions, matrix multiplication and string problems. Our framework uses a strong connection
between all of these problems and the ability to ﬁnd witnesses.
Speciﬁcally, we prove conditional lower bounds for computing partial outputs of convolutions
and matrix multiplication for sparse inputs. These problems are inspired by the open question
raised by Muthukrishnan 20 years ago [22]. The lower bounds we show rule out the possibility
(unless the 3SUM conjecture is false) that almost linear time solutions to sparse input-output
convolutions or matrix multiplications exist. This is in contrast to standard convolutions and
matrix multiplications that have, or assumed to have, almost linear solutions.
Moreover, we improve upon the conditional lower bounds of Amir et al. [5] for histogram
indexing, a problem that has been of much interest recently. The conditional lower bounds we
show apply for both reporting and decision variants. For the well-studied decision variant, we
show a full tradeoﬀ between preprocessing and query time for every alphabet size > 2. At an
extreme, this implies that no solution to this problem exists with subquadratic preprocessing
time and Õ(1) query time for every alphabet size > 2, unless the 3SUM conjecture is false. This
is in contrast to a recent result by Chan and Lewenstein [9] for a binary alphabet.
While these speciﬁc applications are used to demonstrate the techniques of our framework,
we believe that this novel framework is useful for many other problems as well.

1

Introduction

In recent years much eﬀort has been invested towards developing polynomial time lower
bounds for algorithms and data structures in both static and dynamic settings. This eﬀort is
directed towards obtaining a better understanding of the complexity class P for well-studied
∗
†
‡

This research is supported by the Adams Foundation of the Israel Academy of Sciences and Humanities
This research is supported by NSF grants CCF-1217338, CNS-1318294, and CCF-1514383
This research is supported by a BSF grant 2010437 and a GIF grant 1147/2011.

2

How Hard is it to Find (Honest) Witnesses?

problems which seem hard in the polynomial sense. The seminal paper by Gajentaan and
Overmars [13] set the stage for this approach by proving lower bounds for many problems in
computational geometry conditioned on the 3SUM conjecture. In the 3SUM problem we are
given a set A of n integers and we need to establish if there are a, b, c ∈ A such that a+b+c =
0. This problem has a simple O(n2 ) algorithm (and some poly-logarithmic improvements
in [6, 17]) but no truly subquadratic algorithm is known, where truly subquadratic means
O(n2−ǫ ) for some ǫ > 0. The 3SUM conjecture states that no truly subquadratic algorithm
exists for the 3SUM problem. Based on this conjecture, there has been a recent extensive
line of work establishing conditional lower bounds (CLBs) for many problems in a variety
of ﬁelds other than computational geometry, including many interesting dynamic problems,
see e.g. [1, 2, 3, 4, 19, 23].

1.1

Decision and Reporting Problems

Algorithmic problems come in many ﬂavors. The classic one is the decision variant. In this
variant, we are given an instance of a problem and we are required to decide if it has some
property or not. Some examples include: (1) given a 3-CNF formula we may be interested
in deciding if it satisﬁable by some truth assignment; (2) given a bipartite graph we may be
interested in deciding if the graph has a perfect matching; (3) given a text T and a pattern
P we may be interested in deciding if P occurs in T . It is well-known that the ﬁrst example
is NP-complete while the two others are in P. An instance that has the property in question
has at least one witness that proves the existence of the property. In the examples above a
witness is: (1) a satisfying assignment; (2) a perfect matching in the graph; (3) a position of
an occurrence of P in T . Sometimes, we are not only interested in understanding if a witness
exists, but rather we wish to enumerate all of the witnesses. This is the reporting variant of
the problem. In the examples mentioned above the goal of the reporting variant is to: (1)
enumerate all satisfying assignments; (2) enumerate all perfect matchings; (3) enumerate all
occurrences of P in T . For the ﬁrst two examples it is known from complexity theory that
it is most likely hard to count the number of witnesses (not to mention reporting them)
(these are #P-complete problems), while the third example can be solved by classic linear
time algorithms.
In this paper we investigate the interplay between the decision and reporting variants of
algorithmic problems and present a systematic framework that is used for proving CLBs for
these variants. We expect this framework to be useful for proving CLBs on other problems
not considered here.

1.2

Our Framework

We introduce and follow a framework that shows 3SUM-hardness of decision problems via
their reporting versions. The high-level idea is to reduce an instance of 3SUM to an instance
of a reporting problem, and then reduce the instance of a reporting problem to several
instances of its decision version using a sophisticated search structure. The outline of this
framework is described next.
Compact Representation. One of the diﬃculties in proving CLBs based on the 3SUM
conjecture is that the input universe for 3SUM could be too large for accommodating a
reduction to a certain problem. To tackle this, we embed the universe using special hashing techniques. This is sometimes coupled with a secondary problem-speciﬁc encoding
scheme in order to match the problem at hand.

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

Reporting. The embedding in the ﬁrst step may introduce false-positives. To tackle
this, we report all the candidate solutions (witnesses) for the embedded 3SUM instance,
in order to verify if a true solution (an honest witness) to 3SUM really exists. This
is where we are able to say something about the diﬃculty of solving reporting problems. This is done by reducing the embedded 3SUM instance to an instance of such a
reporting problem, if it provides an eﬃcient way to ﬁnd all the false-positives. In some
cases, such reductions reveal tradeoﬀ relationships between the preprocessing time and
reporting/query time.
Reporting via Decision. In this step the goal is to establish 3SUM-hardness of a
decision problem. To do so we reduce an instance of the reporting version of the problem
to instances of the decision version by creating a data structure on top of the many
instances of the decision version. This data structure allows us to eﬃciently report all
of the elements in the output of the instance of the reporting version. By constructing
the data structure in diﬀerent ways we obtain varying CLBs for the decision variants
depending on the speciﬁc structure that we use.
By following this route we introduce new CLBs for some important problems which are
discussed in detail in Section 2. We point out that the embedding in the ﬁrst step follows
along the lines of [23] and [19]. However, in some cases we also add an additional encoding
scheme to ﬁt the needs of the speciﬁc problem at hand.
Implications. In Section 2 we discuss three applications from two diﬀerent domains which
utilize our framework for proving CLBs, thereby demonstrating the usefulness of our framework. Table 1 in Appendix A summarizes these results. Of particular interest are new
results on Histogram Indexing (deﬁned in Section 2) which, together with the algorithm
of [9], demonstrate a sharp separation when allowing truly subquadratic preprocessing time
between binary and trinary alphabet settings. Moreover, our framework is the ﬁrst to obtain
a CLB for the reporting version, which, as opposed to the decision variant, also holds for
the binary alphabet case. See Table 2 in Appendix A.

2

Applications

Convolution Problems
The convolution of two vectors u, v ∈ {R+ ∪ {0}}n is a vector w, such that w[k] =
Pk
i=0 u[i]v[k − i] for 0 ≤ k ≤ 2n − 2. Computing the convolution of u and v takes O(n log n)
time using the celebrated FFT algorithm. Convolutions are used extensively in many areas
including signal processing, communications, image compression, pattern matching, etc. A
convolution witness for the kth entry in w is a pair (a, b) such that a+b = k and u[a]·v[b] > 0.
In other words, the witnesses of entry k in w are all values i that contribute a non-zero value
Pk
to the summation w[k] = i=0 u[i]v[k − i]. The ﬁrst convolution problem we consider is
the convolution witnesses problem which is deﬁned as follows.
◮ Definition 1. In the convolution witnesses problem we preprocess two vectors u, v ∈
{R+ ∪ {0}}n and their convolution vector w, so that given a query integer 0 ≤ k ≤ 2n − 2,
we list all convolution witnesses of index k in w.
We prove the following CLB for the convolution witnesses problem that holds even if u
and v are binary vectors and all numbers in w are non-negative integers.
◮ Theorem 1. Assume the 3SUM conjecture is true. Then for any constant 0 < α <
1, there is no algorithm solving the convolution witnesses problem with O(n2−α ) expected
preprocessing time and O(nα/2−Ω(1) ) expected amortized query time per witness.

3

4

How Hard is it to Find (Honest) Witnesses?

Theorem 1 implies that when using only truly subquadratic preprocessing time one is
required to spend a signiﬁcant polynomial amount of time on every single witness. In particular, this means that, assuming the 3SUM conjecture, one cannot expect to ﬁnd witnesses
much faster than following the naive algorithm for computing convolution naïvely according
to the convolution deﬁnition. This is in contrast to the decision version of the problem,
where we only ask if a witness exists. This variant is easily solved using constant query time
after a near linear time preprocessing procedure (computing the convolution itself).
Another variation of the convolution problem which we consider is the sparse convolution
problem. There are two diﬀerent problems named sparse convolution, both appearing as open
questions in a paper by Muthukrishnan [22]. In the ﬁrst, which is now well understood, we
are given Boolean vectors u and v of lengths N and M , where M < N . There are n ones
in u, m ones in v and z ones in w, where w is the Boolean convolution vector of u and
v. The goal is to report the non-zero elements in w in Õ(z) time. This problem has been
extensively studied, and the goal has been achieved; see for example [9, 11, 15]. The second
variant which we call partial convolutions is as follows.
◮ Definition 2. The partial convolution problem on two vectors u and v of real numbers
(of length N and M respectively, where M < N ) and a set S of indices is to compute, for
each i ∈ S, the value of the i-th element in the convolution of u and v.
Muthukrishnan in [22] asked if it is possible to compute a partial convolution signiﬁcantly
faster than the time needed to compute a (classic) convolution. We prove a CLB based on
the 3SUM conjecture, that holds also for the special case of Boolean vectors, and, therefore,
also for the special case in which we only want to know if the output values at indices in S
are zero or more. Moreover, we focus on the important variant of this problem that deals
with the case where the two input vectors have only n = O(N 1−Ω(1) ) ones and are both
given implicitly (specifying only the indices of the ones). Our results also extend to the
indexing version of the partial convolution problem, which we call the partial convolution
indexing problem, and is deﬁned as follows.
◮ Definition 3. The partial convolution indexing problem is to preprocess an N -length
vector u of real numbers and a set of indices S to support the following queries: given an
M -length vector v (M < N ) of real numbers, for each i ∈ S compute the value of the i-th
element of the convolution of u and v.
Once again this variant already relevant when the input is Boolean and sparse, i.e. u
and v have n = O(N 1−Ω(1) ) ones and are represented implicitly by specifying their indices.
We prove the following CLBs for these problems with the help of our framework.
◮ Theorem 2. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial convolution problem with O(N 1−Ω(1) ) time, even if |S| and the number of ones in
both input vectors are less than N 1−Ω(1) .
◮ Theorem 3. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial convolution indexing problem with O(N 2−Ω(1) ) preprocessing time and O(N 1−Ω(1) )
query time, even if both |S| and the number of ones of the input vectors are O(N 1−Ω(1) ).
As mentioned above, the convolution of vectors of length N can be computed in Õ(N )
time with the FFT algorithm. However, in the partial convolution problem and partial convolution indexing problem, despite the input vectors being sparse and represented sparsely
(specifying only the O(N 1−Ω(1) ) indices of the ones in each vector), and despite the portion

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

of the output we need to compute being sparse (|S| = O(N 1−Ω(1) )), no linear time algorithm
(in n = O(N 1−Ω(1) )) exists, unless the 3SUM conjecture is false.
Notice that the partial convolution problem and its indexing variant are decision problems, since they require a decision for each location i ∈ S, whether w[i] > 0 or not. This is
in contrast to the convolution witnesses problem, which is a reporting problem, as it requires
the reporting of all of the witnesses for w[i].
To prove CLBs for the convolution problems we follow our framework. That is, we ﬁrst
use a hash function to embed a 3SUM instance to a smaller universe. This mapping introduces false-positives, which we enumerate by utilizing the reporting problem of convolution
witnesses. To solve the reporting version we reduce it to several instances of a decision problem, partial convolution or its indexing variant, by constructing a suitable data structure.
Tying it all together leads to CLBs for both the reporting and decision problems.
Matrix Problems
We also present some similar CLBs for matrices.
◮ Definition 4. The partial matrix multiplication problem on two N × N matrices A
and B of real numbers and a set of entries S ⊆ N × N is to compute, for each (i, j) ∈ S,
the value (A × B)[i, j].
The indexing variant of this problem is deﬁned as follows.
◮ Definition 5. The partial matrix multiplication indexing problem is to preprocess
an N × N matrix A of real numbers and a collection S = {S1 , S2 , ..., Sk } of sets of entries,
where Si ⊆ N × N , so that given a sequence B1 , . . . , Bk of N × N matrices of real numbers,
we enumerate the entries of A × Bi that correspond to Si .
Pk
For S = {S1 , S2 , ..., Sk } let SIZE(S) = i=1 |Si |. We prove the following CLBs, which
hold also for the special case of Boolean multiplication assuming that the input is given
implicitly by specifying only the indices of the ones.
◮ Theorem 4. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial matrix multiplication problem running in O(N 2−Ω(1) ) expected time, even if |S| and
the number of ones in the input matrices is O(N 2−Ω(1) ).
◮ Theorem 5. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial matrix multiplication indexing problem with O(SIZE(S)) preprocessing time and
O(N 2−Ω(1) ) query time.
Matrix multiplication, and in particular Boolean matrix multiplication, can be solved in
Õ(nω ) time, where ω ≈ 2.373 [14, 25]. Many researchers believe that the true value of ω
is 2. This belief implies that the running time for computing the product of two Boolean
matrices is proportional to the size of the input matrices and the resulting output. However,
our results demonstrate that such a result is unlikely to exist for sparse versions of the
problem, where the number of ones in the matrices is O(N 2−Ω(1) ) and we are interested in
only a partial output matrix (only O(N 2−Ω(1) ) entries of the matrix product).
To prove Theorem 4 and 5 we follow our framework. The process is very similar to the
path for proving CLBs for convolution problems. In fact, instead of considering a reporting
version of the partial matrix multiplication problem for proving these CLBs, we once again
utilize the reporting problem of convolution witnesses. However, this time we transform the
convolution witnesses to the matrix multiplication problems using a more elaborate data
structure. The main diﬃculty in this transformation is to guarantee the sparsity of both the

5

6

How Hard is it to Find (Honest) Witnesses?

input and the required output. This transformation illustrates how a reporting version of
a problem can be used to prove CLBs for decision versions of other problems, by changing
the way we look for honest witnesses.
String Problems
Another application of our framework, which is seemingly unrelated to the previous two, is
the problem of histogram indexing. A histogram, also called a Parikh vector, of a string T
over alphabet Σ is a |Σ|-length vector containing the character count of T . For example, for
T = abbbacab the histogram is ψ(T ) = (3, 4, 1).
◮ Definition 6. In the histogram indexing problem we preprocess a string T to support
the following queries: given a query Parikh vector ψ, return whether there is a substring T ′
of T such that ψ(T ′ ) = ψ.
◮ Definition 7. In the histogram indexing reporting problem we preprocess a string
T to support the following queries: given a query Parikh vector ψ, report indices of T at
which a substring T ′ of T begins such that ψ(T ′ ) = ψ.
The problem of histogram indexing (not the reporting version) is sometimes called
jumbled indexing. It has received much attention in recent years. For example, for binary alphabets - that is histograms of length 2 - there is a straightforward algorithm with
O(n2 ) preprocessing time and constant query time, see [10]. Burcsi et al. [8] and Moosa and
Rahman [20] improved the preprocessing time to O(n2 / log n). Using the four-Russian trick
a further improvement was achieved by Moosa and Rahman [21]. Then, using a connection to the recent improvement of all-pairs-shortest path by Williams [24], as observed by
Bremner et al. [7] and by Hermelin et al. [16], the preprocessing time was further reduced
n2
) . Finally, Chan and Lewenstein [9] presented an O(n1.859 ) preprocessing
to O( 2Ω(log
n)0.5
time algorithm for the problem with constant query time. For non-binary alphabets some
progress was achieved in the work by Kociumaka et al. [18] and even further achievement
was shown in [9]. On the negative side, some CLBs were recently shown by Amir et al. [5].
We follow our framework and ﬁrst obtain CLBs for the reporting version of histogram
indexing. This is the ﬁrst time CLBs are shown for the reporting version. Moreover, these
CLBs apply to binary alphabets, as opposed to the decision version in which there currently
is no CLB known for binary alphabets. The CLBs for the reporting version admit a full
tradeoﬀ between preprocessing and query time. For the decision variant, we improve upon
the CLB by Amir et al. [5] by presenting full-tradeoﬀs between preprocessing and query
time based on the standard 3SUM conjecture. Speciﬁcally, our new CLB implies that no
solution to the histogram indexing problem exists with subquadratic preprocessing time and
Õ(1) query time for every alphabet size bigger than 2, unless the 3SUM conjecture is false.
This demonstrates a sharp separation between binary and trinary alphabets, since Chan
and Lewenstein [9] introduced an algorithm for histogram indexing on binary alphabets
with Õ(n1.859 ) preprocessing time and constant query time. A complete comparison of our
results and the results by Amir et al. [5] appears in Table 2 in Appendix A.
The CLBs are summarized by the following theorems.
◮ Theorem 6. Assume the 3SUM conjecture is true. Then the histogram reporting problem
2γ
for an N -length string and constant alphabet size ℓ ≥ 2 cannot be solved using O(N 2− ℓ+γ −Ω(1) )
γ
γℓ
2γ
preprocessing time, O(N 1− ℓ+γ −Ω(1) ) query time and O(N ℓ+γ − ℓ+γ −Ω(1) ) reporting time per
item, for any 0 < γ < ℓ.
◮ Theorem 7. Assume the 3SUM conjecture holds. Then the histogram indexing problem for

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

7
2(1−α)

a string of length N and constant alphabet size ℓ ≥ 3 cannot be solved with O(N 2− ℓ−1−α −Ω(1) )
preprocessing time and O(N 1−

1+α(ℓ−3)
ℓ−1−α −Ω(1)

) query time.

The main structure of these proofs follows our framework. We ﬁrst embed a 3SUM
instance and encode it in a string with limited length. We then report the false-positives
using the reporting variant of the histogram indexing problem, which implies CLBs for this
variant. Finally, we reduce the reporting version to the decision version thereby obtaining
CLBs for the decision version. The reduction utilizes a sophisticated data structure for
reporting witnesses using many instances of the decision version.

3

Preliminaries

In the basic 3SUM problem we are given a set A of n integers and we need to answer whether
there are a, b, c ∈ A such that a + b + c = 0. In a common variant of the classic problem,
which we also denote by 3SUM, three arrays A, B and C are given and we need to answer
whether there are a ∈ A, b ∈ B, c ∈ C such that a + b + c = 0. Both versions have the same
computational cost (see [13]). There are some other variants of the 3SUM problem shown to
be as hard as 3SUM up to poly-logarithmic factors. One such variant is Convolution3SUM,
shown to be hard by Pǎtraşcu [23], see also [19]. In Convolution3SUM A is an ordered set and
we need to answer whether there exist indices 0 ≤ i, j ≤ n−1 such that A[i]+A[j] = A[i+j].
We also deﬁne DiffConv3SUM, in which we are given an ordered set A and we need to verify
whether there exists 0 ≤ i, k ≤ n − 1 such that A[k] − A[i] = A[k − i]. It is easy to see that
this is equivalent to Convolution3SUM.
Let H be a family of hash functions from [u] → [m]. H is called linear if for any h ∈ H
and any x, x′ ∈ [u], we have h(x) + h(x′ ) ≡ h(x + x′ ) (mod m). H is called almost-linear if
for any h ∈ H and any x, x′ ∈ [u], we have either h(x) + h(x′ ) ≡ h(x + x′ ) + ch (mod m), or
h(x) + h(x′ ) ≡ h(x + x′ ) + ch + 1 (mod m), where ch is an integer that depends only on the
choice of h. For a function h : [u] → [m] and a set S ⊂ [u] where |S| = n, we say that i ∈ [m]
is an overﬂowed value of h if |{x ∈ S : h(x) = i}| > 3n/m. H is called almost-balanced if for
a random h ∈ H and any set S ⊂ [u] where |S| = n, the expected number of elements from
S that are mapped to overﬂowed values is O(m). See [19] for constructions of families that
are almost-linear and almost-balanced (see also [6, 12]).
For simplicity of presentation, and following the footsteps of previous papers that have
used such families of functions [6, 23], we assume for the rest of the paper that almost
linearity implies that for any h ∈ H and any x, x′ ∈ [u] we have h(x) + h(x′ ) ≡ h(x +
x′ ) (mod m). There are actually two assumptions taking place here. The ﬁrst is that
there is only one option of so-called linearity. Overcoming this assumption imposes only a
constant factor overhead. The second assumption is that ch = 0. However, the constant
ch only aﬀects oﬀsets in our algorithm in a straightforward and not meaningful way, so we
drop it in order to avoid clutter in our presentation.

4

Convolution Witnesses

We ﬁrst prove a CLB for the convolution witnesses problem. We begin with a lemma which
has elements from the proof of Pǎtraşcu’s reduction [23] and from [6]. However, the lemma
diverges from [23] by treating the hashed subsets diﬀerently. Speciﬁcally, many special 3SUM
subproblems are created and then reduced to convolution witnesses.
We say that a binary vector of length n is r-sparse if it contains at most r 1’s. An
instance of convolution witnesses problem (u, v, w) is (n, R)-sparse if u and v are both of

8

How Hard is it to Find (Honest) Witnesses?

length n and n/R-sparse.
◮ Lemma 1. Let sequence A = hx1 , · · · , xn i be an instance of Convolution3SUM. Let R =
O(nδ ), where 0 < δ < 0.5 is a constant. There exists a truly subquadratic reduction from
the instance A to O(R2 ) (n, R)-sparse instances of convolution witnesses problem for which
we need to report O(n2 /R) witnesses (over all instances).
Proof. We use an almost-linear, almost-balanced, hash function h : U → [R] and create R
buckets B0 , · · · , BR−1 where each Ba contains the indices of all elements xi ∈ A for which
h(xi ) = a. Since h is almost-balanced the expected overall number of elements in buckets
with more than 3n/R elements is O(R). For each index i in an overﬂowed bucket, we verify
whether xi +xj = xi+j for every other j in O(n) time. Hence, we verify whether any index in
an overﬂowed bucket is part of a Convolution3SUM solution in O(nR) expected time. Since
R = O(n1−Ω(1) ) the expected time is truly subquadratic time.
We now assume that every bucket contains at most 3n/R elements. From the properties
of almost-linear hashing, if xi +xj = xi+j then h(xi )+h(xj ) mod R = h(xi+j ) mod R. Hence,
if xi + xj = xi+j then i ∈ Ba , j ∈ Bb implies that i + j ∈ Ba+b mod R .
Every three buckets form an instance of 3SUM and are uniquely deﬁned by a and b.
Hence, there are R(R − 1)/2 = O(R2 ) 3SUM subproblems each on O(n/R) elements from
the small universe [n]. However, h may generate false positives. So, we must be able to
verify that any 3SUM solution (a witness) for any instance is indeed a solution (an honest
witness) for the problem on A. The number of false positives is expected to be O(n2 /R)
over all O(R2 ) instances, see [6]. So, we need an eﬃcient tool to report each such witness
in order to be able to solve Convolution3SUM.
To obtain such a tool, we reduce the problem to the convolution setting in the following
way. We generate a characteristic vector va of length n for every set Ba (va [i] = 1 if
i ∈ Ba and va [i] = 0 otherwise, for 0 ≤ i < n). This vector will be 3n/R-sparse, since
|Ba | ≤ 3n/R. Note that: i ∈ Ba , j ∈ Bb and i + j ∈ Ba+b mod R ⇐⇒ va [i] = 1, vb [j] =
1 and va+b mod R [i + j] = 1. Now, for each pair of vectors, va and vb , we generate their
convolution. Let v = va ∗ vb be the convolution of va and vb , and let ℓ = v[i + j]. If
va+b mod R [i + j] = 1, then we need to extract the ℓ witnesses of v[i + j]. For each witness
(i, j) we check whether xi + xj = xi+j . We note that if, while verifying, we discover that
the overall number of the false-positives exceeds expectation (cn2 /R, for some constant c)
by more than twice we rehash.
Thus, we see that Convolution3SUM can be solved by generating O(R2 ) (n, R)-sparse
instances of convolution witnesses problem. These instances are computed in O(nR2 ) time,
◭
which is truly subquadratic as R = O(nδ ) for δ < 1/2.
It now follows that:
◮ Theorem 1. Assume the 3SUM conjecture is true. Then for any constant 0 < α <
1, there is no algorithm solving the convolution witnesses problem with O(n2−α ) expected
preprocessing time and O(nα/2−Ω(1) ) expected amortized query time per witness.
Proof. We make use of Lemma 1 and its parameter R. In particular, the total cost of
solving Convolution3SUM is at most O(R2 · P (n, R) + n2 /R · Q(n, R)) expected time, where
P (n, R) is the time needed to preprocess an (n, R)-sparse instance of a convolution witness
and Q(n, R) is the time per witness query for an (n, R)-sparse instance of a convolution
witness.
If we choose R = nα/2−Ω(1) we have that for P (n) = O(n2−α ) and Q(n) = O(nα/2−Ω(1) )
we solve Convolution3SUM in O(n2−Ω(1) ) time which is truly subquadratic.
◭

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

5

From Reporting to Decision I: Hardness of Partial Convolutions

We further consider the problem of reporting witnesses for convolutions. However, now we
use the third step of our framework. We will construct a search data structure over decision
problems which will allow us to eﬃciently search for witnesses. This will be our method for
proving CLBs for the decision problems of partial convolutions [22]. Speciﬁcally, we intend
to generate a data structure that uses convolutions on small sub-vectors of the input vectors
in order to solve the problem. However, the data structure cannot be fully constructed as
it will be too large. Hence, the construction is partial and we defer some of the work to the
query phase.
We start with Lemma 1, and focus on an (n, R)-sparse instance of the convolution witnesses problem(u, v, w). We generate a specialized search tree for eﬃciently ﬁnding witnesses,
which is created in an innovative way exploiting the sparsity of the input.

5.1

Search Tree Construction

Assume, without loss of generality, that n is a power of 2. We construct a binary tree in the
following way. First, we generate the root of the tree with the convolution of v and u. Then
we split u into 2 sub-vectors, say u1 and u2 , each containing exactly n/(2R) 1s. For each
sub-vector we generate nodes that are children of the root, where the ﬁrst node contains
the convolution of v and u1 and the second node contains the convolution of v and u2 . We
continue this construction recursively so that at the ith recursive level we partition u into
2i sub-vectors each containing n/(2i R) 1s. A vertex at level i represents the convolution of
v and a sub-vector uA containing n/2i R 1s. The vertex has two children, one represents
the convolution of v and the sub-vector of uA with the ﬁrst n/2i+1 R 1s of uA (denoted by
uA,1 ). The other represents the convolution of v and the rest of uA with the other n/2i+1 R
1s (denoted by uA,2 ). We stop the construction at the leaf level in which u is split to subvectors that each one of them contains X/R 1s from u, for some X < n to be determined
later. Calculating the convolution in each vertex is done bottom-up. First, we calculate
the convolution for each vertex in the leaf level. Then, we use these results to calculate
the convolution of the next level upwards. Speciﬁcally, if we have vertex that represent the
convolution v and some sub-vector uA and it has two children one which represents the
convolution of v and uA,1 and the other which represents the convolution of v and uA,2 ,
then (v ∗ uA )[k] = (v ∗ uA,1 )[k] + (v ∗ uA,2 )[k − l1 ] for every k ∈ [0, n + l1 + l2 − 1], where
l1 and l2 are the lengths of uA,1 and uA,2 respectively, and we consider the value of out of
range entries as zero. This way we continue to calculate all the convolutions in the tree until
reaching its root.
Construction Time. It is straightforward to verify that the total cost of the construction
procedure is dominated by the time of constructing the lowest level of the binary tree. In
this level, we have n/X sub-vectors of u as each of them has X/R 1’s and the total number
of 1s in u is n/R. We calculate the convolution of v with each of these sub-vectors, which can
be done in Õ(n) time. Thus, the total time needed to build the tree is Õ(n2 /X). Therefore,
the total time for calculating the binary trees for all O(R2 ) (n, R)-sparse instances of the
convolution witnesses problem is Õ(R2 n2 /X).
Witness Search. To search for a witness we begin from the root of the binary tree and
traverse down to a leaf containing a non-zero value in the result of the convolution at the
query index (adjusting the index as needed while moving down the structure). The search
for a leaf costs logarithmic time per query (as the tree has logarithmic height and in each
level we just need to ﬁnd a child with a non-zero value in the convolution it represents in

9

10

How Hard is it to Find (Honest) Witnesses?

the speciﬁc index of interest). Within the leaf, representing the convolution of v and some
sub-vector uA of u we can simply ﬁnd a witness in Õ(X/R) time as uA contains just X/R
1s. Thus, as we have O(n2 /R) false-positives over all O(R2 ) instances, the total time for
ﬁnding all them is Õ(n2 X/R2 ).
Consequently, using the binary tree for solving Convolution3SUM will cost Õ(R2 n2 /X +
n2 X/R2 ) time, which for X = R2 is Θ̃(n2 ) time. Since the tradeoﬀ between the preprocessing
time and query time meets at n2 , any improvement to the running time of either of them
will imply a subquadratic solution for the Convolution3SUM problem.

5.2

Conditional Lower Bounds for Partial Convolution

As a consequence of our discussion above we obtain the following results regarding partial
convolution and its indexing variant:
◮ Theorem 2. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial convolution problem with O(N 1−Ω(1) ) time, even if |S| and the number of ones in
both input vectors are less than N 1−Ω(1) .
Proof. We make use of Lemma 1. In order to construct the binary tree as described in
Section 5.3, we need to be able compute the convolution of v with some sub-vector of u for
each leaf in the tree (all other convolution can be calculated eﬃciently from the convolutions
in the leaves as described in the previous section). Recall that both input vectors have
length N = n, n/R 1s (which is O(N 1−Ω(1) ) for R = na , where a is a positive constant),
and we are interested in ﬁnding their convolution result only at the O(n/R) indices (that
is, |S| = O(N 1−Ω(1) )). If we preprocess the input for partial convolution in truly sublinear
time (for example, proportional to n/R) then the total time for constructing all the search
trees will be O(R2 n2−Ω(1) /X) while the total query time will remain O(n2 X/R2 ). Choosing
X = nc for small enough constant c and setting R = X, we obtain a subquadratic solution
◭
to Convolution3SUM.
◮ Theorem 3. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial convolution indexing problem with O(N 2−Ω(1) ) preprocessing time and O(N 1−Ω(1) )
query time, even if both |S| and the number of ones of the input vectors are O(N 1−Ω(1) ).
Proof. Use Lemma 1 and the previous discussion. If the preprocessing time for the partial
convolution indexing problem is truly subquadratic and queries are answered in truly sublinear time then the total time for constructing all the structures for all O(R2 ) instances is
O(R2 [n2−Ω(1) +n1−Ω(1) ·n/X]) while the total time for all of the queries remains O(n2 X/R2)
(note that N = n). Choosing X = nc for small enough constant c and setting R = X, we
◭
obtain a subquadratic algorithm for Convolution3SUM.

5.3

Search Tree Construction

Notice that the convolution of u and v immediately provides the number of witnesses for
each index in linear time (since the vectors are binary).
Assume, without loss of generality, that n is a power of 2. Let X < n be a power of
2 to be determined later. For every 0 ≤ i ≤ log n − log X we split the two input vectors
to 2i sub-vectors of size n/2i , and for each pair of sub-vectors, one from u and one from
v, we compute their convolution. We construct a quad-tree such that each vertex contains
the convolution between two sub-vectors. Each vertex x (besides the leaves) has exactly 4

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

children, deﬁned in the following way. If x corresponds to the convolution between two subvectors uA and vB of length n/2i , then its children correspond to the convolutions between
the sub-vectors of length n/2i+1 that are the halves of the sub-vectors uA and vB .
P
Formally, the convolution vector is deﬁned to be w[k] = j u[j]v[k − j]. This is deﬁned
for all k ∈ [0, 2n−2]. Consider a vertex that represents sub-vectors uA and vB of length n/2i ,
where A = [a, a + n/2i − 1] and B = [b, b + n/2i − 1], i.e. uA = u[a]u[a + 1] · · · u[a + n/2i − 1].
Then, u[r] = uA [r − a] and v[r] = vB [r − b] (for a ≤ r < a + n/2i ). Hence, w[k] restricted
to A and B is
P
P
j uA [j − a]vB [k − b − a − (j − a)] = wA,B [k − a − b]. For
j uA [j − a]vB [k − j − b] =
most A and B the value wA,B [k − a − b] is out of scope, that is k − a − b ∈
/ [0, 2(n/2i ) − 2].
i
It is easy to verify that summing over the sub-vectors of size n/2 that are in scope for k,
P
w[k] = A,B wA,B [k − a − b]. Hence, if there is a witness for w[k] then we ﬁnd it by ﬁnding
a witness for wA,B where wA,B [k − a − b] is non-zero.
Construction Time. Every leaf in the quad-tree represents a pair (uA , vB ) where |A| =
|B| = X. Since the constructed tree is a complete quad-tree, it is straightforward to verify
that the total cost of the construction procedure is dominated by the time of constructing
the lowest level of the quad-tree. In this level, the length of the convoluted sub-vectors is X.
Thus, the total time needed to build the tree is Õ(n2 /X) since we compute the convolution
between every pair of sub-vectors (one from u and one from v) of length X (we have (n/X)2 )
pairs), and each such convolution costs X log X time. Thus, the total time for calculating
the quad trees for all O(R2 ) instances of the (n, R)-sparse convolution witnesses problem is
O(R2 n2 /X).
Witness Search. To search for a witness we begin from the root of the quad-tree and
traverse down to a leaf containing a non-zero value in the result of the convolution at the
query index (adjusting the index as needed while moving down the structure). The search
for a leaf costs logarithmic time per query (as the tree has logarithmic height and in each
level we just need to ﬁnd a child with non-zero value in the convolution it represents in the
speciﬁc index of interest). Within the leaf, representing a pair of sub-vectors A and B, we
compute all witnesses of wA,B [k − a − b] in Õ(X) time. Thus, the total time for ﬁnding all
the false-positives is Õ(n2 X/R).
Consequently, using the quad-tree for solving Convolution3SUM will cost Õ(R2 n2 /X +
2
n X/R) time. If we choose X = R1.5 we balance the two and obtain n2 R0.5 which is ω(n2 )
time, which is too high for obtaining a lower bound from the 3SUM conjecture. However,
we now reﬁne this idea.
Improved Construction. In order to obtain a better total running time we use a diﬀerent
construction as follows. For every 0 ≤ i ≤ log n − log X we only split u into 2i sub-vectors
of size n/2i , and compute the convolution between v and each sub-vector of u. Hence,
instead of a quad-tree we obtain a binary tree. In this tree, each vertex corresponds to
the convolution of v and a sub-vector uA of u of length n/2i and has as its children the 2
vertices corresponding to convolutions between v and the sub-vectors of length n/2i+1 that
are the halves of uA . Speciﬁcally, as before we deﬁne uA = u[a]u[a + 1] · · · u[a + n/2i − 1].
P
P
Moreover, w[k] =
i uA [i − a]v[k − i] =
i u[i]v[k − i] restricted to A (and all of v) is
P
u
[i
−
a]v[k
−
a
−
(i
−
a)]
=
w
[k
−
a].
A
A
i
The total cost of building this tree is O(n2 /X) time. The search for a leaf costs logarithmic time per query. Searching within the leaf will still cost O(X) time in order to ﬁnd all
witnesses for a speciﬁc index of the convolution it represents by using the naive algorithm.

11

12

How Hard is it to Find (Honest) Witnesses?

This still requires ω(n2 ) running time as before, even for the best choice of R. However, this
is a step toward the next reﬁnement that gives us the desired improvement.
Even Further Improvement. We further reduce the search time by splitting the vector
into (unequal sized) sub-vectors of u during the construction phase according to the location
of the 1s in u as opposed to sub-vector lengths. Recall that there are O(n/R) 1’s in u. For
the sake of clarity, assume that there are exactly n/R 1’s in u. First we generate the root of
the binary tree with the convolution of u and v. Then we split u into 2 sub-vectors, say u1
and u2 , each containing exactly n/2R 1’s. For each sub-vector we generate nodes that are
children of the root, where the ﬁrst node contains the convolution of u1 and v and the second
node contains the convolution of u2 and v. We continue this construction recursively so that
at the i’th recursive level we partition u into 2i sub-vectors each containing n/2i R 1’s. A
vertex at level i represents the convolution of v and a sub-vector uA containing n/2i R 1’s.
The vertex has two children, one which represents the convolution of v and the sub-vector
of uA with the ﬁrst n/2i+1 R 1’s of uA and the other which represents the convolution of v
and the rest of uA with the other n/2i+1 R 1’s.
The leaf level contains sub-vectors A with X/R 1’s from u. Hence, the computation of
P
all witnesses of wA [k − a] = i uA [i − a]v[k − a − (i − a)] only requires access to at most
X/R i’s for which uA [i − a] = 1, thereby taking O(n/X) time. Thus, the total time cost of
this reﬁned solution is O(R2 n2 /X + n2 X/R2 ) which for X = R2 is Θ(n2 ) time. Since the
tradeoﬀ between the preprocessing time and query time meets at n2 , any improvement to the
running time of either of them will imply a subquadratic solution for the Convolution3SUM
problem.

6

From Reporting to Decision II: Hardness of Partial Matrix
Multiplication

Using ideas of the same ﬂavor as those from Section 5 we prove CLBs on the partial matrix
multiplication problem, which is deﬁned in the introduction.
We start with Lemma 1 which shows how to reduce an instance of Convolution3SUM to
O(R2 ) instances of convolution witnesses problem. We will prove the CLB by showing that
partial matrix multiplication can be used to solve a major component of the computation
necessary. We focus, again, on two binary vectors u and v of size n (out of the O(R2 ) pairs
of vectors), each containing O(n/R) 1s, and their convolution result w. Similar to Section 5,
we construct a search tree to seek for witnesses. However, this time we partition each of the
vectors u and v into Θ(n/X) sub-vectors, and the partitioning method here slightly diﬀers
from the one in Section 5. The main obstacle is to guarantee the spareness of the input and
the required output of the matrices we will use in our construction.
The tree we construct for eﬃciently searching for witnesses is computed as follows.
Quad Tree Construction with Special Leaves First partition each vector to n/X
sub-vectors with each sub-vector containing O(X/R) 1s. Then, partition each sub-vector
whose length is more than X into smaller sub-vectors with length exactly X except the last
one that might be shorter. Pad each sub-vector with 0s, if necessary, so that all lengths are
exactly X. Denote the sub-vectors u1 , u2 , ..., uq . It is straightforward to observe that:
◮ Observation 1. Σqi=1 |ui | = O(n). That is, q = cn/X.
Hence, the partition of u is to (padded) sub-vectors u1 , u2 , ..., ucn/X , each of length X
and with O(X/R) 1s each. The same process is done for vector v and we get sub-vectors

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

v1 , v2 , ..., vc′ n/X that satisfy the same properties. We assume without loss of generality that
c = c′ and that cn/X is a power of two.
We construct a quad tree instead of the binary tree from Section 5.3. For integers
1 ≤ i < j denote by ui,j the sub-vector of u that is the concatenation of the sub-vectors
ui , ui+1 , . . . , uj . Similarly, for integers 1 ≤ i < j denote by vi,j the sub-vector of v that is the
concatenation of the sub-vectors vi , vi+1 , . . . , vj . The root of the quad tree will contain the
and v1, cn
.
result of the convolution (which we compute later) of u and v, which are u1, cn
X
X
The root has four children which correspond to all the convolutions between the 4 pairs
cn } × {v
cn , v cn
cn }. Recursively, a vertex representing
cn , u cn
of sub-vectors in {u1, 2X
1, 2X
2X +1, X
2X +1, X
the convolution of a pair ui,j and vi′ ,j ′ has 4 children representing the convolutions of the 4
sub-vector pairs in {ui,i+(j−i)/2 , u(i+(j−i)/2)+1,j } × {vi′ ,i′ +(j ′ −i′ )/2 , v(i′ +(j ′ −i)/2)+1,j ′ }.
Our goal is to compute for each vertex in this tree the convolution of the two sub-vectors
that it covers. In Section 5 we directly computed the convolution for every node. Here, we
will use matrix multiplication in order to achieve our reduction. We do the computation
on the leaves of the tree (we shortly explain how) and then use a bottom-up traversal of
the tree where we compute the convolution for an inner vertex from the convolutions of its
children (without computing it directly).
Seeking a Witness This is literally done in the same way as described in Section 5.3. When
we are looking for a witness for a query number xi we traverse down the tree in logarithmic
time, until we reach a leaf with at most O(X/R) 1s. A naive O(X/R) algorithm at the
sub-vectors of a leaf will complete the process. Thus the total query time is O(n2 X/R2 ).
Partial Convolution via Partial Matrix Multiplications We make use of matrix
multiplication in order to eﬃciently compute the convolutions at the leaves as follows.
′
We construct a set of matrices U = {U1 , U1′ , U2 , U2′ , ..., Ucn/X , Ucn/X
}, two for each ui as
follows. The ﬁrst row in matrix Ui is the sub-vector ui . The kth row of Ui is the sub-vector
ui shifted right by k, i.e. discard the k − 1 least signiﬁcant bits and add k − 1 0s to be
the new most signiﬁcant bits. Each such matrix is called a shift right matrix. In a similar
manner, the ﬁrst row in matrix Ui′ is the sub-vector ui . The kth row of Ui is the sub-vector
ui shifted left by k, i.e. discard the k − 1 most signiﬁcant bits and add k − 1 0s to be the
new least signiﬁcant bits. Each such matrix is called a shift left matrix
Now, construct a matrix V from the O(n/X) sub-vectors of v such that the ith column
of V is vi . This matrix has X rows and O(n/X) columns. We partition V into O(n/X 2 )
squared matrices V1 , V2 , ..., Vcn/X 2 each having exactly X rows and columns.
The matrix multiplication of Ui and Vj together with the matrix multiplication of Ui′ and
Vj computes all the shifts of ui with the X sub-vectors represented by Vj . In other words, we
are computing the convolution of X leaves with two matrix multiplication of two matrices
of size X × X. Hence, the overall time to compute the convolutions of the leaves will be
O(n/X · n/X 2 · T (X)) where T (X) is the time needed for multiplying two squared matrices
of size X × X. The computation of the convolution of inner vertices can be computed from
the convolution of its children. It is straightforward to see that the time of the computations
of the convolutions is dominated by the computation of the convolutions in the leaves.

6.1

Hardness of Partial Matrix Multiplication

We are now ready to prove the following CLBs on partial matrix multiplication and its
indexing variant.

13

14

How Hard is it to Find (Honest) Witnesses?

◮ Theorem 4. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial matrix multiplication problem running in O(N 2−Ω(1) ) expected time, even if |S| and
the number of ones in the input matrices is O(N 2−Ω(1) ).
Proof. Consider the reduction from Lemma 1. Finding O(n2 /R) witnesses from the O(R2 )
instances of witnesses convolution problem can be done by using the tree we have just
constructed and seeking witnesses within it. Recall that for each instance (u, v, w) of the
witnesses convolution problem we only look for witnesses for O(n/R) locations in w (that
corresponds to the indices in the bucket Ba+b mod R it represents, see details in Lemma 1).
As explained in the previous subsection, the total time to construct the quad tree is
O(n/X · n/X 2 · T (X)) where T (X) is the time needed for multiplying two squared matrices
of size X × X. The results of the matrix multiplications of some Vi and all the matrices in
U correspond to the convolution of X sub-vectors of v with u. However, as noted before,
we are interested in computing the result of each convolution only at O(n/R) locations
(that correspond to the indices speciﬁed by elements of bucket Ba+b mod R ). Therefore,
after partitioning u and creating the matrices in U which are of size X × X the number of
locations in the result of the multiplication of some Vi with some matrix in U that we are
interested in is X 2 /R in expectation. But we will require the worst-case number of locations
to be at most X 2 /R, so for each result that has more than X 2 /R locations which we are
interested in we will split the computation into several iterations, each time considering a
set of diﬀerent X 2 /R locations. Since the total number of locations over all the results is no
more than n/R, this only imposes a constant factor time overhead.
Now, in the construction time of the quad tree, instead of the time T (x) for multiplying
two squared matrices of size X × X we just require the time to compute their multiplication
in some speciﬁc X 2 /R locations. Moreover, the number of 1s in any Vi is O(X 2 /R) which
is also the number of 1s in any matrix in U . If the time for computing the multiplication
of these sparse matrices at the O(X 2 /R) speciﬁed locations is O(X 2−Ω(1) ) then the total
construction time will be O(n2 /X 1+Ω(1) ). Therefore, the total time for constructing all
the trees for all R2 instances will be O(R2 n2 /X 1+Ω(1) ), and the query time is O(n2 X/R2).
Choosing X = nǫ for some small constant 0 < ǫ and R = X 1/2+1/4ǫ we obtain a truly
◭
subquadratic solution for 3SUM.
◮ Theorem 5. Assume the 3SUM conjecture is true. Then there is no algorithm for the
partial matrix multiplication indexing problem with O(SIZE(S)) preprocessing time and
O(N 2−Ω(1) ) query time.
Proof. We make use of Lemma 1 and our quad tree. This time, we preprocess Vi with a
collection S = {S1 , S2 , ..., SO(n/X) }. Each set Si ∈ S corresponds to the O(X 2 /R) indices
of interest in the result of the multiplication of Vi and some matrix in U (see the details
in the proof of the previous theorem). After the preprocessing phase we answer queries to
compute the partial multiplication of Vi with matrices in U using the indices from sets in S.
The construction time of the quad tree is O(n/X · [P (X, n/R) + n/X 2 · Q(X, n/R)]), where
P (X, n/R) is the preprocessing time of partial matrix multiplication indexing for sparse
matrices of size X × X while SIZE(S) = O(n/R), and Q(X, n/R) is the corresponding
query time. Therefore, if there is an algorithm for the partial matrix multiplication indexing
problem with O(SIZE(S)) = O(n/R) preprocessing time and O(X 2−Ω(1) ) query time,
then the total construction time for all trees is O(R2 · n/X · [n/R + n/X 2 · X 2−Ω(1) ]) =
O(Rn2 /X +R2 n2 /X 1+Ω(1) ), and the total time spent on all queries is O(n2 X/R2 ). Choosing
X = nǫ for some small constant 0 < ǫ and R = X 1/2+1/4ǫ we obtain a truly subquadratic
◭
solution to 3SUM.

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

Notice that Theorems 4 and 5 hold even when considering the simple case of boolean
matrix multiplication.

7

Hardness of Data Structures for Histogram Indexing

In order to prove a CLB for both the histogram indexing problem and the histogram (indexing) reporting problem, we will ﬁrst focus on reducing 3SUM to the histogram reporting
problem, and then turn our focus to reducing the the histogram reporting problem to the
histogram indexing problem.

7.1

Reducing Convolution3SUM to Histogram Reporting

We are given an ordered set A of integers x1 , x2 , ..., xn for which we want to solve DiffConv3SUM. Our methodology here is to encode the input integers into a compact string S
so that histogram indexing with carefully chosen query patterns implies a solution to DiffConv3SUM. Since the size of the universe of the input integers can be as large as n3 , we
hash down the universe size while (almost) maintaining the linearity property of the input.
To do this, we make use of an almost-linear almost-balanced hash function h : U → [R] as
deﬁned in Section 3, and apply h to all of the input integers.
After utilizing h to compress the input range, we are ready to encode the input and
create the string S. To do this, we encode each h(xk ) separately, and then concatenate
the encodings in the same order as their corresponding original integers in A. We use the
following encoding scheme, using an alphabet Σ = {σ0 , σ1 , , ..., σℓ−1 }. Some other encoding
schemes, which surprisingly provide the same bounds, are discussed in Appendix B.
Encoding 1. The encoding will consist of two separate partial encodings concatenated
together. The ﬁrst partial encoding is partitioned into ℓ parts which together will represent h(xk ) in base R1/ℓ . For 0 ≤ j ≤ ℓ − 1 the jth part of this ﬁrst partial encoding is
a unary representation of pj,h(xk ) = ⌊h(xk )/Rj/ℓ ⌋ mod R1/ℓ using σj , and is denoted by
p(j,h(x ))

k
. The ﬁrst partial encoding of h(xk ), which we also call a regular
enc(j, h(xk )) = σj
encoding of h(xk ), is
encℓ (h(xk )) = enc(0, h(xk ))enc(1, h(xk )) · · · enc(ℓ − 1, h(xk ))
p0,h(xk ) p1,h(xk )
pℓ−1,h(xk )
= σ0
σ1
· · · σℓ−1
.
For the second partial encoding we encode the complement of each enc(j, h(xk )) which
is the unary representation of p̄j,h(xk ) = R1/ℓ − (⌊h(xk )/Rj/ℓ ⌋ mod R1/ℓ ) using σj , and is
denoted by enc(j, h(xk )). The second partial encoding of h(xk ), which we also call a complement encoding of h(xk ), is
p̄0,h(xk ) p̄1,h(xk )
p̄ℓ−1,h(xk )
encℓ (h(xk )) = enc(0, h(xk ))enc(1, h(xk )) · · · enc(ℓ−1, h(xk )) = σ0
σ1
· · · σℓ−1
.
The full encoding of h(xk ) is the concatenation of encℓ (h(xk )) and encℓ (h(xk )) which we
denote by EN Cℓ (h(xk )). Finally, the string S is set to be
1
EN Cℓ (h(x1 ))EN Cℓ (h(x2 )) · · · EN Cℓ (h(xn )). The size of S is clearly N = O(ℓ · R ℓ n). We
denote the substring of S starting at the location of the beginning of encℓ (h(xi )) and ending
at the location of the end of encℓ (h(xj )) by Si,j .

Consider a Parikh vector vk obtained from xk and h where the rth element has a count
of p̄r,h(xk ) + R1/ℓ · (k − 1). We say that vk represents xk . For a vector w = (w0 , w1 , ..., wm )
we deﬁne w>>1 = (0, w0 , w1 , ..., wm−1 ). We also deﬁne the carry set of vk to be Vk =
{vk + R1/ℓ u − u>>1 | u = (u0 , u1 , ..., uℓ−2 , 0), ui ∈ {0, 1} 0 ≤ i < ℓ − 1}. It is easy to see
that |Vk | = 2ℓ−1 and that Vk can be obtained from vk in O(ℓ · 2ℓ−1 ) time. We call vk the
base of Vk . We have the following lemma regarding Vk :

15

16

How Hard is it to Find (Honest) Witnesses?

◮ Lemma 2. If there exists a pair xi , xj such that xk = xj − xi and k = j − i, then the
Parikh vector of Si,j must be in Vk .
Proof. Since h is linear we know that h(xk ) = h(xj ) − h(xi ). This is equivalent to saying
ℓ−1
ℓ−1
ℓ−1
that R + R ℓ − h(xk ) = R + R ℓ − [h(xj ) − h(xi )] = (R + R ℓ − h(xj )) + h(xi ). In Si,j we
have the full encoding of all integers xi+1 , ..., xj−1 . There are exactly k − 1 integers between
xi and xj . Therefore, each of them adds R1/ℓ occurrences of each σr (0 ≤ r ≤ l − 1) to
Si,j . In addition to the full encodings of these integers we have two more partial encodings:
encℓ (h(xi )) and encℓ (h(xj )). Notice that encℓ (h(xi )) and encℓ (h(xj )) represent h(xi ) and
ℓ−1
R + R ℓ − h(xj ), respectively, in base R1/ℓ . If we look at the vector vk (the base of Vk )
after subtracting (k − 1)R1/ℓ from the count of each character, we obtain the representation
ℓ−1
of R + R ℓ − h(xk ) in base R1/ℓ , which intuitively implies that vk is the Parikh vector that
we are looking for. However, it is possible to generate a carry at each of the ℓ digits of the
ℓ−1
base R1/ℓ during the addition of (R + R ℓ − h(xj )) + h(xi ). To handle these carries we
consider all possible 2ℓ carry scenarios and generate a vector for each of the 2ℓ−1 scenarios.
These carry scenarios are exactly represented by the vectors in Vk , as each vector u in the
deﬁnition of Vk speciﬁes the indices in which we have a carry. Hence, the Parikh vector of
◭
Si,j must be one of the vectors in Vk .
Thus, we preprocess S with an algorithm for histogram reporting, and then query the
resulting data structure with all the vectors in Vk , whose base vk represents some xk , in an
attempt to decide if xk is part of a solution to DiffConv3SUM. The reported locations are
classiﬁed into two types:
Candidates: Locations where the histogram match begins and ends exactly between the
complement and regular encodings of two input integers. All these locations correspond to
xi and xj such that for the particular h(xk ) for which the query was constructed, we have
h(xk ) = h(xj ) − h(xi ) and also k = j − i.
Encoding Errors: All matches that are not candidates.
While encoding errors clearly do not provide a solution for DiffConv3SUM on A, candidates may also not be suitable for a solution since the function h introduces false-positives.
The following lemma bounds the total expected number of false-positives (both from falsepositive candidates and encoding errors) that can be reported by a single query vector (and
the vectors in the carry set that it serves as it base). Its proof appears in the appendix.
◮ Lemma 3. The expected number of false positives that are reported when considering all
1
vectors in Vk (whose base represents xk ) as queries is O(2ℓ−1 N/R1− ℓ ).
Proof. We focus on v ∈ Vk that is queried when considering xk . This vector v implies the
value of m which is the length of substrings of S that can have v as their Parikh vector.
Clearly, there are at most N such substrings. We focus on the substring from location α to
location α + m − 1 in S. Due to our encoding scheme, this substring contains a (possibly
empty) suﬃx of EN Cℓ (h(xi )), for some xi , followed by k − 1 full encodings of some integers
from A, and then a (possibly empty) preﬁx of EN Cℓ (h(xj )) , for some integers xi and xj .
The only way in which we may falsely report location α as a match is if for each σ ∈ Σ
the number of σ characters in the substring of S, denoted by f (σ, α, m), is equal to the
count of σ in v, denoted by vσ . For a given σ, since the substring contains k − 1 complete
encodings, we can consider vσ − (k − 1)R1/ℓ which is a function of p̄r,h(xk ) , compared to
f (σ, α, m) − (k − 1)R1/ℓ . Now, since p̄r,h(xk ) is uniformly random (due to h) in the range
[R1/ℓ ], the probability that they are equal is R−1/ℓ . This is true for every character σ
on its own, but when considering all of the ℓ characters, once we set the count for the

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

17

ﬁrst ℓ − 1 characters the count for the last character completely depends on the other
counts. Therefore, the probability that the comparison passes for all of the characters only
depends on the ﬁrst ℓ − 1 characters, and is 1/R1−1/ℓ . By linearity of expectation over all
possible locations in S and all 2ℓ−1 vectors in Vk , the expected number of false positives is
1
◭
O(2ℓ−1 N/R1− ℓ ).

7.2

Hardness of Histogram Reporting

Utilizing the reduction we have described in the previous section, that transforms an ordered
set A to a string S, we can prove the following CLB.
◮ Theorem 6. Assume the 3SUM conjecture holds. The histogram reporting problem for
2γ
an N -length string and constant alphabet size ℓ ≥ 2 cannot be solved using O(N 2− ℓ+γ −Ω(1) )
γ
γℓ
2γ
preprocessing time, O(N 1− ℓ+γ −Ω(1) ) query time and O(N ℓ+γ − ℓ+γ −Ω(1) ) reporting time per
item, for any 0 < γ < ℓ.
Proof. We follow the reduction in Section 7.1. For an instance of the histogram reporting
problem on a string of length N denote the preprocessing time by O(N α ), the query time by
O(N β ) and the reporting time per item by O(N δ ). The total expected running time used
by our reduction to solve DiffConv3SUM is O(N α ) + n · O(N β ) + Ef p · O(N δ ), where Ef p is
the expected total number of false positives. This running time must be Ω(n2−Ω(1) ), unless
3SUM conjecture is false.
1
1
1
Since N = O(ℓ · R ℓ n) and Ef p = O(n2ℓ N/R1− ℓ ), then either (ℓ · R ℓ n)α = Ω(n2−o(1) ),
1
1
1
1
(ℓ · R ℓ n)β = Ω(n1−o(1) ), or n2ℓ (ℓ · R ℓ n)/R1− ℓ · (ℓ · R ℓ n)δ = Ω(n2−o(1) ). Set R to be nγ .
2γ
By straightforward calculations following our choice of R we get that α = 2 − ℓ+γ
− Ω(1),
β =1−

7.3

γ
ℓ+γ

− Ω(1), and δ =

γℓ
ℓ+γ

−

2γ
ℓ+γ

− Ω(1).

◭

From Reporting to Decision: Hardness of Histogram Indexing

We make use of Theorem 6 to obtain a CLB on the decision variant of the problem. Amir
et al. [5] proved similar lower bounds based on a stronger 3SUM conjecture. Our proof here
shows that this stronger assumption is not needed and that the common 3SUM conjecture
suﬃces. The idea of the proof is to make the expected number of false-positives small by a
suitable choice of R.
◮ Lemma 4. Assume the 3SUM conjecture holds. The histogram indexing problem for a
2
string of length N and constant alphabet size ℓ ≥ 3 cannot be solved with O(N 2− ℓ−1 −Ω(1) )
1
−Ω(1)
1− ℓ−1
) query time.
preprocessing time and O(N
Proof. We follow the reduction in Section 7.1. In order to use histogram indexing we will
reduce the probability of a false positive for any query to be less than 1/2. From Lemma 3
ℓ−1

we know that the expected number of false positives due to query is at most O( 2
ℓ
ℓ−2

1

(ℓR ℓ n)

1
R1− ℓ

).

By setting R to be c1 n
for suﬃciently large constant c1 the number of false positives is
strictly smaller than 1/2, which implies immediately that the probability of a false positive
is strictly smaller than 1/2. Therefore, if we were to solve histogram indexing instead of
histogram reporting on the same input as in Theorem 6, the probability of a false positive is
less than 1/2. We can make this probability smaller by repeating the process O(log n) times,
each time using a diﬀerent hash function h. This way, the probability that all of the queries
that are due to a speciﬁc xk return false positives is less than 1/poly(n). If a given xk passes
all of the query processes (that is, a positive answer is received by each one of them), then we

18

How Hard is it to Find (Honest) Witnesses?

can verify that there is indeed a match with this xk in O(n) time, which will add a negligible
cost to the expected running time in the case it is indeed a false positive. Thus, the total
expected running time of this procedure is O(log n(P (N, ℓ)+nQ(N, ℓ))), where P (N, ℓ) is the
preprocessing time (for input string of length N and alphabet size ℓ) and Q(N, ℓ) is the query
time (for the same parameters). Therefore, unless the 3SUM conjecture is false, there is no
solution for histogram indexing such that P (N, ℓ) = O(n2−Ω(1) ) and Q(N, ℓ) = O(n1−Ω(1) ).
If we plug-in the value of R we have chosen and follow the calculations in the proof of
ℓ
), then we obtain that there is no solution for the histogram
Theorem 6 (with γ = ℓ−2
2

1

indexing problem with P (N, ℓ) = O(N 2− ℓ−1 −Ω(1) ) and Q(N, ℓ) = O(N 1− ℓ−1 −Ω(1) ).

◭

We generalize this CLB by presenting a full-tradeoﬀ between preprocessing and query
time. The idea of the proof is to artiﬁcially split the encoded string S to smaller parts, so
we can have many false positives in S, but the probability for a false positive in each part
will be small.
◮ Theorem 7. Assume the 3SUM conjecture holds. The histogram indexing problem for a
2(1−α)
string of length N and constant alphabet size ℓ ≥ 3 cannot be solved with O(N 2− ℓ−1−α −Ω(1) )
preprocessing time and O(N 1−

1+α(ℓ−3)
ℓ−1−α −Ω(1)

) query time, for any 0 ≤ α ≤ 1.

Proof. The idea to get a full-tradeoﬀ between preprocessing time and query time is to
artiﬁcially split the encoded string S to smaller parts, so we can have many false positives in
S but the probability for a false positive in each part will be small. We achieve this artiﬁcial
split by using special character σ ∗ as a separator and construct a search data structure for
queries in the following way.
Search Structure Construction. Say we have encoded A using encoding 1 with ℓ − 1
characters and formed a string S. Let v = (vσ1 , vσ2 , ..., vσℓ−1 ) be a query Parikh vector such
that the sum of all counts in it is N/2. That is, v can be the Parikh vector of a substring of
S that has length N/2. We add nα − 1 special characters σ ∗ to S for some α ∈ [0, 1]. The
special characters are added to S at positions N/2 + aN/(2nα ) for 1 ≤ a < nα . We denote
the resulting string by S ′ .
Denote by uσ the count of character σ in the Parikh vector u. We generate nα vectors
from our query vector v. These vectors are given by the set
V = {vi = (vσ1 , vσ2 , ..., vσℓ−1 , vσ∗ )|vσ∗ = i 0 ≤ i < nα }. Querying S ′ with a vector v ′ ∈ V
such that vσ′ ∗ = i can ﬁnd a substring of S ′ with matching Parikh vector only if this substring
in S (without the special characters σ ∗ ) begins at location β ∈ [(i−1)N/(2nα ), iN/(2nα −1)].
This is because of the limitations posed by the special character σ ∗ .
To handle query vectors whose sum of counts is in the interval [N/4 + 1, N/2], we will
add more special characters to S. Speciﬁcally, we add 1 special character at positions
N/4 + iN/(4nα ) for 1 ≤ i ≤ nα , 2 special characters at positions N/2 + iN/(4nα ) for
1 ≤ i ≤ nα , and 3 special characters at positions 3N/4 + iN/(4nα ) for 1 ≤ i < nα . Again,
we denote the resulting string S ′ . With the special characters in S ′ , we can handle a query
Parikh vector v that the sum of its counts is len ∈ [N/4 + 1, N/2] in the following way. We
ﬁrst extend v to contain a count for σ ∗ and initialize it to the number of occurrences of σ ∗ in
the substring S ′ [0, len − 1] (the substring of S ′ that starts at location 0 and ends at location
len − 1). We call this vector v 0 . We create sequence of O(nα ) query vectors v i such that
v i is created from v 0 by adding i to vσ0 ∗ . It is straightforward to observe that each query
vector v i can match at most N/(4nα ) locations in S ′ . That is, by adding just O(nα ) special
symbols to S we artiﬁcially split the string to O(nα ) parts.
Multi-level Construction. We explain how to handle a query Parikh vector
v = (vσ1 , vσ2 , ..., vσℓ−1 ) that the sum of all counts in it is len ≤ |S|/4. To do this, we create a

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

structure with O(log n) levels, such that each one of them is created by cutting S and adding
O(nα ) special characters. Level 0 will be the string we constructed previously. For level i, we
cut the string S to 2i parts of (almost) equal length by cutting at positions j|S|/2i of S for
1 ≤ j ≤ 2i − 1. We adjust the cutting so that each part will end at the end of a full encoding
i
i
i
of some number xj . We denote the resulting parts by S1i = {S1,1
, S1,2
, ..., S1,2
i }. Moreover,
i+1
i
i
we also cut S at positions |S|/2 + j|S|/2 for 0 ≤ j ≤ 2 − 1 . Again, we adjust the cutting
so that each part will end at the end of a full encoding of some number in A. We denote
i
i
i
the resulting parts except the ﬁrst and last one by S2i = {S2,1
, S2,2
, ..., S2,2
i −1 }. Observe
S
S
i
i
i
i
i
i
that |S1 S2 | = O(2 ), the length of each part in S1 S2 is O(N/2 ), and the total length
of all parts is O(N ). We stop the process at level α log n in which we have O(nα ) parts in
S
i
O(nα /2i ) special characters σ ∗ . We place them similarly
S1 S2 . We add to each part Sj,k
to how we have done it in level 0. Speciﬁcally, we add 1 special character at positions
N/2i+2 + aN/(4nα ) for 1 ≤ a ≤ nα /2i , 2 special characters at positions N/2i+1 + aN/(4nα )
for 1 ≤ a ≤ nα /2i , and 3 special characters at positions 3N/2i+2 + aN/(4nα ) for 1 ≤ a <
nα /2i . After creating all these levels and parts we preprocess each of these parts as an
instance of histogram indexing. Then, given a a query Parikh vector v = (vσ1 , vσ2 , ..., vσℓ−1 )
that the sum of its counts is len, we ﬁrst ﬁnd the right level to handle it. This is the level i
for which we have N/2i+2 ≤ len < N/2i+1 . if len ≥ N/2 we use level 0 and if len < N/nα
we use the last level. Let the right level be level i. We ﬁrst extend v to contain a count for
i
σ ∗ and initialize it to the number of occurrences of σ ∗ in the substring Sj,k
[0, len − 1] (for
some j and k). We call this vector v 0 . We create a sequence of O(nα /2i ) query vectors v i
S
such that v i is created from v 0 by adding i to vσ0 ∗ . We now query each part in S1i S2i with
each vector from the set of vectors we have created. It is straightforward to observe that we
have O(nα ) queries in total and each query can match at most N/(4nα ) locations of some
S
part in S1i S2i .
Time analysis. Now, we analyse the preprocessing time and query time of our construction. Say we use encoding 1 to create S. The expected number of false-positives for
1
a query without the special character is O(N/R1− ℓ−1 ) (see Lemma 3). In Lemma 4 we
required that this number will be strictly less than 1/2 in order to guarantee that with high
probability we have no false positives for a given query (after ampliﬁcation). Following our
construction, we have O(nα ) queries (which is smaller than cnα for some constant c > 0) for
each query vector v ∈ Vk , so that each of these queries covers only some of the substrings of
S. Therefore, we can allow the number of false positives per vector v to be strictly less than
1/2cnα , which will be strictly less than 1/2 for each of the O(nα ) queries corresponding to
v. We can reduce the probability for a false positive per query by creating O(log n) copies
of our structure, each time using a diﬀerent hash function h. Then, for every query vector
v we query all O(log n) structures. This way, the probability that all of the queries return a
false positive is less than 1/poly(n). This is due to the fact that using diﬀerent h does not
change the order of the encoded numbers in the string S. It only changes their encoding.
Therefore, a query vector can match the exact same locations in all O(log n) structures.
1
That being said, we only need to ensure that (ℓR1/(ℓ−1) n)/R1− ℓ−1 < 1/2cnα . This
(ℓ−1)(1−α)

is satisﬁed if we choose R = c′ n ℓ−3
for some suﬃciently large constant c′ . By this
ℓ−2−α
choice of R we get that N = O(n ℓ−3 ). Our structure has O(log n) levels. The total
length of the string parts in each level is O(N ). Moreover, in each level we allow O(nα )
false positives in total. Therefore, the construction time is dominated by the preprocessing
time of level 0, as all levels have the same length and the preprocessing time is O(N β ) for
some β ≥ 1. We construct O(log n) copies of our structure, so the overall preprocessing
time is Õ(P (N, ℓ)) which is the preprocessing time for histogram indexing on input string

19

20

How Hard is it to Find (Honest) Witnesses?

of length N and alphabet size ℓ. We have n numbers in A and for each number xk in
A we have 2ℓ−2 queries (vectors in Vk ). These are the O(2ℓ n) queries we have in the
analysis in proof of Lemma 4. Using our special character we have created O(nα ) query
vectors for each of these O(2ℓ n) queries. Therefore, the total number of query vectors
is ,therefore, O(2ℓ n1+α ). Let Q(N, ℓ) be the query time for histogram indexing on input
string of length N and alphabet size ℓ. The total expected running time of our method
for solving 3SUM is Õ((P (N, ℓ) + n1+α Q(N, ℓ))) for constant alphabet size ℓ. Therefore,
unless the 3SUM conjecture is false, there is no solution for histogram indexing such that
P (N, ℓ) = O(n2−Ω(1) ) and Q(N, ℓ) = O(n1−α−Ω(1) ). If we plug-in the value of R we have
chosen, then we obtain that there is no solution for the histogram indexing problem with
(ℓ−3)(1−α)
2(ℓ−3)
P (N, ℓ) = O(N ℓ−2−α −Ω(1) ) and Q(N, ℓ) = O(N ℓ−2−α −Ω(1) ).
Improving the tradeoff. We get full tradeoﬀ between preprocessing time and query time
for each alphabet size ℓ. We wish that this tradeoﬀ will contain the points given by Lemma 4
when α gets close to zero. However, we have "wasted" one character for σ ∗ . We can bypass
this problem by encoding S using encoding 3 (see Appendix B). In this encoding we have a
special character σℓ−1 that separates between partial encodings. We can use this character
also as σ ∗ . In order to do so, we need to ensure that there will be no confusion between the
two uses of σℓ−1 . We call the characters σℓ−1 used for separating between partial encodings
separating characters and the characters σℓ−1 used as σ ∗ splitting characters. For a query
vector v we have vσℓ−1 = vσsep
+ vσspl
, where vσsep
is the number of separating characters
ℓ−1
ℓ−1
ℓ−1
counted by vσℓ−1 and vσspl
is
the
number
of
splitting
characters counted by vσℓ−1 . Recall
ℓ−1
that in our construction each part of S in each level has regions with 1, 2 or 3 special
characters σ ∗ . Instead of this amount of special characters, we place c∗ , 2c∗ or 3c∗ special
characters for some constant c∗ > 2. Now, for each query vector v we create the query
vectors vi ∈ V by adding each time c∗ to the count of σℓ−1 (that represents σ ∗ ). For a query
vector v the count of all the characters except σℓ−1 implies the number of full encoding
we have. Let v be a query vector for xk then the number of full encodings will be k − 1.
Therefore, if v matches a substring of some part of S, the separating characters in this
substring must be at least vσsep
− 2. Out of vσsep
the only two separating characters that
ℓ−1
ℓ−1
can be mistakenly considered as splitting characters are those between the partial encodings
of some xi and xj such that k = j − i. However, as splitting characters come in groups
of c∗ characters for c∗ > 2, we cannot mistakenly exchange two separating characters for
a complete group of splitting characters. Therefore, the only possibility for a confusion
between the two types is by v matching a substring that contains a partial group of splitting
characters. This can happen only at the suﬃx or preﬁx of the substring. Nevertheless, we
can prevent this possibility by adjusting the placement of the splitting characters to the end
of the full encoding in which they occur. That is, if a group of splitting characters occurs
inside the full encoding of some xi we move them to the end of its encoding in S.
Consequently, by the use of σℓ−1 as both separating and splitting character we can
get the same splitting eﬀect without the need for an additional character. If we redo the
running time calculations, but this time with S encoded using ℓ characters, we get that
unless the 3SUM conjecture is false, there is no solution for histogram indexing such that
(ℓ−2)(1−α)
2(ℓ−2)
P (N, ℓ) = O(N ℓ−1−α −Ω(1) ) and Q(N, ℓ) = O(N ℓ−1−α −Ω(1) ).
For encoding 3 we need at least 4 characters in the alphabet (at least two characters for
encoding a number, one for padding and another to separate between partial encodings) to
extend the result to ℓ = 3 we use encoding 2 (see Appendix B). In this encoding we have
1
σℓ−1 as a padding character. Speciﬁcally, for each number xi we add σℓ−1 (ℓ + 1)R ℓ−1 times
as padding. We can use σℓ−1 not just for padding, but also as our special character σ ∗ .

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat
1

Consequently, by choosing c∗ > 2(ℓ + 1)R ℓ−1 and following the same analysis as before we
prove that the same CLB holds also for alphabet of size 3 (note that the number of σℓ−1
characters we have added only increase the size of the string by some constant factor). ◭
References
1

2

3

4

5

6
7

8
9
10
11
12

13
14
15

16
17
18

Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In
International Colloquium on Automata, Languages and Programming, ICALP 2013, pages
1–12, 2013.
Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower
bounds for dynamic problems. In Foundations of Computer Science, FOCS 2014, pages
434–443, 2014.
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster
alignment of sequences. In International Colloquium on Automata, Languages and Programming, ICALP 2014, pages 39–51, 2014.
Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and
basing hardness on an extremely popular conjecture. In Symposium on Theory of Computing, STOC 2015, pages 41–50, 2015.
Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of
jumbled indexing. In International Colloquium on Automata, Languages and Programming,
ICALP 2014, pages 114–125, 2014.
Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3SUM. In
Workshop on Algorithms and Data Structures, WADS 2005, pages 409–421, 2005.
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeﬀ Erickson, Ferran Hurtado, John
Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions,
and X+Y. Algorithmica, 69(2):294–314, 2014.
Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Algorithms for
jumbled pattern matching in strings. Int. J. Found. Comput. Sci., 23(2):357–374, 2012.
Timothy Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics.
In Symposium on Theory of Computing, STOC 2015, pages 31–40, 2015.
Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Searching for jumbled patterns
in strings. In Prague Stringology Conference, pages 105–117, 2009.
Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard
matching. In Symposium on Theory of Computing, STOC 2002, pages 592–601, 2002.
Martin Dietzfelbinger. Universal hashing and k-wise independent random variables via
integer arithmetic without primes. In Symposium on Theoretical Aspects of Computer
Science, STACS 1996, pages 569–580, 1996.
Anka Gajentaan and Mark H. Overmars. On a class of O(n2 ) problems in computational
geometry. Comput. Geom., 5:165–185, 1995.
François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, pages 296–303, 2014.
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse
fourier transform. In Symposium on Theory of Computing Conference, STOC 2012, pages
563–578, 2012.
Danny Hermelin, Gad M. Landau, Yuri Rabinovich, and Oren Weimann. Binary jumbled
pattern matching via all-pairs shortest paths. CoRR, abs/1401.2065, 2014.
Allan Grønlund Jørgensen and Seth Pettie. Threesomes, degenerates, and love triangles.
In Foundations of Computer Science, FOCS 2014, pages 621–630, 2014.
Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Eﬃcient indexes for
jumbled pattern matching with constant-sized alphabet. In ESA, pages 625–636, 2013.

21

22

How Hard is it to Find (Honest) Witnesses?

19
20
21

22
23
24
25

Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Symposium on Discrete Algorithms, SODA 2016, pages 1272–1287, 2016.
Tanaeem M. Moosa and M. Sohel Rahman. Indexing permutations for binary strings. Inf.
Process. Lett., 110(18-19):795–798, 2010.
Tanaeem M. Moosa and M. Sohel Rahman. Sub-quadratic time and linear space data
structures for permutation matching in binary strings. J. Discrete Algorithms, 10:5–9,
2012.
S. Muthukrishnan. New results and open problems related to non-standard stringology. In
CPM 1995, pages 298–317, 1995.
Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Symposium
on Theory of Computing Conference, STOC 2010, pages 603–610, 2010.
Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on
Theory of Computing, STOC 2014, pages 664–673, 2014.
Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In
Symposium on Theory of Computing Conference, STOC 2012, pages 887–898, 2012.

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

23

Appendix
A

Appendix: Summary of Applications

Problem

Type

Preprocessing
Time

Query
Time

Reporting
Time

Remarks

Convolution
Witnesses

Reporting Ω(N 2−α )

Ω(N 1−α/2 )

Ω(N α/2−o(1) )

[Theorem 1]
0<α<1

Partial
Convolution

Decision

Ω(N 1−o(1) )

—

—

Decision

Ω(N 2−o(1) )

Ω(N 1−o(1) )

—

Partial
Decision
Matrix
Multiplication

Ω(N 2−o(1) )

—

—

Partial
Decision
Matrix
Multiplication
Indexing

Ω(SIZE(S))

Ω(N 2−o(1) )

—

[Theorem 2]
Sparse input:
#1 < N 1−Ω(1) ;
Sparse required
output:
|S| < N 1−Ω(1)
[Theorem 3]
Sparse input:
#1 < N 1−Ω(1) ;
Sparse required
output:
|S| < N 1−Ω(1)
[Theorem 4]
Sparse input:
#1 < N 2−Ω(1) ;
Sparse required
output:
|S| < N 2−Ω(1)
[Theorem 5]
Sparse input:
#1 < N 2−Ω(1) ;
Sparse required
output:
|Si | < N 2−Ω(1) ;
SIZE(S)
=
Pk
|Si |
i=1

Partial
Convolution
Indexing

Histogram
Reporting

Reporting Ω(N

Histogram
Indexing

Decision

2γ

2− ℓ+γ −o(1)

2(1−α)

)

Ω(N 2− ℓ−1−α −o(1) )

Ω(N

γ

1− ℓ+γ −o(1)

Ω(N 1−

)

1+α(ℓ−3)
−o(1)
ℓ−1−α

γℓ

Ω(N ℓ+γ

) —

2γ

− ℓ+γ −o(1)

) [Theorem 6]
alphabet size:
ℓ ≥ 2;
0<γ<ℓ

[Theorem 7]
alphabet size:
ℓ > 2;
0≤α≤1
Table 1 Summary of CLBs proved in this paper. In this table N is the size of vectors, strings
and the dimension of matrices. #1 refers to the number of ones in the input. The rows in this table
are interpreted to mean that there is no data structure that beats these preprocessing, query, and
reporting (if exists) complexities at the same time. For partial convolution and matrix multiplication
the CLB on the preprocessing time should be interpreted as a CLB on the total running time as
these are offline problems.

24

How Hard is it to Find (Honest) Witnesses?

Amir et al. [5]
2 −o(1)
2− ℓ−1

This Paper

CLB for preprocessing time

Ω(N

CLB for query time

Ω(N 1− ℓ−1 −o(1) )

Ω(N 1−

Hardness assumption

Strong 3SUM
conjecture
No

Standard 3SUM
conjecture
Yes

No

Yes

No

Yes

CLBs with full tradeoff between
preprocessing and query time for
every alphabet size.
Separation between binary alphabet and alphabet of size>2 for subquadratic preprocessing time and
Õ(1) query time.
CLBs for the reporting version of
histogram indexing.

1

)

Ω(N

2(1−α)

2− ℓ−1−α −o(1)

Remarks
)

1+α(ℓ−3)
−o(1)
ℓ−1−α

)

alphabet size:
ℓ > 2;
0≤α≤1
alphabet size:
ℓ > 2;
0≤α≤1

Table 2 Comparison of the results in [5] and this paper regarding histogram indexing. In this
table N is the size of the input string. In each column the first two rows in this table are interpreted
to mean that there is no data structure that beats these preprocessing and query complexities at
the same time.

I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat

B

25

Appendix: Other Encodings for Histogram Indexing

We describe two additional encodings of an instance of DiffConv3SUM to a string, which
then can be used to solve the instance using histogram reporting and histogram indexing.
Surprisingly, although these encodings have somewhat diﬀerent ﬂavour they all give the
same CLBs as encoding 1 given in Section 7.1.
Encoding 2. The idea behind this encoding is to use encoding 1 on alphabet of size ℓ−1
(instead of ℓ), and then use the additional character as a padding tool so that the lengths of
the partial encodings of each integer will be exactly ℓR1/(ℓ−1) . For each h(xi ) we ﬁrst create
both encℓ−1 (h(xi )) and encℓ−1 (h(xi )) as deﬁned in encoding 1. We denote by |enc| the length
1/(ℓ−1)
−|encℓ−1 (h(xi ))|
of some encoding enc. We ﬁrst encode h(xi ) by enc2ℓ (h(xi )) = (σℓ−1 )ℓR
·
ℓR1/(l−1) −|enc

(h(x ))|

i
ℓ−1
·encℓ−1 (h(xi )).
encℓ−1 (h(xi )). Then, we encode it by enc2ℓ(h(xi )) = σℓ−1
Finally, the full encoding, denoted by EN C2(h(xi )), is the concatenation of the two encodings.
Using this encoding we create a string S by concatenating EN C2(h(xk )) for all 1 ≤ k ≤
n. We also construct query pattern for each h(xk ), which is a Parikh vector vk such that the
rth element of this vector is p̄r,h(xk ) + R1/(ℓ−1) · (k − 1) for 0 ≤ r ≤ ℓ − 2. For r = ℓ − 1 the
value of the rth element will be ℓR1/(ℓ−1) − |encℓ−1 (h(xk ))| + ℓR1/(ℓ−1) − |encℓ−1 (h(xk ))| +
(ℓ + 1)R1/(ℓ−1) · (k − 1). We can also deﬁne a carry set Vk in an analog way to the carry set
deﬁned in Section 7.1. This set contains all 2ℓ−2 vectors obtained from vk in O(ℓ2ℓ ) time in
order to handle carry issues. It can be shown in a similar manner to Lemma 2 that if there
exist a pair xi , xj such that xk = xj − xi and k = j − i, then Si,j had some v ∈ Vk as its
Parikh vector.
Regarding the length of the encoded string S and the expected number of false-positives
induced by the reduction we have the following lemma:

◮ Lemma 5. The string S created by the reduction from DiffConv3SUM to histogram re1
porting using encoding 2 is of size N = O(ℓR ℓ−1 n). The number of expected false positives
when considering a query vector v ∈ Vk is O(N/R).
Proof. Each xk is embedded by the hash function h to a number in [R]. Then, it is divided
1
to ℓ − 1 parts (that represent h(xk ) in base R ℓ−1 ) each of them encoded by unary encoding.
1
Therefore, each of the encoded parts is of size at most R ℓ−1 , while the last letter of the
1
alphabet used for padding completes it exactly to R ℓ−1 . The same calculation is true to
both enc2ℓ (h(xi )) and enc2ℓ (h(xi )). That being said, the total length of the string using
1
encoding 2 is N = O(ℓR ℓ−1 n).
Now, we consider the expected number of false positives for some query vector v ∈ Vk .
In a similar manner to what we have shown for encoding 1 (see Lemma 3), we are interested
Vl−2
in the probability Pr[ j=0 (p̄j,h(xk ) = f (σj , i, m, k))], where f (σj , i, m, k) = f (σj , i, m) −
(k − 1)R1/(ℓ−1) (f (σj , i, m) represents the number of occurrences of σj in a substring of S
of length m starting at location i. f (σj , i, m, k) represents the same number without taking
into account the occurrences of σj in the k − 1 fully encoded integers in that substring). The
properties of the (almost) linear hash function guarantee that the value of h(xk ) is expected
to be uniformly distributed in its range. Therefore, we have Pr[p̄j,h(xk ) = f (σj , i, m, k)] =
Vl−2
1
1/R ℓ−1 . We conclude that Pr[ j=0 (p̄j,h(xk ) = f (σj , i, m, k))] ≈ 1/R as the number of
occurrences of all letters (except the one used for padding) is (almost) independently and
uniformly distributed. By this, we have that the expected number of false-positives for a
◭
query vector v ∈ Vk is O(N/R) .
We can plug N and the expected number of false-positives, which we have calculated in

26

How Hard is it to Find (Honest) Witnesses?

′

the previous lemma, in the proof of Theorem 6. Choosing R = nγ and ﬁnally substituting
γ ′ = γ(ℓ − 1)/ℓ we obtain the same CLBs that appear in Theorem 6. Moreover, the same
l
CLBs as in Lemma 4 can be achieved using this encoding, if we choose R to be c2 n ℓ−1 for
suﬃciently large constant c2 so the expected number of false positives we have is strictly
less than 1/2.
Encoding 3. In this encoding we ﬁrst create the same string S as in encoding 2 using
ℓ − 1 characters (instead of ℓ, and then add special characters to the string. We use σℓ−1 as
the special character (note that this time σℓ−1 was not used by encoding 2, as it make use
only of the ﬁrst ℓ − 1 characters in the alphabet). We add σℓ−1 at every position jℓR1/ℓ−1
in the string S for 0 ≤ j ≤ 2n. That is, we use σℓ−1 to mark the border of the partial
encodings of each number xi in the string created by encoding 2.
We construct a query for each h(xk ), which is a Parikh vector vk such that the rth
(0 ≤ r ≤ ℓ − 2) element of this vector is p̄r,h(xk ) + R1/(ℓ−2) · (k − 1). For r = ℓ − 2 the value of
the rth element will be (ℓ − 1)R1/(ℓ−2) − |encl−2 (h(xk ))| + (ℓ − 1)R1/(ℓ−2) − |encℓ−2 (h(xk ))| +
ℓR1/(ℓ−2) · (k − 1). Finally, for r = ℓ − 1 the value of the rth element will be 2k + 1. We
can also deﬁne a carry set Vk in an analog way to the carry set deﬁned in Section 7.1. This
set contains all 2ℓ−3 vectors obtained from vk in O(ℓ2ℓ ) time for handling carry issues. As
before, It can be shown that if there exist a pair xi , xj such that xk = xj − xi and k = j − i,
then Si,j had some v ∈ Vk as its Parikh vector.
Regarding the length of the encoded string S and the expected number of false-positives
induced by the reduction we have the following lemma:
◮ Lemma 6. The string S created by the reduction from DiffConv3SUM to histogram re1
porting using encoding 3 is of size N = O(ℓR ℓ−2 n). The number of expected false positives
when considering a query vector v ∈ Vk is O(n/R).
Proof. Each xi is embedded by the hash function h to a number in [R]. Then, it is divided
1
to ℓ − 2 parts (that represent h(xk ) in base R ℓ−2 ) each of them encoded by unary encoding.
1
Therefore, each of the encoded parts is of size at most R ℓ−2 , while σℓ−2 , that is used
1
for padding, completes each of them exactly to R ℓ−2 . The character σℓ−1 occurs only
O(n) times. That being said, the total length of the string using encoding 3 is of size
1
N = O(ℓR ℓ−2 n).
Now, we consider the expected number of false positives for some query vector v ∈
Vk . The use of the padding character σℓ−2 and the special character σℓ−1 guarantees that
every reported match starts exactly between enc2ℓ (h(xi )) and enc2ℓ (h(xi )) and ends exactly
between enc2ℓ (h(xj )) and enc2ℓ (h(xj )) for some i and j such that k = j − i. Therefore,
no false-positives are created by encodings errors. That being said, the expected number of
false-positives for a query vector v ∈ Vk is exactly the number of false-positives introduced
by the use of the hash function which is O(n/R).
◭
We can plug N and the expected number of false-positives, which we have calculated in
′′
the previous lemma, in the proof of Theorem 6. Choosing R = nγ and ﬁnally substituting
γ ′′ = γ(ℓ − 2)/ℓ we obtain the same CLBs that appear in Theorem 6. Moreover, the same
CLBs as in Lemma 4 can be achieved using this encoding, if we choose R to be c3 n for
suﬃciently large constant c3 so the expected number of false positives we have is strictly
less than 1/2.
We note that the encoding 2 requires one extra padding character and encoding 3 requires
another special character, so for them Theorem 6 and Lemma 4 hold from slightly larger ℓ.

