Conditional Lower Bounds for Space/Time Tradeoffs
Isaac Goldstein⋆1 , Tsvi Kopelowitz⋆⋆2 , Moshe Lewenstein⋆ ⋆ ⋆1 , and Ely Porat

arXiv:1706.05847v2 [] 25 Jul 2017

1

⋆ ⋆ ⋆1

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

Abstract. In recent years much effort has been concentrated towards achieving polynomial time lower
bounds on algorithms for solving various well-known problems. A useful technique for showing such
lower bounds is to prove them conditionally based on well-studied hardness assumptions such as 3SUM,
APSP, SETH, etc. This line of research helps to obtain a better understanding of the complexity inside
P.
A related question asks to prove conditional space lower bounds on data structures that are constructed
to solve certain algorithmic tasks after an initial preprocessing stage. This question received little
attention in previous research even though it has potential strong impact.
In this paper we address this question and show that surprisingly many of the well-studied hard problems
that are known to have conditional polynomial time lower bounds are also hard when concerning space.
This hardness is shown as a tradeoff between the space consumed by the data structure and the time
needed to answer queries. The tradeoff may be either smooth or admit one or more singularity points.
We reveal interesting connections between different space hardness conjectures and present matching
upper bounds. We also apply these hardness conjectures to both static and dynamic problems and
prove their conditional space hardness.
We believe that this novel framework of polynomial space conjectures can play an important role in
expressing polynomial space lower bounds of many important algorithmic problems. Moreover, it seems
that it can also help in achieving a better understanding of the hardness of their corresponding problems
in terms of time.

1

Introduction

1.1

Background

Lately there has been a concentrated effort to understand the time complexity within P, the class of
decision problems solvable by polynomial time algorithms. The main goal is to explain why certain
problems have time complexity that seems to be non-optimal. For example, all known efficient
algorithmic solutions for the 3SUM problem, where we seek to determine whether there are three
elements x, y, z in input set S of size n such that x + y + z = 0, take Õ(n2 ) time1 . However,
⋆

This research is supported by the Adams Foundation of the Israel Academy of Sciences and Humanities
Part of this work took place while the second author was at University of Michigan. This work is supported in
part by the Canada Research Chair for Algorithm Design, NSF grants CCF-1217338, CNS-1318294, and CCF-1514383
⋆⋆⋆
This work was partially supported by an ISF grant #1278/16
1
The Õ and Ω̃ notations suppress polylogarithmic factors
⋆⋆

the only real lower bound that we know is the trivial Ω(n). Likewise, we know how to solve the
all pairs shortest path, APSP, problem in Õ(n3 ) time but we cannot even determine whether it is
impossible to obtain an Õ(n2 ) time algorithm. One may note that it follows from the time-hierarchy
theorem that there exist problems in P with complexity Ω(nk ) for every fixed k. Nevertheless, such
a separation for natural practical problems seems to be hard to achieve.
The collaborated effort to understand the internals of P has been concentrated on identifying
some basic problems that are conjectured to be hard to solve more efficiently (by polynomial
factors) than their current known complexity. These problems serve as a basis to prove conditional
hardness of other problems by using reductions. The reductions are reminiscent of NP-complete
reductions but differ in that they are restricted to be of time complexity strictly smaller (by a
polynomial factor) than the problem that we are reducing to. Examples of such hard problems
include the well-known 3SUM problem, the fundamental APSP problem, (combinatorial) Boolean
matrix multiplication, etc. Recently, conditional time lower bounds have been proven based on
the conjectured hardness of these problems for graph algorithms [4,42], edit distance [13], longest
common subsequence (LCS) [3,15], dynamic algorithms [5,36], jumbled indexing [11], and many
other problems [1,2,6,7,14,25,31,34,40].
1.2

Motivation

In stark contrast to polynomial time lower bounds, little effort has been devoted to finding polynomial space conditional lower bounds. An example of a space lower bound appears in the work
of Cohen and Porat [19] and Pǎtraşcu and Roditty [38] where lower bounds are shown on the size
of a distance oracle for sparse graphs based on a conjecture about the best possible data structure
for a set intersection problem (which we call set disjointness in order to differ it from its reporting
variant).
A more general question is, for algorithmic problems, what conditional lower bounds of a
space/time tradeoff can be shown based on the set disjointness (intersection) conjecture? Even
more general is to discover what space/time tradeoffs can be achieved based on the other algorithmic problems that we assumed are hard (in the time sense)? Also, what are the relations between
these identified ”hard” problems in the space/time tradeoff sense? These are the questions which
form the basis and framework of this paper.
Throughout this paper we show connections between different hardness assumptions, show some
matching upper bounds and propose several conjectures based on this accumulated knowledge.
Moreover, we conjecture that there is a strong correlation between polynomial hardness in time
and space. We note that in order to discuss space it is often more natural to consider data structure
variants of problems and this is the approach we follow in this paper.
1.3

Our Results

Set Disjointness. In the SetDisjointness problem mentioned before, it is required to preprocess a
collection of m sets S1 , · · · , Sm ⊂ U , where U is the universe of elements and the total number of
elements in all sets is N . For a query, a pair of integers (i, j) (1 ≤ i, j ≤ m) is given and we are asked
whether Si ∩ Sj is empty or not. A folklore conjecture, which appears in [18,38], suggests that to
achieve a constant query time the space of the data structure constructed in the preprocessing stage
needs to be Ω̃(N 2 ). We call this conjecture the SetDisjointness conjecture. This conjecture does not
say anything about the case where we allow higher query time. Therefore, we suggest a stronger
2

conjecture which admits a full tradeoff between the space consumed by the data structure (denoted
by S) and the query time (denoted by T ). This is what we call the Strong SetDisjointness conjecture.
This conjecture states that for solving SetDisjointness with a query time T our data structure needs
Ω̃(N 2 /T 2 ) space. A matching upper bound exists for this problem by generalizing ideas from [18]
(see also [32]). Our new SetDisjointness conjecture can be used to admit more expressive space lower
bounds for a full tradeoff between space and query time.
3SUM Indexing. One of the basic and frequently used hardness conjectures is the celebrated 3SUM
conjecture. This conjecture was used for about 20 years to show many conditional time lower
bounds on various problems. However, we focus on what can be said about its space behavior. To
do this, it is natural to consider a data structure version of 3SUM which allows one to preprocess
the input set S. Then, the query is an external number z for which we need to answer whether
there are x, y ∈ S such that x + y = z. It was pointed out by Chan and Lewenstein [16] that all
known algorithms for 3SUM actually work within this model as well. We call this problem 3SUM
Indexing. On one hand, this problem can easily be solved using O(n2 ) space by sorting x + y for all
x, y ∈ S and then searching for z in Õ(1) time. On the other hand, by just sorting S we can answer
queries by a well-known linear time algorithm. The big question is whether we can obtain better
than Ω̃(n2 ) space while using just Õ(1) time query? Can it be done even if we allow Õ(n1−Ω(1) )
query time? This leads us to our two new hardness conjectures. The 3SUM-Indexing conjecture
states that when using Õ(1) query time we need Ω̃(n2 ) space to solve 3SUM-Indexing. In the Strong
3SUM-Indexing conjecture we say that even when using Õ(n1−Ω(1) ) query time we need Ω̃(n2 ) space
to solve 3SUM-Indexing.
3SUM Indexing and Set Disjointness. We prove connections between the SetDisjointness conjectures
and the 3SUM-Indexing conjectures. Specifically, we show that the Strong 3SUM-Indexing conjecture
implies the Strong SetDisjointness conjecture, while the SetDisjointness conjecture implies the 3SUMIndexing conjecture. This gives some evidence towards establishing the difficulty within the 3SUMIndexing conjectures. The usefulness of these conjectures should not be underestimated. As many
problems are known to be 3SUM-hard these new conjectures can play an important role in achieving
space lower bounds on their corresponding data structure variants. Moreover, it is interesting to
point on the difference between SetDisjointness which admits smooth tradeoff between space and
query time and 3SUM-Indexing which admits a big gap between the two trivial extremes. This may
explain why we are unable to show full equivalence between the hardness conjectures of the two
problems. Moreover, it can suggest a separation between problems with smooth space-time behavior
and others which have no such tradeoff but rather two ”far” extremes.
Generalizations. Following the discussion on the SetDisjointness and the 3SUM-Indexing conjectures
we investigate their generalizations.
I. k-Set Disjointness and (k+1)-SUM Indexing. The first generalization is a natural parametrization
of both problems. In the SetDisjointness problem we query about the emptiness of the intersection
between two sets, while in the 3SUM-Indexing problem we ask, given a query number z, whether two
numbers of the input S sum up to z. In the parameterized versions of these problems we are interested in the emptiness of the intersection between k sets and ask if k numbers sum up to a number
given as a query. These generalized variants are called k-SetDisjointness and (k+1)-SUM-Indexing
respectively. For each problem we give corresponding space lower bounds conjectures which generalize those of SetDisjointness and 3SUM-Indexing. These conjectures also have corresponding strong
3

