arXiv:1803.00904v1 [cs.CC] 2 Mar 2018

Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein∗
March 5, 2018

Abstract
We prove conditional near-quadratic running time lower bounds
for approximate Bichromatic Closest Pair with Euclidean, Manhattan,
Hamming, or edit distance. Specifically, unless the Strong Exponential Time Hypothesis (SETH) is false, for every δ > 0 there exists a
constant ε > 0 such that computing a (1 + ε)-approximation to the
Bichromatic Closest Pair requires Ω n2−δ time. In particular, this
implies a near-linear query time for Approximate Nearest Neighbor
search with polynomial preprocessing time.
Our reduction uses the Distributed PCP framework of [ARW17],
but obtains improved efficiency using Algebraic Geometry (AG) codes.
Efficient PCPs from AG codes have been constructed in other settings
before [BKK+ 16, BCG+ 17], but our construction is the first to yield
new hardness results.

∗

Harvard University aviad@seas.harvard.edu. This research was supported by a Rabin Postdoctoral Fellowship. I thank Amir Abboud, Karl Bringmann, and Pasin Manurangsi for encouraging me to write up this paper. I am also grateful to Amir, Lijie Chen,
and Ryan Williams for inspiring discussions. Thanks also to Amir, Lijie, Vasileios Nakos,
Zhao Song and anonymous reviewers for comments on earlier versions. Finally, this work
would not have been possible without the help of Gil Cohen and Madhu Sudan with AG
codes.

1

Introduction

Approximate Nearest Neighbor (ANN) search is an important problem in
practice as well as a fundamental problem in theory: preprocess a set A of
N vectors so that given a query vector b, an (approximately) closest vector
(a∗ ∈ A such that ka∗ − bk ≈ mina∈A ka − bk) can be found efficiently. In
this paper we prove conditional hardness results for the easier offline variant, called Batch Approximate Nearest Neighbor or Bichromatic Closest Pair1 : given sets A, B of N vectors, find a pair a∗ ∈ A and b∗ ∈ B
that is approximately the closest (i.e. ka∗ − b∗ k ≈ mina∈A ka − bk). Since
b∈B

this problem is easier, our hardness results extend to Approximate Nearest
Neighbor search as well.
Many algorithms have been designed for Approximate Nearest Neighbor
search and Closest Pair. Even for simple ℓp metrics, there are also many
impossibility results, including: bounds on specific algorithmic approaches
[MNP07, OWZ14, ALRW17], unconditional lower bounds in the cell-probe
and related models (but those hold only against a very small number of
cell probes) [AIP06, PT07, ACP08, PTW08, CR10, PTW10, KP12, AV15,
ALRW17, LPY16], and conditional hardness assuming SETH2 of the exact
variants [Wil05, AW15, DKL16, Wil18].
We are particularly interested in subquadratic algorithms that give
(1 + ε)-approximation to Bichromatic Closest Pair, for arbitrary small
ε > 0. For simplicity, we limit the following discussion to Euclidean metric,
but similar results hold for Hamming and Manhattanmetrics as well. LSH
based techniques can solve this problem in O N 2−Θ(ε) time [IM98], but not
faster[MNP07, OWZ14].
Valiant’s algorithm obtained animproved runtime

√ 
1/3
2−Θ( ε)
[Val15]. The state of the art is an O N 2−Θ̃(ε ) -time
of O N
algorithm by Alman, Chan, and Williams [ACW16]. Can the dependence
on ε be improved indefinitely? Note, for example, that the main result in
[Val15] is an algorithm for an average case
problem
 of the same
 variant
3
5−ω
1.62
4−ω
=O N
(where ω
which, for any constant ε, runs in time O N

is the exponent of matrix multiplication). Can we hope for an f (ε) · N 1.99
time algorithm (for any function f ) for the general case? Our main result

1
Bichromatic distinguishes this problem from the yet easier Monochromatic Closest
Pair problem, where the input is just one set of vectors and the algorithm can return any
pair of vectors.
2
The Strong Exponential Time Hypothesis (SETH) postulates that for every ε there
n
is a k = k (ε) such that k-SAT over n variables requires
 (2 − ε) time.

2ω
3
The running time was later improved to O N 3 = O N 1.59 by [KKK16].

2

in this paper rules out such algorithms:
Theorem 1.1. Assuming SETH, for every constant δ > 0 there exists a
constant ε = ε (δ) such that approximating Bichromatic Closest Pair
in Euclidean,
Manhattan, or Hamming distance to within (1 + ε) requires

2−δ
O N
time.

We also derive an analogous hardness result for Bichromatic Closest
Pair with edit distance4 . However, we note that the best algorithms for
approximate Bichromatic Closest Pair with edit distance [OR07] are
far from matching our hardness result.
Theorem 1.2. Assuming SETH, for every constant δ > 0 there exists a
constant ε = ε (δ) such that approximating Bichromatic
Closest Pair

in edit distance to within (1 + ε) requires O N 2−δ time.

As we mentioned earlier, these results also imply the first (to our knowledge) conditional hardness of Approximate Nearest Neighbor search. In
particular, they imply a near-linear lower bound on query time for any data
structure with a polynomial preprocessing time:
Corollary 1.3. Assuming SETH, for every constants δ, c > 0 there exists
a constant ε = ε (δ, c) such that no algorithm can preprocess a set of N vectors in O (N c ) time, and subsequently
answer (1 + ε)-Approximate Nearest

Neighbor queries in O N 1−δ time (for Euclidean, Manhattan, Hamming,
or edit distance).
Remark 1.4. Informally, in terms of the dependence between δ and ε, our re1/ε
duction loses roughly a single exponential factor (δ ≈ logloglog1/ε
; see Equation
(1)); this is already quite far from best known algorithm [ACW16], which
obtains δ = Θ̃ ε1/3 . Formally, things are worse: we are unable to deduce
any specific relation between δ and ε from SETH, because our reduction also
depends on the unspecified relation between ǫ and k in the formulation of
SETH (alternatively, δ and c in the formulation of the Orthogonal Vectors
Conjecture (OVC); see Conjectures 2.1 and 2.3).

1.1

Techniques

The main technical idea in this paper is a simple instantiation the Distributed PCP framework from [ARW17] with Algebraic Geometry (AG)
codes.
4

The edit distance, sometimes also Levenshtein distance, between two strings a, b is
defined as the minimum number of character deletions, insertions, or substitutions required
to transform a to b.

3