variants which are accompanied by matching upper bounds. We prove that the k-SetDisjointness
conjecture implies (k+1)-SUM-Indexing conjecture via a novel method using linear equations.
II. k-Reachability. A second generalization is the problem we call k-Reachability. In this problem
we are given as an input a directed sparse graph G = (V, E) for preprocessing. Afterwards, for a
query, given as a pair of vertices u, v, we wish to return if there is a path from u to v consisting
of at most k edges. We provide an upper bound on this problem for every fixed k ≥ 1. The upper
bound admits a tradeoff between the space of the data structure (denoted by S) and the query
time (denoted by T ), which is ST 2/(k−1) = O(n2 ). We argue that this upper bound is tight. That
n2
). We call this conjecture
is, we conjecture that if query takes T time, the space must be Ω̃( T 2/(k−1)
the k-Reachability conjecture.
We give three indications towards the correctness of this conjecture. First, we prove that the
base case, where k = 2, is equivalent to the SetDisjointness problem. This is why this problem can
be thought of as a generalization of SetDisjointness.
Second, if we consider non-constant k then the smooth tradeoff surprisingly disappears and
n2
) eventually becomes Ω̃(n2 ). This means that to answer
we get ”extreme behavior” as Ω̃( T 2/(k−1)
reachability queries for non-constant path length, we can either store all answers in advance using
n2 space or simply answer queries from scratch using a standard graph traversal algorithm. The
general problem where the length of the path from u to v is unlimited in length is sometimes referred
to as the problem of constructing efficient reachability oracles. Pǎtraşcu in [37] leaves it as an open
question if a data structure with less than Ω̃(n2 ) space can answer reachability queries efficiently.
Moreover, Pǎtraşcu proved that for constant time query, truly superlinear space is needed. Our kReachability conjecture points to this direction, while admitting full space-time tradeoff for constant
k.
The third indication for the correctness of the k-Reachability conjecture comes from a connection
to distance oracles. A distance oracle is a data structure that can be used to quickly answer queries
about the shortest path between two given nodes in a preprocessed undirected graph. As mentioned
above, the SetDisjointness conjecture was used to exclude some possible tradeoffs for sparse graphs.
Specifically, Cohen and Porat [19] showed that obtaining an approximation ratio smaller than 2
with constant query time requires Ω̃(n2 ) space. Using a somewhat stronger conjecture Pǎtraşcu
and Roditty [38] showed that a (2,1)-distance oracle for unweighted graphs with m = O(n) edges
requires Ω̃(n1.5 ) space. Later, this result was strengthened by Pǎtraşcu et al. [39]. However, these
results do not exclude the possibility of compact distance oracles if we allow higher query time.
For stretch-2 and stretch-3 in sparse graphs, Agarwal et. al. [9,10] achieved a space-time tradeoff
of S × T = O(n2 ) and S × T 2 = O(n2 ), respectively. Agarwal [8] also showed many other results
for stretch-2 and below. We use our k-Reachability conjecture to prove that for stretch-less-than(1+2/k) distance oracles S × T 2/(k−1) is bounded by Ω̃(n2 ). This result is interesting in light of
Agarwal [8] where a stretch-(5/3) oracle was presented which achieves a space-time tradeoff of
S × T = O(n2 ). This matches our lower bound, where k = 3, if our lower bound would hold not
only for stretch-less-than-(5/3) but also for stretch-(5/3) oracles. Consequently, we see that there
is strong evidence for the correctness of the k-Reachability conjecture.
Moreover, these observations show that on one hand k-Reachability is a generalization of SetDisjointness which is closely related to 3SUM-Indexing. On the other hand, k-Reachability is related
to distance oracles which solve the famous APSP problem using smaller space by sacrificing the
accuracy of the distance between the vertices. Therefore, the k-Reachability conjecture seems as a
4

conjecture corresponding to the APSP hardness conjecture, while also admitting some connection
with the celebrated 3SUM hardness conjecture.
SETH and Orthogonal Vectors. After considering space variants of the 3SUM and APSP conjectures
it is natural to consider space variants for the Strong Exponential Time Hypothesis (SETH) and the
closely related conjecture of orthogonal vectors. SETH asserts that for any ǫ > 0 there is an integer
k > 3 such that k-SAT cannot be solved in 2(1−ǫ)n time. The orthogonal vectors time conjecture
states that there is no algorithm that for every c ≥ 1, finds if there are at least two orthogonal
vectors in a set of n Boolean vectors of length c log n in Õ(n2−Ω(1) ) time. We discuss the space
variants of these conjectures in Section 7. However, we are unable to connect these conjectures and
the previous ones. This is perhaps not surprising as the connection between SETH and the other
conjectures even in the time perspective is very loose (see, for example, discussions in [5,25]).
Boolean Matrix Multiplication. Another problem which receives a lot of attention in the context
of conditional time lower bounds is calculating Boolean Matrix Multiplication (BMM). We give a
data structure variant of this well-known problem. We then demonstrate the connection between
this problem and the problems of SetDisjointness and k-Reachability.
Applications. Finally, armed with the space variants of many well-known conditional time lower
bounds, we apply this conditional space lower bounds to some static and dynamic problems. This
gives interesting space lower bound results on these important problems which sometimes also
admits clear space-time tradeoff. We believe that this is just a glimpse of space lower bounds that
can be achieved based on our new framework and that many other interesting results are expected
to follow this promising route.
Figure 1 in Appendix A presents a sketch of the results in this paper.

2

Set Intersection Hardness Conjectures

We first give formal definitions of the SetDisjointness problem and its enumeration variant:
Problem 1 (SetDisjointness
Problem). Preprocess a family F of m sets, all from universe U , with
P
total size N = S∈F |S| so that given two query sets S, S ′ ∈ F one can determine if S ∩ S ′ = ∅.
Problem 2 (SetIntersection
Problem). Preprocess a family F of m sets, all from universe U , with
P
total size N = S∈F |S| so that given two query sets S, S ′ ∈ F one can enumerate the set S ∩ S ′ .
Conjectures. The SetDisjointness problem was regarded as a problem that admits space hardness.
The hardness conjecture of the SetDisjointness problem has received several closely related formulations. One such formulation, given by Pǎtraşcu and Roditty [38], is as follows:
Conjecture 1. SetDisjointness Conjecture [Formulation 1]. Any data structure for the SetDisjointness problem where |U | = logc m for a large enough constant c and with a constant query time
must use Ω̃(m2 ) space.
Another formulation is implicitly suggested in Cohen and Porat [18]:
5

Conjecture 2. SetDisjointness Conjecture [Formulation 2]. Any data structure for the SetDisjointness problem with constant query time must use Ω̃(N 2 ) space.
There is an important distinction between the two formulations, which is related to the sparsity
of SetDisjointness instances. This distinction follows from the following upper bound: store an m×m
matrix of the answers to all possible queries, and then queries will cost constant time. The first
formulation of the SetDisjointness conjecture states that if we want constant (or poly-logaritmic)
query time, then this is the best we can do. At a first glance this makes the second formulation,
whose bounds are in terms of N and not m, look rather weak. In particular, why would we ever be
interested in a data structure that uses O(N 2 ) space when we can use one with O(m2 ) space? The
answer is that the two conjectures are the same if the sets are very sparse, and so at least in terms
of N , if one were to require a constant query time then by the second formulation the space must
be at least Ω(N 2 ) (which happens in the very sparse case).
Nevertheless, we present a more general conjecture, which in particular captures a tradeoff curve
between the space usage and query time. This formulation captures the difficulty that is commonly
believed to arise from the SetDisjointness problem, and matches the upper bounds of Cohen and
Porat [18] (see also [32]).
Conjecture 3. Strong SetDisjointness Conjecture. Any data structure for the SetDisjointness
2
) space.
problem that answers queries in T time must use S = Ω̃( N
T2
For example, a natural question to ask is “what is the smallest query time possible with linear space?”. This question is addressed, at least from a lower bound perspective, by the Strong
SetDisjointness conjecture.
Conjecture 4. Strong SetIntersection Conjecture. Any data structure for the SetIntersection
problem that answers queries in O(T + op) time, where op is the size of the output of the query,
2
must use S = Ω̃( NT ) space.

3

3SUM-Indexing Hardness Conjectures

In the classic 3SUM problem we are given an integer array A of size n and we wish to decide
whether there are 3 distinct integers in A which sum up to zero. Gajentaan and Overmars [23]
showed that an equivalent formulation of this problem receives 3 integer arrays A1 , A2 , and A3 ,
each of size n, and the goal is to decide if there is a triplet x1 ∈ A1 , x2 ∈ A2 , and x3 ∈ A3 that sum
up to zero.
We consider the data structure variant of this problem which is formally defined as follows:
Problem 3 (3SUM-Indexing Problem). Preprocess two integer arrays A1 and A2 , each of length n,
so that given a query integer z we can decide whether there are x ∈ A1 and y ∈ A2 such that
z = x + y.
It is straightforward to maintain all possible O(n2 ) sums of pairs in quadratic space, and then
answer a query in Õ(1) time. On the other extreme, if one does not wish to utilize more than linear
space then one can sort the arrays separately during preprocssing time, and then a query can be
answered in Õ(n) time by scanning both of the sorted arrays in parallel and in opposite directions.
We introduce two conjectures with regards to the 3SUM-Indexing problem, which serve as natural
candidates for proving polynomial space lower bounds.
6

Conjecture 5. 3SUM-Indexing Conjecture: There is no solution for the 3SUM-Indexing problem
with truly subquadratic space and Õ(1) query time.
Conjecture 6. Strong 3SUM-Indexing Conjecture: There is no solution for the 3SUM-Indexing
problem with truly subquadratic space and truly sublinear query time.
Notice that one can solve the classic 3SUM problem using a data structure for 3SUM-Indexing
by preprocessing A1 and A2 , and answering n 3SUM-Indexing queries on all of the values in A3 .
Next, we prove theorems that show tight connections between the 3SUM-Indexing conjectures
and the SetDisjointness conjectures. We note that the proofs of the first two theorems are similar
to the proofs of [31], but with space interpretation.
Theorem 1. The Strong 3SUM-Indexing Conjecture implies the Strong SetDisjointness Conjecture.
Proof. A family H of hash functions from [u] → [m] is called linear if for any h ∈ H and any x, x′ ∈
[u], h(x) + h(x′ ) = h(x + x′ ) + ch (mod m), where ch is some integer that depends only on h. H is
called almost linear if for any h ∈ H and any x, x′ ∈ [u], either h(x)+h(x′ ) = h(x+x′ )+ch (mod m),
or h(x) + h(x′ ) = h(x + x′ ) + ch + 1 (mod m).
Given a hash function h ∈ H we say that a value i ∈ m is heavy for set S = {x1 , . . . , xn } ⊂ [u]
if |{x ∈ S : h(x) = i}| > 3n
m . H is called almost balanced if for any set S = {x1 , . . . , xn } ⊂ [u], the
expected number of elements from S that are hashed to heavy values is O(m). Kopelowitz et al.
showed in [31] that a family of hash functions obtained from the construction of Dietzfelbinger [20]
is almost-linear, almost-balanced, and pair-wise independent. In order to reduce clutter in the proof
here we assume the existence of linear, almost-balanced, and pair-wise independent families of hash
functions. Using the family of hash functions of Dietzfelbinger [20] will only affect multiplicative
constants.
We reduce an instance of the 3SUM-Indexing problem to an instance of the SetDisjointness
γ
2
problem as follows. Let R =
√ n for some constant 0 < γ < 1. Let Q = (5n/R) . Without loss of
generality we assume that Q is an integer. We pick a random hash function h1 : U → [R] from
a family that is linear and almost-balanced. Using h1 we create R buckets B1 , . . . , BR such that
Bi = {x ∈ A1 : h1 (x) = i}, and another R buckets C1 , . . . , CR such that Ci = {x ∈ A2 : h1 (x) = i}.
Since h1 is almost-balanced, the expected number of elements from A1 and A2 that are mapped
to buckets of size greater than 3n/R is O(R). We use O(R) space to maintain this list explicitly,
together with a lookup table for the elements in A1 and A2 .
Next, we pick a random hash function h2 : U → [Q] where
h2 is chosen from a pair-wise
√
Q
shifted
sets as follows: for each
independent
and
linear
family.
For
each
bucket
we
create
√
√
0 ≤ j < Q let Bi,j = {h2 (x) − j · Q (mod Q) | x ∈ Bi } and Ci,j = {−h2 (x) + j (mod Q) | x ∈ Ci }.
These sets are all preprocessed into a data structure for the SetDisjointness problem.
Next, we answer a 3SUM-Indexing query z by utilizing the linearity of h1 and h2 , which implies
that if there exist x ∈ A1 and y ∈ A2 such that x + y = z then h1 (x) + h1 (y) = h1 (z) + ch1 (mod R)
and h2 (x) + h2 (y) = h2 (z) + ch2 (mod Q).
Thus, if x ∈ Bi then y must be in Ch1 (z)+ch1 −i(mod R) . For each i ∈ [R] we would like to inin order to find candidate pairs of x and y. Denote by h↑2 (z) =
√
h2 (z)+c
⌊ √Q h1 ⌋ and h↓2 (z) = h2 (z) + ch2 (mod Q). Due to the almost-linearity of h2 , if the sets Bi and
Ch1 (z)+ch −i(mod R) + z are not disjoint then the sets Bi,h↑ (z) and Ch1 (z)+c −i(mod R),h↓ (z) are not dis-

tersect Bi with Ch1 (z)+ch

1

−i(mod R)

1

2

joint (but the reverse is not necessarily true). Thus, if Bi,h↑ (z) ∩Ch1 (z)+c
2

7

h1

2

↓
h1 −i(mod R),h2 (z)

= ∅ then there

is no candidate pair in Bi and Ch1 (z)+ch −i(mod R) +z. However, if Bi,h↑ (z) ∩Ch1 (z)+c −i(mod R),h↓ (z) 6= ∅
1
h1
2
2
then it is possible that this is due to a 3SUM-Indexing solution, but we may have false positives.
Notice that the number of set pairs whose intersection we need to examine is O(R) since z is given.
Once we pick i (R choices) the rest is implicit.
Set z and let k = h2 (z). Since h2 is pair-wise independent and linear then for any pair x, y ∈ U
where x 6= y we have that if x + y 6= z then Pr[h2 (x) + h2 (y) = k + ch2 (mod R)] = Pr[h2 (x + y) =
h2 (z) + ch2 (mod R)] = Q1 . Since each bucket contains at most 3n/R elements, the probability of a
9
21
false positive due to two buckets Bi and Cj is not greater than ( 3n
R ) Q = 25 . In order to reduce
the probability of a false positive to be polynomially small, we repeat the process with O(log n)
different choices of h2 functions (but using the same h1 ). This blows up the number of sets by a
factor of O(log n), but not the universe. If the sets intersect under all O(log n) choices of h2 then we
can spend O(n/R) time to find x and y within buckets Bi and Cj , which are either a 3SUM-Indexing
solution (and the algorithm halts), or a false positive,
which only occurs with probability 1/poly(n).
√
To summarize, we create a total of O(R Q log n) sets, each of size at most 3n/R. Thus, the
total size of the SetDisjointness instance is N = Õ(n2 /R). For a query, we perform Õ(R) queries on
n
1
the SetDisjointness structure, and spend another O(R · R
· poly(n)
) = O(1) expected time to verify
that we did not hit a false positive. Furthermore, we spend O(R) time to check possible solutions
containing one of the expected O(R) elements from buckets with too many elements by using the
lookup tables. If we denote by T (N ) and S(N ) the query time and space usage, respectively, of the
SetDisjointness data structure on N elements (in our case N = Õ(n2−γ )), then the query time of the
reduction becomes t3SI = Õ(R · T (n2 /R)) time and the space usage is s3SI = Õ(S(n2 /R) + O(n)).
Since we may assume that S(N ) = Ω(N ), we have that s3SI = Õ(S(N )).
By the Strong 3SUM-Indexing Conjecture, either s3SI = Ω̃(n2 ) or t3SI = Ω̃(n), which means that
2

1−γ

either S(N ) = Ω̃(N 2−γ ) or T (N ) = Ω̃(N 2−γ ). For any constant ǫ > 0, if the SetDisjointness data
2

2

2−2γ

structure uses Θ̃(N 2−γ −ǫ ) space, then S(N ) · (T (N ))2 = Ω̃(N 2−γ −ǫ+ 2−γ ) = Ω̃(N 2−ǫ ). Since this
holds for any ǫ > 0 it must be that S(N ) · (T (N ))2 = Ω̃(N 2 ).
⊔
⊓
Theorem 2. The Strong 3SUM-Indexing Conjecture implies the Strong SetIntersection Conjecture.
Proof. The proof follows the same structure as the proof of Theorem 1, but here we set Q =
(n1+δ /R), where δ > 0 is a constant. Furthermore, we preprocess the buckets using a SetIntersection
data structure, and if two sets intersect then instead of repeating the whole process with different
choices of h2 (in order to reduce the probability of a false positive), we use the SetIntersection data
structure to report all of the elements in an intersection, and verify them all directly.
As before, set z and let k = h2 (z). Since h2 is pair-wise independent and linear then for any
pair x, y ∈ U where x 6= y we have that if x + y 6= z then Pr[h2 (x) + h2 (y) = k + ch2 (mod R)] =
Pr[h2 (x + y) = h2 (z) + ch2 (mod R)] = Q1 . We now bound the expected output size from all of the
2
intersections. Since each pair of buckets imply at most ( 3n
R ) pairs of elements, the expected size
n1−δ
21
of their intersection is E[|h2 (Bi ) − k ∩ h2 (Cj )|] = ( 3n
R ) Q = O( R ). Thus, the expected size of the
n
1−δ ). For each pair in an intersection we
output of all of the O(R) intersections is O(R Rn
δ ) = O(n
can verify in constant time if together with z√they form a solution.
To summarize, we create a total of O(R Q) sets, each of size at most 3n/R. Thus, the total
size of the SetIntersection instance is N = Õ(n2 /R). For a query, we perform Õ(R) queries on the
SetIntersection structure. Furthermore, we spend O(R) time to check possible solutions containing
one of the expected O(R) elements from buckets with too many elements by using the lookup tables.
8

If we denote by T (N ) and S(N ) the query time and space usage, respectively, of the SetIntersection
√
3+δ−γ
data structure on N elements (in our case N = Õ(R Qn/R) = Õ(n 2 )), then the query time of
the reduction becomes t3SI = Õ(R·T (N )+n1−δ ) time and the space usage is s3SI = Õ(S(N )+O(n)).
Since we may assume that S(N ) = Ω(N ), we have that s3SI = Õ(S(N )).
By the Strong 3SUM-Indexing conjecture, either s3SI = Ω̃(n2 ) or t3SI = Ω̃(n), which means that
2−2γ

4

either S(N ) = Ω̃(N 3+δ−γ ) or T (N ) = Ω̃(N 3+δ−γ ). For any constant ǫ > 0, if the SetIntersection
4

4

2−2γ

2δ

data structure uses Θ̃(N 3+δ−γ −ǫ ) space, then S(N )·T (N ) = Ω̃(N 3+δ−γ −ǫ+ 3+δ−γ ) = Ω̃(N 2− 3+δ−γ −ǫ ).
Since this holds for any ǫ > 0 and any δ > 0 it must be that S(N ) · T (N ) = Ω̃(N 2 ).
⊔
⊓
Theorem 3. The SetDisjointness Conjecture implies the 3SUM-Indexing Conjecture.
Proof. Given an instance of SetDisjointness, we construct an instance of 3SUM-Indexing as follows.
Denote with M the value of the largest element in the SetDisjointness instance. Notice that we may
assume that M ≤ N (otherwise we can use a straightforward renaming). For every element x ∈ U
that is contained in at least one of the sets we create two integers xA and xB , which are represented
by 2⌈log m⌉ + ⌈log N ⌉ + 3 bits each (recall that m is the number of sets).
The ⌈log N ⌉ least significant bits in xA represent the value of x. The following bit is a zero.
The following ⌈log m⌉ bits in xA represent the index of the set containing x, and the rest of the
2 + ⌈log m⌉ are all set to zero. The ⌈log N ⌉ least significant bits in xB represent the value of M − x.
The following 2 + ⌈log m⌉ are all set to zero. The following ⌈log m⌉ bits in xB represent the index
of the set containing x, and the last bit is set to zero. Finally, the integer xA is added to A1 of the
3SUM-Indexing instance, while the integer xB is added to A2 .
We have created two sets of n ≤ M integers. We then preprocess them to answer 3SUM-Indexing
queries. Now, to answer a SetDisjointness query on sets Si and Sj , we query the 3SUM-Indexing data
structure with an integer z which is determined as follows. The ⌈log N ⌉ least significant bits in z
represent the value of M . The following bit is a zero. The following ⌈log m⌉ bits represent the index
i and are followed by a zero. The next ⌈log m⌉ bits represent the index j and the last bit is set to
zero.
It is straightforward to verify that there exists a solution to the 3SUM-Indexing problem on z
if and only if the sets Si and Sj are not disjoint. Therefore, if there is a solution to the 3SUMIndexing problem with less than Ω̃(n2 ) space and constant query time then there is a solution for
the SetDisjointness problem which refutes the SetDisjointness Conjecture.
⊔
⊓

4

Parameterized Generalization:
k-Set Intersection and (k+1)-SUM

Two parameterized generalizations of the SetDisjointness and 3SUM-Indexing problems are formally
defined as follows:
Problem 4 (k-SetDisjointness
Problem). Preprocess a family F of m sets, all from universe U , with
P
total size N = S∈F |S| so that given k query sets S1 , S2 , . . . , Sk ∈ F one can quickly determine if
∩ki=1 Si = ∅.
Problem 5 ((k+1)-SUM-Indexing Problem). Preprocess k integer arrays A1 , A2 , . . . , Ak , each of length
n, soPthat given a query integer z we can decide if there is x1 ∈ A1 , x2 ∈ A2 , . . . , xk ∈ Ak such that
z = ki=1 xi .
9

It turn out that a natural generalization of the data structure of Cohen and Porat [18] leads to
a data structure for k-SetDisjointness as shown in the following lemma.
Lemma 1. There exists a data structure for the k-SetDisjointness problem where the query time is
T and the space usage is S = O((N/T )k ).
Proof. We call the f largest sets in F large sets. The rest of the sets are called small sets. In
the preprocessing stage we explicitly maintain a k-dimensional table with the answers for all kSetDisjointness queries where all k sets are large sets. The space needed for such a table is S = f k .
Moreover, for each set (large or small) we maintain a look-up table that supports disjointness queries
(with this set) in constant time. Since there are f large sets and the total number of elements is
N , the size of each of the small sets is at most N/f .
Given a k-SetDisjointness query, if all of the query sets are large then we look up the answer
in the k-dimensional table. If at least one of the sets is small then using a brute-force search we
look-up each of the at most O(N/f ) elements in each of the other k − 1 sets. Thus, the total query
time is bounded by O(kN/f ), and the space usage is S = O(f k ). The rest follows.
⊔
⊓
Notice that for the case of k = 2 in Lemma 1 we obtain the same tradeoff of Cohen and Porat [18]
for SetDisjointness. The following conjecture suggests that the upper bound of Lemma 1 is the best
possible.
Conjecture 7. Strong k-SetDisjointness Conjecture. Any data structure for the k-SetDisjointness
k
) space.
problem that answers queries in T time must use S = Ω̃( N
Tk
Similarly, a natural generalization of the Strong 3SUM-Indexing conjecture is the following.
Conjecture 8. Strong (k+1)-SUM-Indexing Conjecture. There is no solution for the (k+1)SUM-Indexing problem with Õ(nk−Ω(1) ) space and truly sublinear query time.
We also consider some weaker conjectures, similar to the SetDisjointness and 3SUM-Indexing
conjectures.
Conjecture 9. k-SetDisjointness Conjecture. Any data structure for the k-SetDisjointness problem
that answers queries in constant time must use Ω̃(N k ) space.
Conjecture 10. (k+1)-SUM-Indexing Conjecture. There is no solution for the (k+1)-SUM-Indexing
problem with Õ(nk−Ω(1) ) space and constant query time.
Similar to Theorem 3, we prove the following relationship between the k-SetDisjointness conjecture and the (k+1)-SUM-Indexing conjecture.
Theorem 4. The k-SetDisjointness conjecture implies the (k+1)-SUM-Indexing conjecture
Proof. Given an instance of k-SetDisjointness, we construct an instance of (k+1)-SUM-Indexing as
follows. Denote by M the value of the largest element in the SetDisjointness instance. Notice that
we may assume that M ≤ N (otherwise we use a straightforward renaming). For every element
x ∈ U that is contained in at least one of the sets we create k integers x1 , x2 , ..., xk , where each
integer is represented by k⌈log m⌉ + (k − 1)⌈log N ⌉ + 2k − 1 bits.
For integer xi , if i > 1 the (k − 1)⌈log N ⌉ + k − 1 least significant bits are all set to zero, except
for the bits in indices (i − 2)(⌈log N ⌉ + 1) + 1, ..., (i − 1)(⌈log N ⌉ + 1) that represent the value of
10

x. If i = 1 the value of the bits in the indices (j − 1)(⌈log N ⌉ + 1) + 1, ..., j(⌈log N ⌉ + 1) is set to
M − x for all 1 ≤ j ≤ k − 1. The k⌈log m⌉ + k following bits are all set to zero, except for the bits
in indices (i − 1)(⌈log m⌉ + 1) + 1, ..., i(⌈log m⌉ + 1) which represent the index of the set containing
x.
We now create an instance of (k+1)-SUM-Indexing where the jth input array Aj is the set
of integers xj for all x ∈ U that is contained in at least one set of our family. Thus, the size
of each array is at most N . Now, given a k-SetDisjointness query (i1 , i2 , ..., ik ) we must decide if
Si1 ∩ Si2 ∩ ... ∩ Sik = ∅. To answer this query we will query the instance of (k+1)-SUM-Indexing we
have created with an integer z whose binary representation is as follows: In the (k −1)⌈log N ⌉+k −1
least significant bits the value of the bits in the indices (j − 1)(⌈log N ⌉ + 1) + 1, ..., j(⌈log N ⌉ + 1)
is set to M for all 1 ≤ j ≤ k − 1. In the k⌈log m⌉ + k following bits, the bits at locations (j −
1)(⌈log m⌉ + 1) + 1, ..., j(⌈log m⌉ + 1) represent ij (for 1 ≤ j ≤ k). The rest of the bits are padding
zero bits (in between representations of various ij s and M s).
If Si1 ∩ Si2 ∩ ... ∩ Sik 6= ∅ then by our construction it is straightforward to verify that the (k+1)SUM-Indexing query on z will return that there is a solution. If Si1 ∩ Si2 ∩ ... ∩ Sik = ∅ then at least
for one j ∈ [k − 1] the sum of values in the bits in indices (j − 1)(⌈log N ⌉ + 1) + 1, ..., j(⌈log N ⌉ + 1)
in the (k − 1)⌈log N ⌉ + k − 1 least significant bits will not be M . This is because we can view
each block of ⌈log N ⌉ + 1 bits in the (k − 1)⌈log N ⌉ + k − 1 least significant bits as solving a linear
equation. This equation is of the form M − x1 + xi = M for every block i − 1 where 2 ≤ i ≤ k.
The solution of each of these equations is x1 = xi for all 2 ≤ i ≤ k. Consequently, a solution can be
found only if there is a specific x which is contained in all of the k sets. Therefore, we get a correct
answer to a k-SetDisjointness query by answering a (k+1)-SUM-Indexing query.
Consequently, if for some specific constant k there is a solution to the (k+1)-SUM-Indexing
problem with less than Ω̃(nk ) space and constant query time, then with this reduction we refute
the k-SetDisjointness conjecture.
⊔
⊓

5

Directed Reachability Oracles as a Generalization of Set Disjointness
Conjecture

An open question which was stated by Pǎtraşcu in [37] asks if it is possible to preprocess a sparse
directed graph in less than Ω(n2 ) space so that Reachability queries (given two query vertices u
and v decide whether there is a path from u to v or not) can be answered efficiently. A partial
answer, given in [37], states that for constant query time truly superlinear space is necessary. In
the undirected case the question is trivial and one can answer queries in constant time using linear
space. This is also possible for planar directed graphs (see Holm et al. [27]).
We now show that Reachability oracles for sparse graphs can serve as a generalization of the
SetDisjointness conjecture. We define the following parameterized version of Reachability. In the
k-Reachability problem the goal is to preprocess a directed sparse graph G = (V, E) so that given
a pair of distinct vertices u, v ∈ V one can quickly answer whether there is a path from u to v
consisting of at most k edges. We prove that 2-Reachability and SetDisjointness are tightly connected.
Lemma 2. There is a linear time reduction from SetDisjointness to 2-Reachability and vice versa
which preserves the size of the instance.
Proof. Given a graph G = (V, E) as an instance for 2-Reachability, we construct a corresponding
instance of SetDisjointness as follows. For each vertex v we create the sets Vin = {u|(u, v) ∈ E} and
11

Vout = {u|(v, u) ∈ E} ∪ {v}. We have 2n sets and 2m + n elements in all of them (|V | = n and
|E| = m). Now, a query u, v is reduced to determining if the sets Uout and Vin are disjoint or not.
Notice, that the construction is done in linear time and preserves the size of the instance. In the
opposite direction, we are given m sets S1 , S2 , ..., Sm having N elements in total e1 , e2 , ..., eN . We
can create an instance of 2-Reachability in the following way. For each set Si we create a vertex vi .
Moreover, for each element ej we create a vertex uj . Then, for each element ej in a set si we create
two directed edges (vi , uj ) and (uj , vi ). These vertices and edges define a directed graph, which is
preprocessed for 2-Reachability queries. It is straightforward to verify that the disjointness of Si and
Sj is equivalent to determining if there is a path of length at most 2 edges from vi to vj . Moreover,
the construction is done in linear time and preserves the size of the instance.
⊔
⊓
Furthermore, we consider k-Reachability for k ≥ 3. First we show an upper bound on the tradeoff
between space and query time for solving k-Reachability.
Lemma 3. There exists a data structure for k-Reachability with S space and T query time such
that ST 2/(k−1) = O(n2 ).
Proof. Let α > 0 be an integer parameter to be set later. Given a directed graph G = (V, E), we
call vertex v ∈ V a heavy vertex if deg(v) > α and a vertex u ∈ V a light vertex if deg(u) ≤ α.
Notice that the number of heavy vertices is at most n/α. For all heavy vertices in V we maintain
a matrix containing the answers to any k-Reachability query between two heavy vertices. This uses
O(n2 /α2 ) space.
Next, we recursively construct a data structure for (k-1)-Reachability. Given a query u, v, if both
vertices are heavy then the answer is obtained from the matrix. Otherwise, either u or v is light
vertex. Without loss of generality, say u is a light vertex. We consider each vertex w ∈ Nout (u)
(Nout (u) = {v|(u, v) ∈ E}) and query the (k-1)-Reachability data structure with the pair w, v. Since
u is a light node, there are no more than α queries. One of the queries returns a positive answer if
and only if there exists a path of length at most k from u to v.
Denote by S(k, n) the space used by our k-Reachability oracle on a graph with n vertices and
denote by Q(k, n) the corresponding query time. In our construction we have S(k, n) = n2 /α2 +
S(k − 1, n) and Q(k, n) = αQ(k − 1, n) + O(1). For k = 1 it is easy to construct a linear space data
structure using hashing so that queries can be answered in constant time. Thus, S = S(k, n) =
O((k − 1)n2 /α2 ) and T = Q(k, n) = O(αk−1 ).
⊔
⊓
Notice that for the case of k = 2 the upper bounds from Lemma 3 exactly match the tradeoff of
the Strong SetDisjointness Conjecture (ST 2 = Õ(n2 )). We expand this conjecture by considering the
tightness of our upper bound for k-Reachability, which then leads to some interesting consequences
with regard to distance oracles.
Conjecture 11. Directed k-Reachability Conjecture. Any data structure for the k-Reachability
n2
) space.
problem with query time T must use S = Ω̃( T 2/(k−1)
Notice that when k is non-constant then by our upper bound Ω̃(n2 ) space is necessary independent of the query time. This fits nicely with what is currently known about the general question
of Reachability oracles: either we spend n2 space and answer queries in constant time or we do no
preprocessing and then answer queries in linear time. This leads to the following conjecture.
Conjecture 12. Directed Reachability Hypothesis. Any data structure for the Reachability
problem must either use Ω̃(n2 ) space, or linear query time.
12

The conjecture states that in the general case of Reachability there is no full tradeoff between
space and query time. We believe the conjecture is true even if the path is limited to lengths of
some non-constant number of edges.

6

Distance Oracles and Directed Reachability

There are known lower bounds for constant query time distance oracles based on the SetDisjointness
hypothesis. Specifically, Cohen and Porat [18] showed that stretch-less-than-2 oracles need Ω(n2 )
space for constant queries. Patrascu et al. [39] showed a conditional space lower bound of Ω(m5/3 )
for constant-time stretch-2 oracles. Applying the Strong SetDisjointness conjecture to the same
argument as in [18] we can prove that for stretch-less-than-2 oracles the tradeoff between S (the
space for the oracle) and T (the query time) is by S × T 2 = Ω(n2 ).
Recent effort was taken toward constructing compact distance oracles where we allow nonconstant query time. For stretch-2 and stretch-3 Agarwal et al. [10] [9] achieves a space-time tradeoff
of S × T = O(n2 ) and S × T 2 = O(n2 ), respectively, for sparse graphs. Agarwal [8] also showed
many other results for stretch-2 and below. Specifically, Agarwal showed that for any integer k a
stretch-(1+1/k) oracle exhibits the following space-time tradeoff: S × T 1/k = O(n2 ). Agarwal also
showed a stretch-(1+1/(k+0.5)) oracle that exhibits the following tradeoff: S × T 1/(k+1) = O(n2 ).
Finally, Agarwal gave a stretch-(5/3) oracle that achieves a space-time tradeoff of S × T = O(n2 ).
Unfortunately, no lower bounds are known for non-constant query time.
Conditioned on the directed k-Reachability conjecture we prove the following lower bound.
Lemma 4. Assume the directed k-Reachability conjecture holds. Then stretch-less-than-(1 + 2/k)
distance oracles with query time T must use S × T 2/(k−1) = Ω̃(n2 ) space.
Proof. Given a graph G = (V, E) for which we want to preprocess for k-Reachability, we create a
layered graph with k layers where each layer consists of a copy of all vertices of V . Each pair of
neighboring layers is connected by a copy of all edges in E. We omit all directions from the edges.
For every fixed integer k, the layered graph has O(|V |) vertices and O(|E|) edges. Next, notice
that if we construct a distance oracle that can distinguish between pairs of vertices of distance at
most k and pairs of vertices of distance at least k + 2, then we can answer k-Reachability queries.
Consequently, assuming the k-Reachability conjecture we have that S ×T 2/(k−1) = Ω(n2 ) for stretchless-than-(1+2/k) distance oracles (For k = 2 this is exactly the result we get by the SetDisjointness
hypothesis).
⊔
⊓
Notice, that the stretch-(5/3) oracle shown by Agarwal [8] achieves a space-time tradeoff of
S × T = O(n2 ). Our lower bound is very close to this upper bound since it applies for any distance
oracle with stretch-less-than-(5/3), by setting k = 3.

7

SETH and Orthogonal Vectors Space Conjectures

Solving SAT using O(2n ) time where n is number of variables in the formula can be easily done
using only O(n) space. However, the question is how can we use space in the case that we have only
a partial assignment of R variables and we would like to quickly figure out whether this partial
assignment can be completed to a full satisfying assignment or not. On one end, by using just O(n)
space we can answer queries in O(2n−R ) time. On the other end, we can save the answers to all
13

possible queries using O(2R ) space. It is not clear if there is some sort of a tradeoff in between these
two. A related problem is the problem of Orthogonal Vectors (OV). In this problem one is given
a collection of n vectors of length O(log n) and need to answer if there are two of them which are
orthogonal to one another. A reduction from SETH to OV was shown in [41]. By this reduction
given a k-CNF formula of n variables one can transform it using O(2ǫn ) time to O(2ǫn ) instances
of OV in which the vectors are of length 2f (k, ǫ) log n (for any ǫ > 0, where f (k, ǫ)n is the number
of clauses of each sparse formula represented by one instance of OV). This reduction leads to the
following conjecture regarding OV, which is based on SETH: There is no algorithm that, for every
c ≥ 1, solves the OV problem on n boolean vectors of length c log n in Õ(n2−Ω(1) ) time.
We can consider a data structure variant of the OV problem, which we call OV indexing. Given
a list of n boolean vectors of length c log n we should preprocess them and create a suitable data
structure. Then, we answer queries of the following form: Given a vector v, is there a vector in the
list which is orthogonal to v?
We state the following conjecture which is the space variant of the well-studied OV (time)
conjecture:
Conjecture 13. Orthogonal Vectors Indexing Hypothesis: There is no algorithm for every
c ≥ 1 that solves the OV indexing problem with Õ(n2−Ω(1) ) space and truly sublinear query time.
We note that we believe that the last conjecture is true even if we allow superpolynomial
preprocessing time. Moreover, it seems that it also may be true even for some constant c slightly
larger than 2.

8

Space Requirements for Boolean Matrix Multiplication

Boolean Matrix Multiplication(BMM) is one of the most fundamental problems in Theoretical
Computer Science. The question of whether computing the Boolean product of two Boolean matrices
of size n × n is possible in O(n2 ) time is one of the most intriguing open problems. Moreover,
finding a combinatorial algorithm for BMM taking O(n3−ǫ ) time for some ǫ > 0 is considered to
be impossible to do with current algorithmic techniques.
We focus on the following data structure version of BMM, preprocess two n×n Boolean matrices
A and B, such that given a query (i, j) we can quickly return the value of ci,j where C = {ci,j }
is the Boolean produce A and B. Since storing all possible answers to queries will require θ(n2 )
space in the worst case, we focus on the more interesting scenario where we have only O(n2−Ω(1) )
space to store the outcome of the preprocessing stage. In case the input matrices are dense (the
number of ones and the number of zeroes are both θ(n2 )) it seems that this can be hard to achieve
as storing the input matrices alone will take θ(n2 ) space. So we consider a complexity model, which
we call the read-only input model, in which storing the input is for free (say on read-only memory),
and the space usage of the data structure is only related to the additional space used. We now
demonstrate that BMM in the read-only input model is equivalent to SetDisjointness.
Lemma 5. BMM in the read-only input model and SetDisjointness are equivalent.
Proof. Given an instance of SetDisjointness let e1 , ..., eN denote the elements in an input instance.
We construct an instance of BMM as follows. Assume without loss of generality that all sets are
not empty, and so m ≤ N . Row i in matrix A represents a set Si while each column j represents
element ej . An entry ai,j equals 1 if ej ∈ Si and equals zero otherwise. We also set B = AT . We
14

also pad each of the matrices with zeroes so their size will be N × N . Clearly, ci,j in matrix C,
which is the product of A and B, is an indicator whether Si ∩ Sj = ∅.
In the opposite direction, given two matrices A and B having m ones we view each row i of A
as a characteristic vector of a set Si (the elements in the set correspond to the ones in that row)
and each column j of B as a characteristic vector of a set Sj+n (the elements in the set corresponds
to the ones in that column). Thus, the instance of SetDisjointness that have been created consists
of 2n set with O(m) elements. The value of an element ci,j in the product of A and B can be
determined by the intersection of Si and Sj+n .
⊔
⊓
Another interesting connection between BMM and the other problems discussed in this paper
is the connection to the problem of calculating the transitive closure of a graph, which is the
general directed reachability mentioned above. It is well-known that BMM and transitive closure
are equivalent in terms of time as shown by Fischer and Meyer [22]. But what happens if we consider
space? It is easy to see that BMM can be reduced to transitive-closure (directed reachability) even
in terms of space. However, the opposite direction is not clear as the reduction for time involves
recursive squaring, which cannot be implemented efficiently in terms of space.
Another fascinating variant of BMM is the one in which an n × n matrix A is input for preprocessing and afterwards we need to calculate the result of multiplying it by a given query vector
v. This can be seen as the space variant of the celebrated OMV (online matrix-vector) problem
discussed by Henzinger et al. [25]. It is interesting to see if one can make use of a data structure so
that n consecutive vector queries can be answered in Õ(n3−Ω(1) ) time.

9

Applications

We now provide applications of our rich framework for proving conditional space lower bounds. In
the following subsections we consider both static and dynamic problems.
9.1

Static Problems

Edge Triangles The first example we consider is in regards to triangles. In a problem that is called
edge triangles detection, we are given a graph G = (V, E) to preprocess and then we are given an
edge (v, u) as a query and need to answer whether (u, v) belongs to a triangle. In a reporting variant
of this problem, called edge triangles we need not only to answer if (u, v) belongs to a triangle but
also report all triangles it belongs to. This problem was considered in [12].
It can be easily shown that these problems are equivalent to SetDisjointness and SetIntersection.
We just construct a set Sv per each vertex v containing all its neighbors. Querying if there is a
triangle containing the edge (u, v) is equivalent to asking if Sv ∩ Su is empty or not. Considering
the reporting variant, reporting all triangles containing (u, v) is thus equivalent to finding all the
elements in Sv ∩ Su . Therefore, we get the following results:
Theorem 5. Assume the Strong SetDisjointness conjecture. Suppose there is a data structure for
edge triangles detection problem for a graph G = (V, E), with S space and query time T . Then
S = Ω̃(|E|2 /T 2 ).
Theorem 6. Assume the Strong SetIntersection conjecture. Suppose there is a data structure for
edge triangles problem for a graph G = (V, E), with S space and query time O(T + op) time, where
op is the size of the output of the query. Then S = Ω̃(|E|2 /T ).
15

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 = aaccbacab the
histogram is v(T ) = (4, 2, 3). In the histogram indexing problem we preprocess an N -length string
T to support the following queries: given a query histogram v, return whether there is a substring
T ′ of T such that v(T ′ ) = v.
This problem has received much attention in the recent years. The case where the alphabet size
is 2 (binary alphabet) was especially studied. A simple algorithm for this case solves the problem in
O(N 2 ) preprocessing time and constant query time. There was a concentrated effort to reduce the
quadratic preprocessing time for some years. However, an algorithm with preprocessing time that
is O(N 2−ǫ ) for some ǫ > 0 was unknown until a recent breakthrough by Chan and Lewenstein [16].
They showed an algorithm with O(N 1.859 ) preprocessing time and constant query time. For alphabet
size ℓ they obtained an algorithm with Õ(N 2−δ ) preprocessing time and Õ(N 2/3+δ(ℓ+13)/6 ) query
time for 0 ≤ δ ≤ 1. Regarding space complexity, it is well known how to solve histogram indexing
for binary alphabet using linear space and constant query time. For alphabet size ℓ, Kociumaka
et al. [30] presented a data structure with Õ(N 2−δ ) space and Õ(N δ(2ℓ−1) ) query time. Chan and
Lewenstein [16] improved their result and showed a solution by a data structure using Õ(N 2−δ )
space with only Õ(N δ(ℓ+1)/2 ) query time.
Amir et al. [11] proved conditional lower bound on the tradeoff between the preprocessing and
query time of the histogram indexing problem. Very recently, their lower bound was improved and
generalized by Goldstein et al. [24]. Following the reduction by Goldstein et al. [24] and utilizing
our framework for conditional space lower bounds, we obtain the following lower bound on the
tradeoff between the space and query time of histogram indexing:
Theorem 7. Assume the Strong 3SUM-Indexing conjecture holds. The histogram indexing problem
2(1−α)

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

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

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

Proof. We use the same reduction as in [24]. This time it will be used to reduce an instance
of 3SUM-Indexing (on 2n numbers) to histogram indexing, instead of reducing from an instance
of 3SUM. The space consumed by the reduction is dominated by the space needed to prepare a
ℓ−2−α
histogram indexing instance with string length N = O(n ℓ−3 ) for histogram queries. The number
of histogram queries we do for each query number z of the 3SUM-Indexing instance is O(nα ). The
query time is dominated by the time required by these queries. Let S(N, ℓ) denote the space required
by a data structure for histogram indexing on N -length string over alphabet size ℓ and let Q(N, ℓ)
denote the query time for the same parameters. Assuming the strong 3SUM-Indexing conjecture and
following our reduction, we have that S(N, ℓ) = O(n2−Ω(1) ) and Q(N, ℓ) = O(n1−α−Ω(1) ). Plugging
in the value of n in terms of N we get the required lower bound.
⊔
⊓
If we plug in the previous theorem δ = 2(1−α)
ℓ−1−α , we get that if the strong 3SUM-Indexing conjecture
is true we cannot have a solution for histogram indexing with Õ(N 2−δ ) space and Õ(N δ(ℓ−2)/2 ) query
time. This lower bound is very close to the upper bound obtained by Chan and Lewenstein [16] as
there is only a gap of 32 δ in the power of N in the query time. Moreover, if the value of δ becomes
close to 0 (so the value of α is close to 1) the upper bound and the lower bound get even closer
to each other. This is very interesting, as it means that to get truly subquadratic space solution
for histogram indexing for alphabet size greater than 2, we will have to spend polynomial query
16

time. This is in stark contrast to the simple linear space solution for histogram indexing over binary
alphabets that supports queries in constant time.
Following reductions presented in [31], from SetIntersection or SetDisjointness to several other
problems, we are able to show that based on the Strong SetDisjointness conjecture, the same problems admit a space/query time lower bounds. For sake of completeness, we reproduce these reductions in the next three subsections and show that they admit the space lower bounds as needed.
Distance Oracles for Colors Let P be a set of points in some metric with distance function
d(·, ·), where each point p ∈ P has some associated colors C(p) ⊂ [ℓ]. For c ∈ [ℓ] we denote by
P (c) the set of points from P with color c. We generalize d so that the distance between a point p
and a color c is denoted by d(p, c) = minq∈P (c) {d(p, q)}. In the (Approximate) Distance Oracles for
Vertex-Labeled Graphs problem [17,26] we are interested in preprocessing P so that given a query
of a point q and a color c we can return d(q, c) (or some approximation). We further generalize d
so that the distance between two colors c and c′ is denoted by d(c, c′ ) = minp∈P (c) {d(p, c′ )}. In the
Distance Oracle for Colors problem we are interested in preprocessing P so that given two query
colors c and c′ we can return d(c, c′ ). In the Approximate Distance Oracle for Colors problem we
are interested in preprocessing P and some constant α > 1 so that given two query colors c and c′
we can return some value dˆ such that d(c, c′ ) ≤ dˆ ≤ αd(c, c′ ).
We show evidence of the hardness of the Distance Oracle for Colors problem and the Approximate Distance Oracle for Colors problem by focusing on the 1-D case.
Theorem 8. Assume the Strong SetDisjointness conjecture. Suppose there is a 1-D Distance Oracle
for Colors with constant stretch α ≥ 1 for an input array of size N with S space and query time T .
Then S = Ω̃(N 2 /T 2 ).
Proof. We reduce SetDisjointness to the Colored Distance problem as follows. For each set Si we
define a unique color ci . For an element e ∈ U (U is the universe
of the elements in our sets) let
P
|e| denote the number of sets containing e and notice that e∈U |e| = N . Since each element in U
appears in at most m sets, we partition U into Θ(log m) parts where the ith part Pi contains all of
the elements e ∈ U such that 2i−1 < |e| ≤ 2i . An array Xi is constructed from Pi = {e1 , · · · e|Pi | }
by assigning an interval Ij = [fj , ℓj ] in Xi to each ej ∈ Pi such that no two intervals overlap.
Every interval Ij contains all the colors of sets that contain ej . This implies that |Ij | = |ej | ≤ 2i .
Furthermore, for each ej and ej+1 we separate Ij from Ij+1 with a dummy color d listed 2i + 1
times at locations [ℓj + 1, fj+1 − 1].
We can now simulate a SetDisjointness query on subsets (Si , Sj ) by performing a colored distance
query on colors ci and cj in each of the Θ(log m) arrays. There exists a Pi for which the two points
returned from the query are at distance strictly less than 2i + 1 if and only if there is an element in
U that is contained in both Si and Sj . The space usage is Õ(S) and the query time is Õ(T ). The
rest follows directly from the Strong SetDisjointness conjecture.
Finally, notice that the lower bound also holds for the approximate case, as for any constant α
the reduction can overcome the α approximation by separating intervals using α2i + 1 listings of
d.
⊔
⊓
Document Retrieval Problems with Multiple Patterns In the Document Retrieval problem [35] we are interested in preprocessing a collection of documents X = {D1 , · · · , Dk } where
17

P
N = D∈X |D|, so that given a pattern P we can quickly report all of the documents that contain
P . Typically, we are interested in run time that depends on the number of documents that contain
P and not in the total number of occurrences of P in the entire collection of documents. In the
Two Patterns Document Retrieval problem we are given two patterns P1 and P2 during query time,
and wish to report all of the documents that contain both P1 and P2 . We consider two versions of
the Two Patterns Document Retrieval problem. In the decision version we are only interested in
detecting if there exists a document that contains both patterns. In the reporting version we are
interested in enumerating all documents that contain both patterns.
All known solutions
√for the Two Patterns Document Retrieval problem with non trivial preprocessing use at least Ω( N ) time per query [18,28,29,35]. In a recent paper, Larsen, Munro, Nielsen,
and Thankachan [33] show lower bounds for the Two Patterns Document Retrieval problem conditioned on the hardness of boolean matrix multiplication.
It is straightforward to see that the appropriate versions of the two pattern document retrieval
problem solve the corresponding versions of the SetDisjointness and SetIntersection problems. In
particular, this can be obtained by creating an alphabet Σ = F (one character for each set),
and for each e ∈ U we create a document that contains the characters corresponding to the sets
that contain e. The intersection between Si and Sj directly corresponds to all the documents that
contain both a and b. Thus, all of the lower bound tradeoffs for intersection problems are lower
bound tradeoffs for the two pattern document retrieval problem.
Theorem 9. Assume the Strong SetDisjointness conjecture. Suppose there is a data structure for
the decision version
P of the Two Patterns Document Retrieval problem for a collection of documents
X where N = D∈X |D|, with S space and query time T . Then S = Ω̃(N 2 /T 2 ).
Theorem 10. Assume the Strong SetIntersection conjecture. Suppose there is a data structure for
the reporting version
of the Two Patterns Document Retrieval problem for a collection of documents
P
X where N = D∈X |D|, with S space and query time O(T + op) where op is the size of the output.
Then S = Ω̃(N 2 /T ).
Forbidden Pattern Document Retrieval In the Forbidden Pattern Document Retrieval problem [21] we are also interested in preprocessing the collection of documents but this time given a
query P + and P − we are interested in reporting all of the documents that contain P + and do not
contain P − . Here too we consider a decision version and a reporting version.
All known solutions for the
√ Forbidden Pattern Document Retrieval problem with non trivial
preprocessing use at least Ω( N ) time per query [21,29]. In a recent paper, Larsen, Munro, Nielsen,
and Thankachan [33] show lower bounds for the Forbidden Pattern Document Retrieval problem
conditioned on the hardness of boolean matrix multiplication.
Theorem 11. Assume the Strong 3SUM-Indexing conjecture. Suppose there is a data structure
for the decision version ofPthe Forbidden Pattern Document Retrieval problem for a collection of
documents X where N = D∈X |D|, with S space and query time T . Then S = Ω̃(N 2 /T 4 ).
Proof. We will make use of the hard instance of SetDisjointness that was used in order to prove
Theorem 1, and reduce this specific hard instance to the decision version of the Forbidden Pattern
Document Retrieval problem. Recall that the size of this hard instance is Õ(n2−γ ), the universe
size is O(n2−2γ ), the number of sets is Õ(n), and we need to perform Õ(nγ ) SetDisjointness queries
in order to answer one 3SUM-Indexing query.
18

Similar to the proof of Theorem 9 we set Σ = F (one character for each set). However, this
time for each e we create a document that contains all the characters corresponding to sets Bi,j
that contain e and all the characters corresponding to sets Ci,j that do not contain e.
The reason that we prove our lower bound based on the Strong 3SUM-Indexing conjecture and
not on the Strong SetDisjointness conjecture is because the size of our instance can become rather
large relative to N (as the number of sets that do not contain an element can be extremely large).
Thus, the size of the Forbidden Pattern Document Retrieval instance is N = θ(n3−2γ ), and the
number of queries to answer is θ(nγ ). Notice that the size of the instance enforces γ to be strictly
2
larger than 1/2. By the Strong 3SUM-Indexing conjecture, either S = s3SI = Ω̃(n2 ) = Ω̃(N 3−2γ ) or
1−γ

O(nγ T ) ≥ t3SI ≥ Ω̃(n), and so T ≥ Ω̃(N 3−2γ ). For any constant ǫ > 0, if the Forbidden Pattern
2

2

−ǫ

Document Retrieval data structure uses Θ̃(N 3−2γ ) space, then S · T 4 = Ω̃(N 3−2γ
Ω̃(N 2−ǫ ). Since this holds for any ǫ > 0 it must be that S · T 4 = Ω̃(N 2 ).

4−4γ
−ǫ+ 3−2γ

) =
⊔
⊓

1

Notice that if we only allow linear space then we obtain a query time lower bound of Ω(N 4 −o(1) ).
Theorem 12. Assume the Strong 3SUM-Indexing conjecture. Suppose there is a data structure
for the reporting version of
Pthe Forbidden Pattern Document Retrieval problem for a collection of
documents X where N = D∈X |D|, with S space and query time O(T + op) where op is the size
of the output. Then S = Ω̃(N 2 /T ).
Proof. Our proof is similar to the proof of Theorem 11, only this time we use the hard instance
of SetIntersection from Theorem 2. So the number of queries is Õ(nγ ), the size of the universe is
1+δ+γ
O(n1+δ−γ ), the number of sets is Õ(n 2 ), and the total size of the output is Θ(n2−δ ).
1+δ+γ
Thus, the size of the Forbidden Pattern Document Retrieval instance is N = Θ(n1+δ−γ n 2 ) =
3+3δ−γ
Θ(n 2 ), and the number of queries to answer is θ(nγ ). Notice that the size of the instance en4
forces 3δ − γ < 1. By the Strong 3SUM-Indexing conjecture, either S = s3SI = Ω̃(n2 ) = Ω̃(N 3+3δ−γ )
2−2γ

or O(nγ T ) ≥ t3SI ≥ Ω̃(n), and so T ≥ Ω̃(N 3+3δ−γ ). For any constant ǫ > 0, if the Forbidden Pattern
4

Document Retrieval data structure uses Θ̃(N 3+3δ−γ
6δ
−ǫ
2− 3+3δ−γ

−ǫ

). Since this holds for any ǫ > 0 and since we can make
Ω̃(N
it must be that S · T = Ω̃(N 2 ).
9.2

4

) space, then S · T = Ω̃(N 3+3δ−γ
6δ
3+3δ−γ

2−2γ
−ǫ+ 3+3δ−γ

)=

as small as we like,
⊔
⊓

Dynamic Problems

We show space lower bounds on dynamic problems. Lower bounds for these problems from the time
perspective were considered by Abboud and Vassilevska-Williams [5]. The first dynamic problem
we consider is st-SubConn which is defined as follows. Given an undirected graph G = (V, E), two
fixed vertices s and t and a set S ⊆ V , answer whether s and t are connected using vertices form
S only. Vertices can be added or removed from S.
The SetDisjointness problem can be reduced to st-SubConn. Given an instance of SetDisjointness
we create an undirected graph G = (V, E) as follows. We first create two unique vertices s and t.
Then, for each set Si we create two vertices vi and ui and for each element ej we create a vertex wj .
Moreover, we define E = {(vi , wj )|ej ∈ Si } ∪ {(ui , wj )|ej ∈ Si } ∪ {(s, vi )|1 ≤ i ≤ m} ∪ {(ui , t)|1 ≤
i ≤ m}. Initially the set S contains s and t and all the wi s. Given a query (i, j) asking about the
emptiness of Si ∩ Sj , we add vi and uj to the set S. Then, we ask if s and t are connected, if so we
19

know that Si ∩ Sj is not empty as the only way to get from s to t is following vi and uj and some
node representing a common element of Si and Sj . If s and t are not connected then it is clear
that the intersection is empty. After the query we remove the two vertices we have added so other
queries can be handled properly. By this construction we get the following result:
Theorem 13. Assume the Strong SetDisjointness conjecture. Suppose there is a data structure for
st-SubConn problem for a graph G = (V, E), with S space and update and query time T . Then
S = Ω̃(|E|2 /T 2 ).
There are other dynamic problems that st-SubConn can be efficiently reduced to, as shown by
Abboud and Vssilevska-Williams [5]. This includes the following 3 problems:
Problem 6. (s,t)-Reachability (st-Reach). Maintain a directed graph G = (V, E) subject to
edge insertions and deletions, so that queries about the reachability of fixed vertices s and t can be
answered quickly.
Problem 7. Bipartite Perfect Matching (BPMatch). Preprocess and maintain undirected bipartite graph G = (V, E) subject to edge insertions and deletions, so that we can quickly answer if
the graph has perfect matching.
Problem 8. Strong Connectivity (SC). Preprocess and maintain directed graph G = (V, E)
subject to edge insertions and deletions, so that we can quickly answer if the graph is strongly
connected
Using our last theorem and the reductions by Abboud and Vassilevska-Williams [5], noting that
they do not effect the space usage, we get the following:
Theorem 14. Assume the Strong SetDisjointness conjecture. Suppose there is a data structure for
st-Reach/ BPMatch/ SC problem for a graph G = (V, E), with S space and update and query time
T . Then S = Ω̃(|E|2 /T 2 ).
We can get better lower bound for these 3 problems on sparse graphs based on the directed
reachability conjecture. Given a sparse graph G = (V, E) as an instance of directed reachability we
can reduce it to an instance of st-Reach by just adding to special nodes s and t to the graph. Then,
we can answer queries of the form ”Is v reachable from u?” by inserting two edges (s, v) and (u, t)
and asking if t is reachable from s. After the query we can restore the initial state by deleting these
two edges. Thus, by using the reductions from st-Reach to BPMatch and SC as shown in [5], we
get the following hardness result:
Theorem 15. Assume the Directed Reachability conjecture. Any data structure for the st-Reach/
BPMatch/ SC problem on sparse graphs can not have Õ(n1−Ω(1) ) update and query time and
Õ(n2−Ω(1) ) space.

References
1. Amir Abboud, Arturs Backurs, Thomas Deuholm Hansen, Virginia Vassilevska Williams, and Or Zamir. Subtree
isomorphism revisited. In Proc. of 27th ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1256–1271,
2016.

20

2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal,
so is Valiant’s parser. 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 98–117,
2015.
3. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-time hardness of LCS and other
sequence similarity measures. 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages
59–78, 2015.
4. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph
centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015.
5. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic
problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia,
PA, USA, October 18-21, 2014, pages 434–443, 2014.
6. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences.
In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 39–51, 2014.
7. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an
extremely popular conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of
Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 41–50, 2015.
8. Rachit Agarwal. The space-stretch-time tradeoff in distance oracles. In Algorithms - ESA 2014 - 22th Annual
European Symposium on Algorithms, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 49–60, 2014.
9. Rachit Agarwal, Brighten Godfrey, and Sariel Har-Peled. Faster approximate distance queries and compact
routing in sparse graphs. CoRR, abs/1201.2703, 2012.
10. Rachit Agarwal, Philip Brighten Godfrey, and Sariel Har-Peled. Approximate distance queries and compact routing in sparse graphs. In INFOCOM 2011. 30th IEEE International Conference on Computer Communications,
pages 1754–1762, 2011.
11. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark,
July 8-11, 2014, Proceedings, Part I, pages 114–125, 2014.
12. Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Mind the gap. CoRR,
abs/1503.07563, 2015.
13. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH
is false). In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015,
Portland, OR, USA, June 14-17, 2015, pages 51–58, 2015.
14. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms
unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661–670, 2014.
15. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic
time warping. 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2015.
16. Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proceedings
of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA,
June 14-17, 2015, pages 31–40, 2015.
17. Shiri Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In ESA 2012, pages 325–336,
2012.
18. Hagai Cohen and Ely Porat. Fast set intersection and two-patterns matching. Theor. Comput. Sci., 411(4042):3795–3800, 2010.
19. Hagai Cohen and Ely Porat. On the hardness of distance oracle for sparse graph. CoRR, abs/1006.1117, 2010.
20. M. Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without
primes. In Proceedings 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages
569–580, 1996.
21. Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, and Niko
Välimäki. Forbidden patterns. In LATIN, pages 327–337, 2012.
22. Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual
Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13-15, 1971, pages 129–
131, 1971.
23. A. Gajentaan and M. H. Overmars. On a class of O(n2 ) problems in computational geometry. Comput. Geom.,
5:165–185, 1995.

21

24. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. How hard is it to find (honest) witnesses?
In European Symposium on Algorithms, ESA 2016, pages 45:1–45:16, 2016.
25. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and
strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR,
USA, June 14-17, 2015, pages 21–30, 2015.
26. Danny Hermelin, Avivit Levy, Oren Weimann, and Raphael Yuster. Distance oracles for vertex-labeled graphs.
In Automata, Languages, and Programming - 38th International Colloquium, ICALP (2), pages 490–501, 2011.
27. Jacob Holm, Eva Rotenberg, and Mikkel Thorup. Planar reachability in linear space and constant time. CoRR,
abs/1411.5867, 2014.
28. Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, and Jeffrey Scott Vitter. String retrieval for multi-pattern
queries. In SPIRE, pages 55–66, 2010.
29. Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, and Jeffrey Scott Vitter. Document listing for queries with
excluded pattern. In CPM, pages 185–195, 2012.
30. Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Efficient indexes for jumbled pattern matching
with constant-sized alphabet. In ESA, pages 625–636, 2013.
31. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In To appear in
27th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
32. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Dynamic set intersection. In Proceedings 14th Int’l Symposium on
Algorithms and Data Structures (WADS), pages 470–481, 2015.
33. Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, and Sharma V. Thankachan. On hardness of several
string indexing problems. In CPM, pages 242–251, 2014.
34. Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, and Sharma V. Thankachan. On hardness of several
string indexing problems. Theor. Comput. Sci., 582:74–82, 2015.
35. S. Muthukrishnan. Efficient algorithms for document retrieval problems. In SODA, pages 657–666, 2002.
36. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM
Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603–
610, 2010.
37. Mihai Patrascu. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827–847, 2011.
38. Mihai Patrascu and Liam Roditty. Distance oracles beyond the Thorup-Zwick bound. SIAM J. Comput.,
43(1):300–311, 2014.
39. Mihai Patrascu, Liam Roditty, and Mikkel Thorup. A new infinity of distance oracles for sparse graphs. In 53rd
Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October
20-23, 2012, pages 738–747, 2012.
40. Mihai Patrascu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the TwentyFirst Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19,
2010, pages 1065–1075, 2010.
41. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci.,
348(2-3):357–365, 2005.
42. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle
problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26,
2010, Las Vegas, Nevada, USA, pages 645–654, 2010.

22

Appendix
A

Sketch of the Main Results

Strong (k+1)-SUM Indexing

(k+1)-SUM Indexing

Strong k-Set Disjointness

k-Set Disjointness

Directed Reachability

k-Reachability

Strong 3SUM Indexing

3SUM Indexing

Strong Set Disjointness

Set Disjointness

Less-than-(1+2/k) Distance Oracles

Boolean Matrix Multiplication

2-Reachability
Orthogonal Vecors and SETH

Strong Set Intersection
Dynamic Problems

Static Problems

Fig. 1. Space conjectures and the connections between them as shown in this paper. Rectangles represent conjectures,
while problems shown to be hard based on these conjectures are represented by ovals. Full arrow represents a reduction
between two problems which also means an implication in the case of conjectures. Dotted arrow means a generalization
which is also an implication, while dashed line means a generalization with no (known) reduction.

23