Distributed PCP
Most reductions from SETH to polynomial time problems use the following outline: Given a CNF ϕ over n variables, construct gadget(s) for each
half assignment α, β ∈ {0, 1}n/2 . If the number of gadgets is N ≈ 2n/2 ,
then SETH implies an ≈ N 2 lower bound on the running time for solving
the new instance. One obstacle for using Probabilistically Checkable Proofs
(PCP) to prove hardness of approximation in P is the PCP blowup: given
a 3-CNF ϕ over n variables, the PCP Theorem [AS98, ALM+ 98] gives an
efficient construction of a 3-SAT ϕ′ over n′ variables which is hard to ap′
proximate. But if we construct N ′ ≈ 2n /2 ≫ 2n gadgets, we do not obtain
any meaningful running time lower bounds (even assuming SETH).
Our starting point is the Distributed PCP framework of [ARW17]. Another way to think about the PCP Theorem is as a way to, given assignment x ∈ {0, 1}n to CNF ϕ, generate a proof π (x) that x satisfies ϕ. The
proof π (x) should be “probabilistically checkable”, which means that a randomized verifier needs to read only a small number of bits from the proof.
[ARW17] observed that if we construct the proof π (x) in a distributed manner, namely construct a “half-proof” π (α) , π (β) for each “half-assignment”,
we overcome the PCP blowup because the number of gadgets remains small.
Constructing distributed PCP in this way is not quite possible, but [ARW17]
gave a construction using a short non-deterministic hint. Since we can enumerate over all short hints in deterministic subexponential time, this construction gives near-quadratic hardness of approximation for several problems such as Maximum Inner Product over {0, 1}-vectors.
The techniques of [ARW17] seem inherently doomed to fail to obtain results like Theorem 1.1 (or even Theorem 1.25 ). To understand why, we must
delve into some more details of the non-deterministic distributed PCP construction from [ARW17]. The construction is based on a generalization of an
MA-communication protocol for Set Disjointness by Aaronson and Wigder
son [AW09]. In the T -generalized protocol, (i) Merlin sends O Tn log n bits;
(ii) Alice and Bob toss O (log n) coins; (iii) Bob sends O (T log n) bits; and
then (iv) Alice decides to accept or reject. This protocol is tight up to the
logarithmic factors [Kla03], but those logarithmic factors are crucial for our
fine-grain applications!
Let nMerlin denote the length of Merlin’s message, and nBob for Bob’s
message. The reduction needs to enumerate over all of Merlin’s and Bob’s
potential messages. To enumerate over Merlin’s messages, we simply in5

See also discussion on the closely related Open Question 3 in [ARW17]

4

crease the number of vectors by a 2nMerlin factor; hence we must set nMerlin <
n. For the above T -generalized protocol, this means T = Ω (log n). The
enumeration over Bob’s messages is a bit more subtle, but it roughly corresponds to a (1 + 2−nBob )-factor hardness of approximation for Euclidean
Bichromatic Closest Pair. Hence we also want to set nBob as small as
possible, and in particular constant. But ifwe use the same protocol with
T = Ω (log n), we get that nBob = Ω log2 n , i.e. we don’t even recover the
trivial (1 + 1/poly (n))-hardness of approximation. In other words, our reduction is ultimately restricted by the PCP blowup even in the Distributed
PCP framework.
AG codes
The reason that [AW09]’s MA-protocol incurs an O (log n) overhead is that
it uses Reed-Solomon error correcting code (low degree polynomials), which
has (relative) rate Θ (1/ log n). Indeed, there are many error correcting
codes that achieve constant rate, but most of them don’t have some of the
other nice properties of the Reed Solomon code, such as “systemacity” and
“polynomial closure” (see Theorem 2.4). In fact, in accordance with the
theme of [AW09], their protocol seems inherently based on “algebrization”.
Building on ideas of [Mei13, BKK+ 16], we replace the Reed Solomon code
with AG codes that do satisfy the same nice properties, and at the same
time also achieve constant rate.
 This allows us to reduce Merlin’s and Bob’s
message lengths to O Tn log T and O (T log T ) (Theorem 3.1). In particular,
we can now take T to be a (large) constant.
Edit distance
Our hardness for ANN with edit distance (Theorem 1.2) is obtained by a
black-box reduction from the hardness of ANN with Hamming distance. The
main challenge in the reduction is to rule out small edit distance solutions
obtained by “shifting” the vectors with deletions. Our construction replaces
each bit of the Hamming distance instance vectors with a short random
string. Now for every i such that ai = bi , the corresponding random string
gadgets are identical so the contribution to the edit distance is zero. For i
such that ai 6= bi , the gadget corresponding to ai is matched with a uniformly
random string, regardless of the shift. Some care is required in the analysis
since the behavior of edit distance of random strings is not so well understood
(even the expected edit distance is not known).

5

1.2

Related work

Distributed PCP Most closely related to our work is [ARW17] that introduced the Distributed PCP framework and proved SETH-based nearquadratic hardness of approximation results for several problems in P. In
particular, they show hardness of approximation for near-polynomial6 factors of Bichromatic Closest Pair with the (non-metric) similarity measures of Maximum Inner Product and Longest Common Subsequence. More
recently, [AR18] built on the Distributed PCP to show that deterministic
truly subquadratic-time algorithms for Longest Common Subsequence (of
two long strings) would imply new circuit lower bounds. [CLM18] use the
Distributed PCP framework to rule out Fixed Parameter Time approximation algorithms for several fundamental problems; in particular their reduction from SETH relies on the more efficient construction of Distributed PCP
(with AG codes) from our work.
The latest in this line of work is [Che18], who obtains several closely
related results: (i) building on our techniques, he obtains more refined
variants of our hardness results and the matching algorithms (in particular, more explicit dependence on the dimension d); (ii) he exhibits a hardness of approximation result (for {±1}-Maximum Inner Product) inspired
by replacing MA-communication complexity with quantum communication
complexity; (iii) he proves new hardness of exact Euclidean Bichromatic
∗
Closest Pair in 2O(log n) dimensions by replacing MA-communication with
NP · UPP-communication; and finally (iv) he makes significant progress on
our Open Question 1.
Approximate Nearest Neighbor The list of algorithms for Approximate Nearest Neighbor search and Closest Pair in ℓp metrics is very long, e.g.
[SH75, BS76, GBT84, AES91, AM93, AMN+ 94, KM95, Kle97, IM98, Ind99,
KOR00, Ind00, AF03, Ind03, AI06, AMM09, AC14, AINR14, AIL+ 15,
AR15, Val15, ACW16, ALRW17, Ahl17, Cha17]; see also Razenshteyn’s
recent thesis [Raz17] for more details. As we mentioned earlier, previous
impossibility results include bounds on progress via specific algorithmic approaches [MNP07, OWZ14, ALRW17], unconditional lower bounds in the
cell-probe and related models (but those hold only against a very small number of cell probes) [AIP06, PT07, ACP08, PTW08, CR10, PTW10, KP12,
AV15, ALRW17, LPY16], and conditional hardness assuming SETH of the
exact Nearest Neighbor Search problem [Wil05, AW15, DKL16, Wil18]. For
6

Building on our techniques, this was later improved to polynomial factors in [Che18].

6

edit distance Approximate Nearest Neighbor search, after a sequence of improving embedding-based algorithms [Ind04, BYJKK04, BES06, OR07], the
state
√ of the art for truly subquadratic time algorithms in d dimensions is a
log d log log d) -approximation [OR07]. For embedding into specific norms,
O(
2
some lower bounds were proven, e.g. [ADG+ 03, KN05, AK07, AJP10].
SETH-hardness for the exact problem is also known [ABV15, BI15].
AG codes Algebraic Geometry (AG) codes generalize Reed Solomon
and Reed Muller codes. The first construction is due to Goppa [Gop81],
but we use an efficiently decodable construction from [SAK+ 01]. AG
codes have received significant attention from computer scientists (e.g.
[GS99, GP08, BT13, CT13, GX13, GX14, HRW17]). In particular, Meir
[Mei13] observed that “algebrization-like” construction (in particular, the
proof of IP = PSPACE) can be obtained with any error correcting codes
that satisfy properties that he calls multiplicativity (polynomial closure)
and systemacity. Ben-Sasson et al. [BKK+ 16] observed that AG codes satisfy those properties and at the same time achieve a constant rate. They
used AG codes to construct PCP of linear size but polynomial query complexity. Finally, [BCG+ 17] used AG codes to construct Interactive Oracle
Proofs of linear size, constant query complexity, and a constant number of
rounds. We note that our construction is the first to obtain qualitatively
new hardness results from AG codes (and our ideas have already inspired
even more hardness results in followup work [CLM18, Che18]!).

1.3

Discussion and open problems

While our application of AG codes to the MA-communication protocol is
very simple and easily yields strong results like Theorem 1.1, there are a few
closely related applications where we are unable to shave the logarithmic
factors using AG codes.
MA-communication complexity of Set Disjointness [AW09]’s origi√
nal protocol gives an O ( n log n) MA-communication protocol for Set Disjointness. Naively, one would expect that it should be possible to obtain an
√
O ( n) protocol using AG codes, which would be tight by [Kla03]. However,
√
there is a step in the protocol that requires verifying that a vector in {0, 1} n
is all zeros by looking at its sum; we only know how to perform this step
√
over a large field. In Theorem 3.2 we use related ideas to obtain an O ( n)
AMA-communication complexity, but we don’t know how to do that for
MA-communication. Note also that [AW09]’s protocol also solves the more
7

general Inner Product problem for the same communication complexity. In
an earlier version of this paper, we asked whether the MA-communication
√
√
complexity of (Set Disjointness / Inner Product) is Θ ( n)√or Θ ( n log n)?
This was partially answered by [Che18] who gave an O n log n log log n
protocol using AG codes.
Open Question 1 (MA-communication complexity). What are the MAcommunication complexities of the Set Disjointness
and Inner
 Product prob√
√
lems (known to be between Ω ( n) and O n log n log log n )?

IP-communication complexity of Set Disjointness [AW09]’s protocol
also generalizes to an O (log n log log n) IP-protocol. The IP-protocol uses
O (log n) rounds, where at each round a Reed Solomon code over field size
O (log n) is used. One may hope to obtain an O (log n) bits protocol using
AG codes. But it is crucial that the failure probability in each round is
1 − O (1/ log n), whereas AG codes of constant rate cannot obtain distance
1 − o (1). We note that this IP protocol is used in [AR18] in the context of
Distributed PCP, and reducing the communication to O (log n) would imply
stronger conditional circuit lower bounds.
Open Question 2 (IP-communication complexity). Is there an O (log n)
IP-communication complexity protocol for Set Disjointness?
Exact Bichromatic Closest Pair with short vectors Williams
[Wil18] recently used a construction closely related to [AW09]’s protocol
to prove that, assuming SETH, exact Bichromatic Closest Pair with
Euclidean distance requires near-quadratic time even for vectors of dimension O log2 log N . (He also proves similar results for Furthest Pair and
Orthogonal Vectors.) He poses an open problem to obtain a similar
result for constant dimension. Again, the bottleneck is the log-of-field-size
factor in the communication protocol, which one may hope to overcome by
using constant size fields. Recent work by Chen [Che18] significantly reduced
∗
the dimension to 2O(log N ) ; but achieving constant dimension remains open.
1.3.1

Looser approximations of Bichromatic Closest Pair

Our techniques can only rule out very good approximations of Bichromatic
Closest Pair in strongly-subquadratic time. Indeed for weaker approximation factors there are strongly subquadratic time algorithms. But can
we rule out near-linear time algorithms for, say, any constant approximation factor? Even better, can we obtain tight conditional result for every
8

approximation factor, as [ALRW17] do for data-dependent LSH? Below we
discuss some of the technical barriers that seem to arise toward proving such
results. We stress that the discussion below is highly informal and should
not be used to draw any definite conclusions.
Finer-grain PCP Reductions from SETH to problems in P are typically
classified as “fine grain complexity” because they provide a very refined
understanding of the running time of problems like Bichromatic Closest
Pair, up to sub-polynomial factors. This means that we have to nail the
“correct” size of the reduction almost exactly — to within sub-polynomial
factors. The PCP blowup we described earlier arises because the reduction
size is exponential in the length of the PCP; so our PCP length should be
optimal up to sub-constant factors!
The Distributed PCP can be seen as a technique for decoupling the
size of the reduction into two parts: the exact part that reduces k-SAT to
some problem in P (e.g. Bichromatic Closest Pair), and the PCP-like
part that is responsible for hardness or approximation gap amplification. In
other words, the size of the new instance NApprox can roughly be described
as the product of the size of the exact reduction, N ≈ 2n/2 , and the gap
amplification factor, NGap :
NApprox ≈ N · NGap .
The first (exact) part is still required to have the correct size, but if the “correct” blowup of gap amplification (NGap ) is tiny, then we can afford some
redundancy. For example, in [ARW17] the correct blowup for gap amplification was NGap = N o(1) , so we could afford to use a much less efficient (losω(1)
[
ing super-polynomial factors) gap amplification N
, while
Gap = (NGap )
o(1) . In the present paper, the
[
barely affecting the reduction size: N
=
N
Gap
correct gap blowup for proving (1 + ε)-inapproximability is NGap = N f (ε) ;
g(ε) blowup, which is still OK
[
using AG codes we can obtain N
Gap = N
when ε is sufficiently small. In contrast, by [AR15], a 2-approximation can
be obtained in time
T (N ) ≈ (NApprox )8/7 ≈ (N · NGap )8/7 ;
plugging in an T (N ) ≈ N 2 lower bound from SETH and solving for NGap ,
we estimate that the correct blowup for a factor 2 gap has to be at least
NGap ≈ N 6/7 . Therefore if we don’t get the correct exponent to within a 7/6factor, we cannot keep the total instance size under N 2 , and hence cannot
9

obtain any super-linear lower bounds on the running time. Even using AG
codes, it seems that we lack the techniques for obtaining such fine-grained
gap amplification. In particular, all PCP constructions (including Dinur’s
combinatorial PCP [Din07]) use error correcting codes, which are inherently
redundant.
Triangle inequality This barrier is specific to obtaining hardness of approximation for factor 3 or greater. Consider a naive gadget reduction where
we construct a vector for each half assignment. Let α1 , α2 ∈ {0, 1}n/2 be
partial assignments to the first half of the variables, and β1 , β2 ∈ {0, 1}n/2
for the second half. Suppose that (α1 ; β1 ) , (α2 ; β1 ) , (α2 ; β2 ) satisfy the formula, but (α1 , β2 ) does not. Let aα1 , aα2 , bβ1 , bβ2 be the corresponding vectors. Then, if our reduction has completeness c and soundness s, we would
like to have
aα1 − bβ2 ≥ s ≥ 3c ≥ aα1 − bβ1 + aα2 − bβ2 + aα2 − bβ1 .
But that would violate the triangle inequality. Note that this restricts our
ability to prove stronger hardness of approximation even for more complicated metrics like edit distance. It is also important to remark that the
reductions based on Distributed PCP (including the ones in this paper) do
not exactly fall into this naive gadget reduction framework; nevertheless it
is not at all clear that they can overcome this obstacle.
Open Question 3 (3-approximation). Prove that, assuming SETH and
for some constant ε > 0, approximating Bichromatic Closest
Pair with

1+ε
Euclidean metric to within factor 3 requires time Ω N
.

2
2.1

Preliminaries
Complexity assumptions

Conjecture 2.1 (Strong Exponential Time Hypothesis (SETH) [IP01]).
For any ǫ > 0, there exists k = k (ǫ) such that k-SAT on n variables cannot
be solved in time O 2(1−ǫ)n .

SETH is in particular known to imply the Orthogonal Vectors Conjecture
(OVC) [Wil05], which postulates a quadratic-time hardness for the following
Orthogonal Vectors problem:
Problem 2.2 (Orthogonal Vectors). Given two sets A, B ⊂ {0, 1}m ,
decide whether there is a pair (a, b) ∈ A × B such that a · b = 0.
10

Conjecture 2.3 (Orthogonal Vectors Conjecture (OVC)). For every δ > 0
there exists c = c (δ) such that given two sets A, B ⊂ {0, 1}m of cardinality
N , where m = c log N , deciding if there is a pair (a, b) ∈ A × B such that
a · b = 0 cannot be solved in time O N 2−δ .

2.2

AG codes

Algebraic Geometry (AG) codes generalize Reed Solomon and Reed Muller
codes. The first construction is due to Goppa [Gop81], but we use an efficiently decodable construction from [SAK+ 01]. The codewords of Reed
Muller codes are low-degree multivariate polynomials. AG codewords are
multivariate rational functions (quotients of polynomials). In particular, like
Reed Solomon or Reed Muller codes, we can add codewords (for free) and
multiply codewords (with some loss in the distance). Here, we only use the
following basic properties of AG codes; for a thorough introduction, we refer
the reader to [Sti09].
Theorem 2.4 ([SAK+ 01]). There exists a constant q0 ∈ N, such that
o
n for
′
′
every prime q ≥ q0 , there exist two code families C , {Cn } and C , Cn
O(log n)

whose codewords are given by functions w : Rn → Fq2 , for Rn ⊂ Fq2
Furthermore, those code families satisfy the following properties:

.

Systematicity There exists a subset Sn ⊂ Rn of cardinality |Sn | = Θ (n),
such that for any assignment x : Sn → Fq2 , there exists a codeword
w ∈ C such that w |Sn = x.
′

Polynomial Closure C and C are linear codes; furthermore, for every
′
′
′
w1 , w2 ∈ C, there exists w ∈ C such that for every i ∈ Rn , w (i) =
w1 (i) · w2 (i).
Parameters Both codes have (relative) rate at 0.1 and (relative) distance
at least 0.1.
Efficiency Both codes can be encoded and checked in poly (n) time.

3
3.1

communication complexity
MA communication complexity

Theorem 3.1. The following holds for every T ∈ [2, m]. There is a computationally efficient MA-communication protocol for Set Disjointness over
universe [m] where:
11

1. Merlin sends Alice O



m log T
T



bits.

2. Alice and Bob toss O (log m) coins.
3. Bob sends Alice O (T log T ) bits.
4. Alice returns Accept or Reject.
If the sets are disjoint, Alice always accepts. Otherwise, she accepts with
probability at most 1/2.
Proof. Assume wlog that T divides m. We partition the universe into T
disjoint sets of size m/T : [m] = U 1 ∪ · · · ∪ U T . Let α, β ⊆ [m] denote Alice
and Bob’s respective inputs; for t ∈ [T ], let αt , α ∩ U t , and define β t
analogously.
Let C be an algebraic geometry code over field Fq2 with characteristic
at least q ≥ T , as promised by Theorem 2.4; let ρC , δC , and nC = T m
·ρC =
O (m/T ) denote the relative rate, relative
distance,
and
the
length
of its

t
t
t
codewords. For t ∈ [T ], let C α , C β denote the encodings of α and
β t . Then, by the multiplicative
closure)
property, their entry (polynomial
 

′
t
t
t
t
wise product µ (i.e. µ i , C α i · C β i ) is a codeword in C . By
P
′
T
t
linearity of C , the entry-wise sum of the µt ’s (µi ,
t=1 µ i ) is also a
′
codeword of C .
for each i ∈ [n/T ],
 Since
 C
 is ta systematic code, we have that
t
t
C α i , C β i ∈ {0, 1}, and therefore also µ i ∈ {0, 1}. Observe that
the sets are disjoint iff µt i = 0 for all i ∈ [m/T ] and t ∈ [T ]. Because the
characteristic is at least T , this is equivalent to requiring that µi = 0 for all
i ∈ [m/T ].
Now the protocol proceeds as follows:
1. Merlin sends Alice µ̂, which is allegedly the encoding of µ.
2. Alice and Bob pick a random i∗ ∈ [nC ].


3. Bob sends Alice C β t i∗ , for all t ∈ [T ].

4. Alice accepts iff all of the following hold:
′

(a) µ̂ is a codeword in C ;
 

P 
(b) µ̂i∗ = Tt=1 C αt i∗ · C β t i∗ ; and
(c) µ̂i = 0 for all i ∈ [m/T ].

12

First, we observe that Merlin sends nC · ⌈log T ⌉ = O (log T · m/T ) bits, and
Bob sends T · ⌈log T ⌉ bits, so the communication complexity is as promised
in the theorem statement.
′
If Alice accepts with nonzero probability, then µ̂ is a codeword of C .
Therefore if Alice accepts with probability greater than 1− δC ′ (where δC ′ ≥
0.1 is the relative distance of C ′ ) then µ̂ is also equal to the true µ. Then this
also implies that µi = 0 for all i ∈ [m/T ]. Hence by our earlier observation,
the sets are disjoint.
Finally, repeat Steps 2-4 of the protocol (in parallel) a constant number
of times to obtain soundness 0.5.

3.2

AMA communication complexity

Theorem 3.2. The following holds for every T ∈ [2, m]. There is a computationally efficient AMA-communication protocol for Set Disjointness over
universe [m] where:
1. Alice and Bob toss O (log m) coins, and send them to Merlin.
2. Merlin sends Alice O (m/T ) bits.
3. Alice and Bob toss O (log m) coins.
4. Bob sends Alice O (T ) bits.
5. Alice returns Accept or Reject.
If the sets are disjoint, Alice always accepts. Otherwise, she accepts with
probability at most 1/2.
Proof. The set up is similar to the proof of Theorem 3.1, but we use error
′
correcting codes C, C over a field Fq2 of constant size (that does not depend
on T or m).
t
t
Partition the set [m] into T parts, and let
 α , βt  be the restriction of
t
α, β (respectively) to the t-th part. Let C α , C β denote the encodings
t
t
of
and let µt denote their entrywise product (µt i ,
 α ,tβ, respectively,


t
C α i · C β i ).
At the first step of the protocol, Alice and Bob pick a random subset
S ⊆ [T ]. For now, let us assume that S is chosen uniformly at random (note
√
that this already suffices to show O ( n) AMA-communication complexity).
We will later reduce the number of coins tossed in this step using a standard
argument due to Newman [New91].
13

We now define µ (S) as the entrywise sum of µt , taken only over t ∈ S:
X
µi (S) ,
µt i .
t∈S

Observe that the sets are disjoint iff µt i = 0 for all i ∈ [m/T ] and t ∈ [T ].
If the sets are indeed disjoint, we also have that µi = 0 for all i ∈ [m/T ].
t
Otherwise, there exists i ∈ [m/T ] and t ∈ [T ] such
P that µ ti′ = 1. Fix some
choice of S \ {t}, and hence also the value of t′ ∈S\{t} µ i . Conditioned
on
P those, t t′∈ S with probability exactly 1/2. Therefore, for any value of
t′ ∈S\{t} µ i , we have that the sum with t is nonzero with probability at
least 1/2.
Now the protocol proceeds as follows:
1. Alice and Bob pick S ⊆ [T ] at random, and send it to Merlin
2. Merlin sends Alice µ̂ (S), which is allegedly the encoding of µ (S).
3. Alice and Bob pick a random i∗ ∈ [nC ].


4. Bob sends Alice C β t i∗ , for all t ∈ [T ].

5. Alice accepts iff all of the following hold:
′

(a) µ̂ is a codeword in C ;

 

P
(b) µ̂i∗ (S) = t∈S C αt i∗ · C β t i∗ ; and
(c) µ̂i (S) = 0 for all i ∈ [m/T ].

′

If Alice accepts with nonzero probability, then µ̂ is a codeword of C . Therefore if Alice accepts with probability greater than 1 − δC ′ (where δC ′ ≥ 0.1
is the relative distance of C ′ ) then µ̂ is also equal to the true µ. Then this
also implies that µi = 0 for all i ∈ [m/T ]. Hence by our earlier observation,
if Alice accepts with probability greater than 1 − δC ′ /2, the sets must be
disjoint.
To amplify the soundness to 1/2, we need to repeat the protocol. For
fixed non-disjoint input α, β, we say that Step 1 of the protocol fails if µi = 0
for all i ∈ [m/T ]. We repeat this step of the protocol twice (in parallel) so
the probability that both repetitions fail is only 1/4. Notice that it is safe
to repeat this step in parallel (i.e. we do not need to invoke a “parallel
repetition” theorem) because the failure probability of this step does not
depend on Merlin’s actions. Similarly, we repeat Steps 3-5 of the protocol,
in parallel to amplify the overall soundness of the protocol to 1/2.
14

Finally, instead of sampling S uniformly at random, Alice, Bob and
Merlin can agree in advance on a candidate family S of sets S j , chosen
uniformly at random. For any fixed input α, β, the probability that Step 1
fails on significantly more than half of the S j is 2−O(|S|) . Setting |S| = Θ (m)
allows us to take a union bound over all choices of α, β. Therefore Alice and
Bob only need log |S| = O (log m) coins to choose a random set S j ∈ S.

4

Approximate Closest Pair

Theorem 4.1 (Detailed version of Theorem 1.1). Unless SETH and OVC
are false, the following holds for any ℓp metric, for constant p (including
Hamming, Manhattan, and Euclidean distance): for every δ > 0 there exists
an ǫ = ǫ (δ, p) such that given a set A, B ⊂ {0, 1}d of N vectors (where d =
O (log N )), computing a (1 +
 ǫ)-approximation to Bichromatic Closest
Pair requires time Ω N 2−δ .

Proof. We consider the MA-protocol
 from Theorem 3.1, instantiated with

log 1ǫ
parameter T = T (ǫ) = O log log 1 . Let T ′ = 2O(log T ·T ) denote the number
ǫ

of different possible messages sent by Bob in the protocol. We set T so that
T ′ = O (1/ǫ).
Our reduction takes as input an instance (AOV , BOV ) of Orthogonal
Vectors over {0, 1}m . For heach
i vector β ∈ BOV , we construct a new vector
T ′ ×m
β
β
b̃ ∈ {0, 1}
by setting b̃
, 1 iff Bob sends message i on input β ′
i,j

and randomness j. For each Merlin-message µ ∈ {0, 1}O(log T ·m/T ) and each
′
vector α ∈ AOV , we construct a new vector ãµ,α ∈ {0, 1}T ×m as follows:
[ãµ,α ]i,j , 1 iff Alice accepts on input α, message µ from Merlin, message
i from Bob, and randomness j. Notice also that the inner product of two
vectors ãµ,α · b̃β is exactly proportional to the probability that Alice and Bob
accept on inputs α, β and message µ from Merlin. In particular, if α and β
are not disjoint/orthogonal, the inner product is at most ãµ,α · b̃β ≤ m/2.
Otherwise, there exists a µ such that ãµ,α · b̃β = m.
To argue about distances we have to make one small modification. We
′
′
replace vector ã ∈ {0, 1}T ×m by vector a ∈ {0, 1}T ×m×2 constructed as
follows: ai,j,1 , ãi,j and ai,j,2 , 1 − ãi,j . This guarantees that the number
of 1’s in every a-vector is the same (T ′ · m). The number of 1’s in b-vectors
was already the same (m), so we can just define bi,j,1 , b̃i,j and bi,j,2 , 0.

15

We now have the following
Pr

(i,j,b)∈[T ]′ ×[m]×[2]



[ãµ,α ]i,j,b

h i
6
=
b̃β

i,j,b



h

= Pr [ãµ,α ]i,j,b
=

h i
i
= 1 + Pr b̃β

i,j,b

1
1
1
+
− ′ Pr [Alice accepts] .
′
2 2T
T

In particular, for every p > 0 we have that
(
p
m (T ′ − 1)
min ãµ,α − b̃β =
µ
p
≥ mT ′


=1 −2

α∩β =∅
.
otherwise

For any constant p, taking the (1/p)-th power we have that Orthogonal Vectors reduces to approximating Bichromatic Closest Pair in
ℓp norm to within a factor of


1+

1
T′ − 1

1/p

≥ 1 + Ωp



1
T′



.

The result for Hamming distance follows from Manhattan distance since all
the entries are in {0, 1}.
Finally, observe that our reduction
increases
the number of vectors by


2O(log T ·m/T )

O m·

log2 log 1
ǫ
log 1
ǫ

. Hence in total, if there are
a factor of
= 2
m/c
NOV = 2
vectors in the OVC instance,
 instance of Bichro our new
log2 log 1
ǫ
log 1
ǫ

m 1/c+O

vectors. In particular,
matic Closest Pair has N = 2
approximating Bichromatic Closest Pair to within 1 + ǫ is as hard as
solving the original instance of Orthogonal Vectors, which by OVC
requires time
2−δOV

(|AOV | + |BOV |)2−δOV = 2m/c


 2
log log
m δOV /c−O
1

= N 2 /2

log ǫ

1
ǫ



= N 2−δ ,

where the last equality follows by choosing δ = O δOV +

(1)
c log2 log
log 1ǫ

1
ǫ


, where

δOV and c = c (δOV ) are as in the OVC.
Finally, notice that the vectors we construct have dimension 2T ′ · m =
O (m) = O (log N ).
16

ãµ,α · b̃β
T′ · m · 2

!

4.1

Edit distance

Below we restate and prove our hardness for Bichromatic Closest Pair
with edit distance. In the proof, we use a somewhat non-standard (but
equivalent) notion of edit distance, where we think of characters from both
strings being deleted or substituted (as opposed to inserting, deleting, and
substituting characters from one string).
Theorem 4.2 (Detailed version of Theorem 1.2). Unless SETH and OVC
are false, the following holds for edit distance: for every δ > 0 there exists
an ǫ = ǫ (δ) such that given a set A, B ⊂ {0, 1}d of N vectors (where d =
O (log N log log N )), computing a (1 +
 ǫ)-approximation to Bichromatic
2−δ
.
Closest Pair requires time Ω N

Proof. We first provide a randomized construction. We will later describe
how to efficiently derandomize it.
We begin with a hard instance (AH , BH ) of Hamming distance Bichromatic Closest Pair as guaranteed by Theorem 4.1. Let dH = O (log N )
be the dimension of the vectors in (AH , BH ). We draw 2dH binary random strings of dimension d′ = O (log dH ) uniformly at random, denoted
′
strings
si0 , si1 ∈ {0, 1}d , ∀i ∈ [dH ]. By Claim 4.4, for any twoh random
i

′

′

i i
is
sic , sic′ , the expectation of their edit distance λED
2,d′ , E ED sc , sc′


′
bounded from below by Ω (d′ ). By Claim 4.3, their edit distance ED sic , sic′

also concentrates around its expectation to within ±o (d′ ), with probability 1 − 1/poly (dH ). Furthermore, by applying the same claim with union
bound, if we consider any choice c1 , . . . , cdH , and any contiguous substring of
s1c1 ◦ · · · ◦ sdcdH , it’s distance from any string si1−ci is within (1 ± o (1)) factor
H
of the expected edit distance of two strings of those lengths (w.h.p.).
Our reduction is constructed as follows. For each vector uH ∈ AH ∪ BH
we construct a vector u ∈ {0, 1}d , for d , dH · d′ , by replacing the i-th bit
of uH with one of si0 , si1 . Let [uH ]i denote the i-th bit of uH ; then define
ui , si[uH ] , and also
i

u , u1 ◦ · · · ◦ udH = s1[uH ] ◦ · · · ◦ sd[uHH ] .
1

dH

Analysis
We now argue that for any uH , vH , we have that
ED (u, v) = λED
2,d′ · ∆Hamming (uH , vH ) ± o (d) .
17

By matching every pair of i-th strings, it is clear that ED (u, v) ≤ λED
2,d′ ·
∆Hamming (uH , vH ) + o (d). To see the other direction, it remains to show
that there doesn’t exist a much better way to edit u and v. Recall the
partition of u into the dH substrings ui , . . . , udH . Fix an optimal way to edit
u and v, and partition v into dH contiguous substrings v̂ 1 , . . . , v̂ dH , where all
the characters in each v̂ i are either deleted or matched to a character from
ui . We now have that
ED (u, v) =

dH
X
i=1


ED ui , v̂ i .

(2)

Let G ⊆ [dH ] denote the set of coordinates on which uH , vH agree (notice
that ∆Hamming (uH , vH ) = d
− |G|). We lower bound the sum on the
H
RHS of (2) by considering i ∈ G and i ∈
/ G separately.
• For i ∈ G, we lower bound the contribution to the edit distance by the
difference in length, namely

ED ui , v̂ i ≥ ui − v̂ i ,
(3)
where we use v̂ i to denote the length of v̂ i (in particular, ui = d′
for all i).

• Consider the sum of the edit distances over i ∈
/ G. Let us first replace
i
i
i
i
u , v̂ with freshly drawn random x , y of same lengths. By concentration, we have that
#
"
X
X


ED xi , y i .
ED ui , v̂ i ≥ (1 − o (1)) E
i∈G
/

i∈G
/

By subadditivity, the latter is at least the expected
beP
P editi distance
i .
v̂
u
,
tween two long strings x, y of respective P
lengths i∈G
i∈G
/
/P
i
i
v̂ (i.e. x
u ≥ i∈G
Assume without loss of generality that i∈G
/ P
/
′
is longer). Let y be a uniformly random string of length i∈G
ui .
/
We now have that
#
"
X

i i
≥ E [ED (x, y)]
ED x , y
E
i∈G
/

X
X


≥ E ED x, y ′ −
ui −
v̂ i ,
i∈G
/

i∈G
/

where the second inequality follows by triangle inequality.
18

(4)

Summing (3) and (4), we have that
dH
X
i=1




ED ui , v̂ i ≥ (1 + o (1)) E ED x, y ′ ,

P
ui =
where x, y ′ are uniformly random strings of length at least
i∈G
/
d′ · ∆Hamming (uH , vH ). Finally, by subadditivity of the edit distance and
Fekete’s Lemma, the expected distance between two random strings over
their lengths converges to some constant, so (for sufficiently large d),
P


ui ED
/
′
E ED x, y ≥ (1 − o (1)) i∈G
λ2,d′ .
d′
Hence also

dH
X
i=1


ED ui , v̂ i ≥ (1 − o (1)) λED
2,d′ · ∆Hamming (uH , vH ) .

Derandomizing the construction
In the construction above we used 2d = Θ (log N log log N ) random bits
to generate the strings sic . We can reduce the number of random bits
to poly log log N by making the strings log log N -wise independent (e.g.
[Kop13]), over which we can enumerate in N o(1) time. (Note that there is
another O (log log N ) factor because each string requires d′ = O (log log N )
random bits, and yet another log dH = O (log log N ) random bits because
we generate 2dH random strings.)
If thestringsare pairwise independent, this already suffices to guarantee
′
i i′
that ED sic , sic′ = (1 ± o (1)) λED
2,d′ for every sc , sc′ , with high probability.
But when we argued about the edit distance between any contiguous substring of s1c1 ◦ · · · ◦ sdcdH and si1−ci , we assumed the strings s1c1 , . . . , sdcdH are all
H

H

fully independent (in particular, we took a union bound over all 2dH choices
of c1 , . . . , cdH ). Instead, we observe that it suffices to use the probabilistic
argument only for contiguous substrings of length O (d′ ), i.e. substrings
that intersect with only a constant number of sici : for longer substring, their
edit distance to si1−ci is always almost maximal, because the si1−ci is much
shorter so we have to delete almost the entire longer substring. Therefore
using log log N = ω (1)-wise independent strings suffices.

19

4.1.1

Edit distance between random strings

Claim 4.3 (Concetration of edit distance). Let z ∈ {0, 1}n be an arbitrary
string, and let x, y ∈ {0, 1}m be chosen uniformly at random. Then for any
t ≥ 0,


2t2
Pr [|ED (z, x) − Ey [ED (z, y)]| > t] ≤ 2 exp −
.
x
m
Proof. For any choice of x ∈ {0, 1}m and i ∈ [n], let x̂i ,
(x1 , . . . xi−1 , 1 − xi , xi+1 , . . . , xm ). Observe that by the triangle inequality,


ED (z, x) − ED z, x̂i ≤ ED x, x̂i = 1.

The claim follows from McDiarmid’s inequality.

Claim 4.4 (Expectation of edit distance). Let z ∈ {0, 1}n be an arbitrary
string, and let x ∈ {0, 1}n be chosen uniformly at random. Then
1
E [ED (z, x)] ≥ 0.08686.
n
Proof. By [Lue09], the expected length of the longest common subsequence
(Chvatal-Sankoff constant, γ2 ) for sufficiently large n is at most
1
E [LCS (z, x)] ≤ 0.826280.
n
The claim follows from ED (z, x) ≥ (n − E [LCS (z, x)]) /2.

4.2

Approximate Nearest Neighbor

For completeness, we present the proof of Corollary 1.3 from Theorems 4.1
and 4.2. Variants of this reduction have appeared many times before; to the
best of our knowledge, the original idea is due to [WW10].
Proof of Corollary 1.3. We show that given an Approximate Nearest Neigh
bor data structure with preprocessing time O (N c ) and query time O N 1−δ ,
we can 
obtain an
 algorithms for Bichromatic Closest Pair that runs in
′
2−δ
for δ′ = δ′ (δ, c). Set γ , 1/2c. Given an instance (A, B) of
time O N

Bichromatic Closest Pair, partition the set A into N 1−γ disjoint subsets

A1 , . . . , AN γ . Now preprocess each set Ai in time O ((N γ )c ) = O N 1/2 ,


so O N 3/2−γ in total for O N 1−γ
subsets.
For each b ∈ B, query each




1−δ
γ
= O N γ−γδ , so O N 2−γδ in
of the data structures in time O (N )
20

total. Note that if there exists a close pair (a∗ , b∗ ), when we query the subset
that contains a∗ with vector b∗ we are guaranteed to find a pair which is
approximately as close.

References
[ABV15]

Amir Abboud, Arturs Backurs, and Virginia Vassilevska
Williams. Tight hardness results for LCS and other sequence
similarity measures. In Proc. of the 56th FOCS, pages 59–78,
2015.

[AC14]

Sunil Arya and Timothy M. Chan. Better ǫ-dependencies for offline approximate nearest neighbor search, euclidean minimum
spanning trees, and ǫ-kernels. In 30th Annual Symposium on
Computational Geometry, SOCG’14, Kyoto, Japan, June 08 11, 2014, page 416, 2014.

[ACP08]

Alexandr Andoni, Dorian Croitoru, and Mihai Patrascu. Hardness of nearest neighbor under l-infinity. In Proc. of the 49th
FOCS, pages 424–433, 2008.

[ACW16]

Josh Alman, Timothy M. Chan, and R. Ryan Williams. Polynomial representations of threshold functions and algorithmic
applications. In IEEE 57th Annual Symposium on Foundations
of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt
Regency, New Brunswick, New Jersey, USA, pages 467–476,
2016.

[ADG+ 03]

Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk,
and Sofya Raskhodnikova. Lower bounds for embedding edit
distance into normed spaces. In Proc. of the 14th SODA, pages
523–526, 2003.

[AES91]

Pankaj K. Agarwal, Herbert Edelsbrunner, and Otfried
Schwarzkopf. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry,
6:407–422, 1991.

[AF03]

Sunil Arya and Ho-Yam Addy Fu. Expected-case complexity
of approximate nearest neighbor searching. SIAM J. Comput.,
32(3):793–815, 2003.

21

[Ahl17]

Thomas Dybdahl Ahle. Optimal las vegas locality sensitive
data structures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA,
October 15-17, 2017, pages 938–949, 2017.

[AI06]

Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.
In Proc. of the 47th FOCS, pages 459–468. IEEE, 2006.

[AIL+ 15]

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal lsh for
angular distance. In Advances in Neural Information Processing Systems, pages 1225–1233, 2015.

[AINR14]

Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proc. of the 25th
SODA, pages 1018–1028. SIAM, 2014.

[AIP06]

Alexandr Andoni, Piotr Indyk, and Mihai Patrascu. On the
optimality of the dimensionality reduction method. In Proc. of
the 47th FOCS, pages 449–458. IEEE, 2006.

[AJP10]

Alexandr Andoni, T. S. Jayram, and Mihai Patrascu. Lower
bounds for edit distance and product metrics via poincaré-type
inequalities. In Proc. of the 21st SODA, pages 184–192, 2010.

[AK07]

Alexandr Andoni and Robert Krauthgamer. The computational hardness of estimating edit distance [extended abstract].
In Proc. of the 48th FOCS, pages 724–734, 2007.

[ALM+ 98]

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan,
and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998.

[ALRW17]

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and
Erik Waingarten. Optimal hashing-based time-space trade-offs
for approximate near neighbors. In Proc. of the 28th SODA,
pages 47–66, 2017.

[AM93]

Sunil Arya and David M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the Fourth
Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas., pages 271–280,
1993.
22

[AMM09]

Sunil Arya, Theocharis Malamatos, and David M. Mount.
Space-time tradeoffs for approximate nearest neighbor searching. J. ACM, 57(1):1:1–1:54, 2009.

[AMN+ 94] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching. In Proceedings of the Fifth
Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25
January 1994, Arlington, Virginia., pages 573–582, 1994.
[AR15]

Alexandr Andoni and Ilya Razenshteyn.
Optimal datadependent hashing for approximate near neighbors. In Proc.
of the Forty-Seventh Annual ACM on Symposium on Theory
of Computing, pages 793–801. ACM, 2015.

[AR18]

Amir Abboud and Aviad Rubinstein. Fast and deterministic
constant factor approximation algorithms for LCS imply new
circuit lower bounds. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018,
Cambridge, MA, USA, pages 35:1–35:14, 2018.

[ARW17]

Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P.
In 58th IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017,
pages 25–36, 2017.

[AS98]

Sanjeev Arora and Shmuel Safra. Probabilistic checking of
proofs: A new characterization of NP. J. ACM, 45(1):70–122,
1998.

[AV15]

Amirali Abdullah and Suresh Venkatasubramanian. A directed isoperimetric inequality with application to bregman
near neighbor lower bounds. In Proc. of the 47th STOC, pages
509–518. ACM, 2015.

[AW09]

Scott Aaronson and Avi Wigderson. Algebrization: A new
barrier in complexity theory. TOCT, 1(1):2:1–2:54, 2009.

[AW15]

Josh Alman and Ryan Williams. Probabilistic polynomials and
hamming nearest neighbors. In Proc. of the 56th FOCS, pages
136–150. IEEE, 2015.

23

[BCG+ 17]

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive oracle proofs with
constant rate and query complexity. pages 40:1–40:15, 2017.

[BES06]

Tuğkan Batu, Funda Ergun, and Cenk Sahinalp. Oblivious
string embeddings and edit distance approximations. In Proc.
of the seventeenth annual ACM-SIAM symposium on Discrete
algorithm, pages 792–801. Society for Industrial and Applied
Mathematics, 2006.

[BI15]

Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be
Computed in Strongly Subquadratic Time (unless SETH is
false). In Proc. of the 47th Annual ACM SIGACT Symposium
on Theory of Computing (STOC), pages 51–58, 2015.

[BKK+ 16]

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and
Henning Stichtenoth. Constant rate pcps for circuit-sat with
sublinear query complexity. J. ACM, 63(4):32:1–32:57, 2016.

[BS76]

Jon Louis Bentley and Michael Ian Shamos. Divide-andconquer in multidimensional space. In Proceedings of the 8th
Annual ACM Symposium on Theory of Computing, May 3-5,
1976, Hershey, Pennsylvania, USA, pages 220–230, 1976.

[BT13]

Avraham Ben-Aroya and Amnon Ta-Shma. Constructing
small-bias sets from algebraic-geometric codes. Theory of Computing, 9:253–272, 2013.

[BYJKK04] Ziv Bar-Yossef, TS Jayram, Robert Krauthgamer, and Ravi
Kumar. Approximating edit distance efficiently. In Foundations
of Computer Science, 2004. Proceedings. 45th Annual IEEE
Symposium on, pages 550–559. IEEE, 2004.
[Cha17]

Timothy M. Chan. Orthogonal range searching in moderate
dimensions: k-d trees and range trees strike back. In 33rd
International Symposium on Computational Geometry, SoCG
2017, July 4-7, 2017, Brisbane, Australia, pages 27:1–27:15,
2017.

[Che18]

Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. Electronic Colloquium on
Computational Complexity (ECCC), 25:26, 2018.

24

[CLM18]

Karthik C.S., Bundit Laekhanukit, and Pasin Manurangsi. On
the parameterized complexity of approximating dominating set.
In STOC, 2018. To appear.

[CR10]

Amit Chakrabarti and Oded Regev. An optimal randomized cell probe lower bound for approximate nearest neighbor
searching. SIAM J. Comput., 39(5):1919–1940, 2010.

[CT13]

Gil Cohen and Amnon Ta-Shma. Pseudorandom generators
for low degree polynomials from algebraic geometry codes.
Electronic Colloquium on Computational Complexity (ECCC),
20:155, 2013.

[Din07]

Irit Dinur. The PCP theorem by gap amplification. J. ACM,
54(3):12, 2007.

[DKL16]

Roee David, Karthik C. S., and Bundit Laekhanukit. The curse
of medium dimension for geometric problems in almost every
norm. CoRR, abs/1608.03245, 2016.

[GBT84]

Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related techniques for geometry problems. In
Proceedings of the 16th Annual ACM Symposium on Theory of
Computing, April 30 - May 2, 1984, Washington, DC, USA,
pages 135–143, 1984.

[Gop81]

Valerii Denisovich Goppa. Codes on algebraic curves. Soviet
mathematics - Doklady, 24:170–172, 1981.

[GP08]

Venkatesan Guruswami and Anindya C. Patthak. Correlated algebraic-geometric codes: Improved list decoding over
bounded alphabets. Math. Comput., 77(261):447–473, 2008.

[GS99]

Venkatesan Guruswami and Madhu Sudan. Improved decoding
of reed-solomon and algebraic-geometry codes. IEEE Trans.
Information Theory, 45(6):1757–1767, 1999.

[GX13]

Venkatesan Guruswami and Chaoping Xing. List decoding
reed-solomon, algebraic-geometric, and gabidulin subcodes up
to the singleton bound. In Symposium on Theory of Computing
Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013,
pages 843–852, 2013.

25

[GX14]

Venkatesan Guruswami and Chaoping Xing. Optimal rate list
decoding of folded algebraic-geometric codes over constantsized alphabets. In Proceedings of the Twenty-Fifth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2014,
Portland, Oregon, USA, January 5-7, 2014, pages 1858–1866,
2014.

[HRW17]

Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local
list recovery of high-rate tensor codes and applications. CoRR,
abs/1706.03383, 2017.

[IM98]

Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. of
the thirtieth annual ACM symposium on Theory of computing,
pages 604–613. ACM, 1998.

[Ind99]

Piotr Indyk. A sublinear time approximation scheme for clustering in metric spaces. In 40th Annual Symposium on Foundations of Computer Science, FOCS, pages 154–159, 1999.

[Ind00]

Piotr Indyk. Dimensionality reduction techniques for proximity
problems. In Proc. of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 371–378, 2000.

[Ind03]

Piotr Indyk. Better algorithms for high-dimensional proximity
problems via asymmetric embeddings. In Proc. of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 539–545, 2003.

[Ind04]

Piotr Indyk. Approximate nearest neighbor under edit distance
via product metrics. In Proc. of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, SODA, pages 646–
650, 2004.

[IP01]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367–375, 2001.

[KKK16]

Matti Karppa, Petteri Kaski, and Jukka Kohonen. A faster subquadratic algorithm for finding outlier correlations. In Proc. of
the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1288–1305. Society for Industrial and
Applied Mathematics, 2016.

26

[Kla03]

Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10
July 2003, Aarhus, Denmark, pages 118–134, 2003.

[Kle97]

Jon M. Kleinberg. Two algorithms for nearest-neighbor search
in high dimensions. In Proceedings of the Twenty-Ninth Annual
ACM Symposium on the Theory of Computing, El Paso, Texas,
USA, May 4-6, 1997, pages 599–608, 1997.

[KM95]

Samir Khuller and Yossi Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34–
37, 1995.

[KN05]

Subhash Khot and Assaf Naor. Nonembeddability theorems
via fourier analysis. In Proc. of the 46th FOCS, pages 101–110.
IEEE, 2005.

[Kop13]

Swastik Kopparty. Lecture 5: k-wise independent hashing and
applications, 2013. Lecture notes for Topics in Complexity Theory and Pseudorandomness (Rutgers University ).

[KOR00]

Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient
search for approximate nearest neighbor in high dimensional
spaces. SIAM J. Comput., 30(2):457–474, 2000.

[KP12]

Michael Kapralov and Rina Panigrahy. Nns lower bounds via
metric expansion for l∞ and emd. In International Colloquium
on Automata, Languages, and Programming, pages 545–556.
Springer, 2012.

[LPY16]

Mingmou Liu, Xiaoyin Pan, and Yitong Yin. Randomized
approximate nearest neighbor search with limited adaptivity.
In Proceedings of the 28th ACM Symposium on Parallelism
in Algorithms and Architectures, SPAA 2016, Asilomar State
Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 23–33,
2016.

[Lue09]

George S. Lueker. Improved bounds on the average length of
longest common subsequences. J. ACM, 56(3):17:1–17:38, 2009.

[Mei13]

Or Meir. IP = PSPACE using error-correcting codes. SIAM J.
Comput., 42(1):380–403, 2013.
27

[MNP07]

Rajeev Motwani, Assaf Naor, and Rina Panigrahy. Lower
bounds on locality sensitive hashing. SIAM J. Discrete Math.,
21(4):930–935, 2007.

[New91]

Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett., 39(2):67–71, 1991.

[OR07]

Rafail Ostrovsky and Yuval Rabani. Low distortion embeddings
for edit distance. Journal of the ACM (JACM), 54(5):23, 2007.

[OWZ14]

Ryan O’Donnell, Yi Wu, and Yuan Zhou. Optimal lower
bounds for locality-sensitive hashing (except when q is tiny).
ACM Transactions on Computation Theory (TOCT), 6(1):5,
2014.

[PT07]

Mihai Patrascu and Mikkel Thorup. Randomization does
not help searching predecessors. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007,
pages 555–564, 2007.

[PTW08]

Rina Panigrahy, Kunal Talwar, and Udi Wieder. A geometric
approach to lower bounds for approximate near-neighbor search
and partial match. In Proc. of the 49th FOCS, pages 414–423.
IEEE, 2008.

[PTW10]

Rina Panigrahy, Kunal Talwar, and Udi Wieder. Lower bounds
on near neighbor search via metric expansion. In Proc. of the
51st FOCS, pages 805–814. IEEE, 2010.

[Raz17]

Ilya Razenshteyn. High-Dimensional Similarity Search and
Sketching: Algorithms and Hardness. PhD thesis, MIT, 2017.

[SAK+ 01]

Kenneth W. Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning
Stichtenoth, and Vinay Deolalikar. A low-complexity algorithm
for the construction of algebraic-geometric codes better than
the gilbert-varshamov bound. IEEE Trans. Information Theory, 47(6):2225–2241, 2001.

[SH75]

Michael Ian Shamos and Dan Hoey. Closest-point problems. In
16th Annual Symposium on Foundations of Computer Science,
Berkeley, California, USA, October 13-15, 1975, pages 151–
162, 1975.
28

[Sti09]

Henning Stichtenoth. Algebraic Function Fields and Codes,
chapter Algebraic Geometry Codes, pages 45–65. Springer
Berlin Heidelberg, Berlin, Heidelberg, 2009.

[Val15]

Gregory Valiant. Finding correlations in subquadratic time,
with applications to learning parities and the closest pair problem. Journal of the ACM (JACM), 62(2):13, 2015.

[Wil05]

R. Ryan Williams. A new algorithm for optimal 2-constraint
satisfaction and its implications. Theoretical Computer Science,
348(2–3):357–365, 2005.

[Wil18]

Ryan Williams. On the difference between closest, furthest, and
orthogonal pairs: Nearly-linear vs barely-subquadratic complexity. In Proceedings of the Twenty-Ninth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2018, New
Orleans, LA, USA, January 7-10, 2018, pages 1207–1215, 2018.

[WW10]

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.

29

