Authors Zeev Dvir, Shubhangi Saraf, Avi Wigderson,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36
www.theoryofcomputing.org
Superquadratic Lower Bound for 3-Query
Locally Correctable Codes over the Reals
Zeev Dvir∗ Shubhangi Saraf† Avi Wigderson‡
Received July 20, 2015; Revised March 20, 2017; Published October 23, 2017
Abstract: We prove that 3-query linear locally correctable codes of dimension d over the
reals require block length n > d 2+α for some fixed, positive α > 0. Geometrically, this
means that if n vectors in Rd are such that each vector is spanned by a linear number of
disjoint triples of others, then it must be that n > d 2+α . This improves the known quadratic
lower bounds (e. g., Kerenidis–de Wolf (2004), Woodruff (2007)). While the improvement
is modest, we expect that the new techniques introduced in this article will be useful for
further progress on lower bounds of locally correctable and decodable codes with more than
2 queries, possibly over other fields as well.
Several of the new ideas in the proof work over every field. At a high level, our proof has
two parts, clustering and random restriction.
The clustering step uses a powerful theorem of Barthe from convex geometry. It can be
used (after preprocessing our LCC to be balanced), to apply a basis change (and rescaling)
of the vectors, so that the resulting unit vectors become nearly isotropic. This together with
the fact that any LCC must have many “correlated” pairs of points, lets us deduce that the
An extended abstract of this paper appeared in the Proceedings of the Forty-sixth Annual ACM Symposium on Theory of
Computing 2014 [14].
∗ Supported by NSF CAREER award DMS-1451191 and NSF grant CCF-1523816.
† Supported by NSF grant CCF-1350572.
‡ Supported by NSF grant CCF-1412958.
ACM Classification: E.4
AMS Classification: 94B65, 52C35
Key words and phrases: coding theory, discrete geometry, combinatorics, lower bounds
© 2017 Zeev Dvir, Shubhangi Saraf, and Avi Wigderson
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a011
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
vectors must have a surprisingly strong geometric clustering, and hence also combinatorial
clustering with respect to the spanning triples.
In the restriction step, we devise a new variant of the dimension reduction technique used
in previous lower bounds, which is able to take advantage of the combinatorial clustering
structure above. The analysis of our random projection method reduces to a simple (weakly)
random graph process, and works over any field.
1 Introduction
Locally-correctable codes (sometimes under different names of program self-correctors or random self-
reductions), abbreviated LCCs, have the property that each symbol of a corrupted codeword can be
recovered, with high probability, by randomly accessing only a few other symbols. LCCs have played a
key role in important developments within several (impressively) diverse areas of theoretical computer
science, which we briefly summarize below.
Blum and Kannan [9] introduced the idea of probabilistic, local correction for the purpose of program
checking. With the follow-up papers [10] on linearity testing and [27] on low-degree testing this sequence
inaugurated the field of Property Testing and Sublinear Algorithms. The realization of [25, 7], that
Reed-Muller codes (namely low-degree multivariate polynomials) are locally correctable, gave the first
random self-reducibility examples of very hard functions like the Permament, and this average-case
to worst-case complexity reduction was useful for pseudo-random generators [4]. It further lead (with
many more ideas) to the celebrated sequence of characterizations of the power of probabilistic proofs,
IP = PSPACE by [26, 28], MIP = PSPACE by [3] and PCP = NP by [2, 1]. Close cousins of LCCs,
Locally-Decodable Codes (LDCs),1 formally introduced in [19] but having their origins in these earlier
works, were key to Private Information Retrieval and other models of secure delegation of computation
(see, e. g., [11]). Dvir [12] has shown that sufficiently strong lower bounds on LCCs would yield explicit
rigid matrices, which are related, via the work of Valiant [29] to circuit complexity.2 While this has not
materialized yet, it motivated the invention of multiplicity codes by [23] which are new LCCs of high
rate, and turn out to yield optimal list-decodable codes as well [22]. Finally, since the work of Dvir and
Shpilka [16], LDCs and LCCs have played a role in understanding basic problems in Polynomial Identity
Testing and established its connection to problems in Incidence Geometry, e. g., [20, 5, 15].
The most important parameters of LCCs are the number of queries, q, made by the correcting
algorithm, and the block length n as a function of the message length (or dimension, for linear codes) d,
where we fix corruptions to some small fixed fraction, say 1%. For upper bounds, the best constructions
we have are still based on Reed-Muller codes3 which exist only over finite fields. For q queries these
require block length about exp(d 1/(q−1) ). Indeed most applications require the block-length n to be
polynomial in d and hence using these codes forces the number of queries to be at least logarithmic.
1 In LDCs one needs to locally recover only d linearly independent coordinates (equivalently, the message) from the corrupted
codeword, rather than all n of them.
2 While the work of Kopparty, Saraf, and Yekhanin shows that, over small finite fields, this approach could not give superlinear
circuit lower bounds, the approach might still be valid over large fields.
3 For the weaker LDCs there are far better constructions, based on the work of Yekhanin and Efremenko [32, 17, 13], but
these are not known to be locally correctable.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 2
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Finding better codes, and in particular constant-query, polynomial block-length LCCs, has been a major
challenge, and this challenge naturally turns attention to the limits of constant query LCCs and LDCs.
On the lower bound front, relatively little is known to rule out the feasibility of the challenge above.
We shall restrict ourselves to linear codes4 over a field F, namely when the set of codewords is a subspace
of Fn of dimension d. We will denote by q-LCC such a linear locally-correctable codes with q queries. It
is easy to see that 1-LCCs do not exist over any field. The first set of interesting results came for 2-LCCs,
and here strong lower bounds are known through a variety of techniques. An exponential n > 2Ω(d) lower
bound via isoperimetric/entropy methods for 2-LCCs over F2 follows from the same methods as for the
(weaker) LDCs [18, 21, 16] and is matched by the Hadamard code whose generating matrix is composed
of all binary vectors over F2 . Strangely, while these vectors provide an LDC over every field, they fail to
be an LCC except over F2 . This gap was first explained in [5, 15] where the authors showed that over the
real numbers (and indeed even over large enough finite fields), 2-LCCs simply do not exist! For every
error-rate δ the dimension d for which such codes exist is finite, and cannot exceed poly(1/δ ). The proofs
here use a combination of geometric, analytic and linear-algebraic techniques, and give quantitative form
to known qualitative point-line incidence theorems. Tighter bounds of n > pΩ(d) over finite fields of
prime order p were proved in [8] using methods from arithmetic combinatorics, matching the trivial
construction of taking all vectors in (Fq )d .
For q ≥ 3 the known lower bounds are far weaker, and practically only one lower-bound technique is
known: random restrictions of the given code which reduce the number of queries q to 2 or 1, appealing
to the lower bounds above. This technique was introduced for LDCs by Katz and Trevisan [19]. The
resulting lower bounds trivially hold for (the stronger) LCCs as well. The best bounds known are due
to [21, 30], which show that linear q-LDCs, over any field F, must satisfy n = Ω(d e 1+1/(dq/2e−1) ) for every
q ≥ 3. So, in particular, the best lower bound for 3-LDCs (or LCCs) is quadratic, n = Ω(d e 2 ). (For linear
codes the Ω was replaced by Ω in [31].) Our main result is breaking this quadratic barrier for 3-LCCs
e
over the real numbers. Over the reals there are no known constructions of constant-query LCCs (of any
rate!). We prove that for some fixed constant5 α > 0 every linear 3-LCC over the reals must satisfy
n = Ω(n2+α ), even when the error parameter δ is allowed to be polynomially small in n. To this end, we
introduce several new ideas and techniques, which we hope will lead to further progress. Some of our
ideas are general enough to work over any field, while others are specifically tailored for the reals. We
briefly discuss now the main sources for our improvement over the known quadratic lower bound. A
more detailed overview of the proof is given after the formal statement of the theorem in the next section.
1.1 Clustering and restrictions
A linear 3-LCC of dimension d and block length n over F may be viewed as a set V ⊂ Fd of n vectors
(which form the generating matrix of the code), together with n collections Mv , one for each v ∈ V . Each
Mv is a matching of δ n disjoint triples from V , and each of the triples in Mv spans v. This structure is
easy to deduce for linear codes from the more traditional definition using a randomized decoder (cf.
Definition 2.1).
We now informally describe a way to obtain a possible quadratic lower bound on n, which uses
4 Some of the results below are known also for non-linear codes.
5 We did not make an attempt to optimize the constant α, but the proof gives some α > .01.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 3
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
√
random restriction to reduce the dimension of the code. Pick a set A ⊂ V of size about n at random.
Then, take a linear projection whose kernel is exactly the span of the vectors in A and apply it to the
elements of V . Notice that in expectation, for every v ∈ V , a pair of points in A will be contained in some
triple in Mv . Thus, after the projection the third point in that triple will become the same as v (up to
scaling). As this happens to every point, we expect V to shrink by a factor of 2! Notice that in such a
√
projection, the dimension of V can drop by at most |A| ≈ n. Repeating this process logarithmically
many times will shrink V completely, revealing that its original dimension could not have been larger
√
than n log n, giving a near quadratic relation n ≥ d 2 / log d. We note that the proofs appearing in the
literature are somewhat different then the one we just described. Indeed, there are several possible ways
of using a random restriction argument to get a quadratic bound (up to poly-logarithmic factors) for linear
3-LCCs. The argument above is new to this paper, and is indeed a simplified variant of our actual proof,
which improves its analysis over the reals.
It is not hard to see that if the collection of triples in all of matchings Mv were chosen at random, the
analysis above could not be improved. But a random collection is far from being an LCC. Indeed, in
contrast to standard codes, which exist in abundance and a random subspace is one with high probability,
locally correctable (or decodable, or testable) codes are extremely rare and structured. This raises the
question of what other structural properties are imposed on the matchings Mv in an LCC. In this paper we
reveal a new such property, clustering, at least when the underlying field is the reals.6 We conclude with
a simplified description of this clustering property, how it is obtained, and how it enables better analysis
of the random restriction process.
√
A collection {Mv } of matchings of triples is said to be clustered if there are about n subsets
√
S1 , . . . , S√n of V , each of size about n, such that every triple in every matching Mv has a pair in one of
these sets. Note that such a configuration is extremely far from random. Indeed, as these sets have at most
n3/2 pairs between them, many of the triples (of different matchings) share pairs (a typical pair exists in
√
about n triples!). Note that this cluster structure is completely combinatorially described.
Why should the triples in a 3-LCC admit such a clustering? The main observation is that, over the
reals, a small linearly dependent subset, such as a 4-tuple composed of v and a triple from Mv , must
contain a pair which is significantly correlated (say, with inner product at least 1/4 for said example).
Thus, a 3-LCC must contain many correlated pairs. On the other hand, a powerful result of Barthe from
convex geometry allows us to deduce that, after a carefully chosen change of basis, the vectors of our
code are almost isotropic, meaning that they point roughly equally in all directions in space. This implies
that most pairs are hardly correlated at all. These two seemingly contradicting structures can exist only
if the points in V are geometrically clustered. Delicate analysis shows that they can be partitioned into
√
roughly n small balls. The correlations then must arise from triples containing a pair in one of the
(geometric) clusters.
Why does clustering help? Let us return to the random restriction and projection argument above,
but let us pick now the set A as follows. First pick one of the clusters Si uniformly at random, and
inside it pick A at random of size about n1/4 . The clustering ensures that this much smaller set has a pair
intersecting each of the matchings Mv in expectation (due to the fact that a typical pair in a typical cluster
√
participates in n matchings). So a much smaller set A suffices to create the same effect after projection,
namely a shrinking of the set V by a factor of 2. Again a logarithmic number of such restrictions is
6 The actual proof requires several extra conditions on the code, which can be obtained via a sequence of reductions.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 4
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
likely to shrink V completely, giving a dimension upper bound of n1/4 log n, and yielding the lower bound
n ≥ d 4 / log d. We note again that this part works over any field, as long as the triples are clustered.
“Balanced” codes. A recurring notion in our proof is that of an LCC in which no large subset of the
coordinates lies in a subspace of significantly lower dimension. One can think of such codes as being
“balanced” in the sense that they cannot be “compressed” (by projecting the large set of low dimension to
zero). Our proof contains a sequence of reductions, used to obtain certain conditions that are used in the
clustering and restriction steps. Each of these reductions can only be carried out if the code is “balanced”
and this property is used in several different ways in the proof. If the code is not “balanced” we can use
an iterative argument that projects the large low-dimensional subset to zero. We find this condition of
being balanced a very natural one in the context of LCCs (and other codes) and hope it could be useful as
a conceptual tool in future works.
Organization. In Section 2 we state our results formally. Then, in Section 3 we provide a more detailed
and technical overview of the proof. The organization of the rest of the paper (which contains a complete
proof of our main result) is given at the end of Section 3.
Acknowledgments. We thank the anonymous referees for their careful reading of the paper and for
many useful comments. We are grateful to Boaz Barak, Moritz Hardt and Amir Shpilka for their
contribution in early stages of this work. In particular, we thank Moritz Hardt for introducing us to
Barthe’s work.
2 Definitions and results
For a string y ∈ Fn , we define w(y) to be the number of nonzero entries in y. A q-matching M in [n] is
defined to be a set of disjoint unordered q-tuples (i. e., disjoint subsets of size q) of [n].
Definition 2.1 (Linear q-LCC, decoder definition). A linear (q, δ )-LCC of dimension d over a field
F is a d-dimensional linear subspace U ⊂ Fn such that there exists a randomized decoding procedure
D : Fn × [n] → F with the following properties.
1. For all x ∈ U, for all i ∈ [n] and for all y ∈ Fn with w(y) ≤ δ n we have that D (x + y, i) = xi with
probability at least 3/4 (the probability is taken only over the internal randomness of D).
2. For every y ∈ Fn and i ∈ [n], the decoder D(y, i) reads at most q positions in y.
Definition 2.2 (Linear q-LCC, geometric definition). Let V = (v1 , . . . , vn ) ∈ (Fd )n be a list of n vectors
spanning Fd . We say that V is a linear (q, δ )-LCC in geometric form if for every v ∈ V there exists
a q-matching Mv in [n] of size at least δ n such that for every q-tuple { j1 , . . . , jq } ∈ Mv it holds that
v ∈ span{v j1 , . . . , v jq }.
It is well known that any linear (q, δ )-LCC (over any field) can be converted into the geometric form
given above by replacing δ with δ /q. The transformation is simple. take v1 , . . . , vn ∈ Fd to be the rows of
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 5
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
the generating matrix of U. Clearly, this does not change the dimension of the code. This is surprising
since it implies also that the decoder in the first definition can be made non adaptive without much loss in
parameters (for linear codes).
In our results we will assume that the error parameter δ is not too small as a function of n. Specifically,
we will require that n ≥ (1/δ )ω(1) . This condition can be replaced with n ≥ (1/δ )C for a sufficiently
large absolute constant C which can be calculated from the proof.
We now state our main result which bounds the dimension of 3 query LCC’s when the underlying
field is R.
Theorem 2.3 (Main Theorem). There exists an absolute constant ε > 0 such that if V = (v1 , . . . , vn ) ∈
(Rd )n is a linear (3, δ )-LCC and n ≥ (1/δ )ω(1) , then
d = dim(V ) ≤ n1/2−ε .
3 Proof overview: “Cluster and Restrict” method
From a high level, our proof is divided into two conceptually distinct steps.
1. Clustering step. Show that the triples used in the matchings Mv , v ∈ V are “clustered” in some
precise sense (described below).
2. Restriction step. Use the clustering to find a large subset of V that has low dimension. The name of
this step is due to the fact that it uses a random restriction argument (projecting a random subset to
zero).
Combining these two steps (in Lemma 10.1) we get that V must have a large subset (of size Ω(n)) with
low dimension (at most n1/2−ε ). Using this to prove a global dimension bound on V (as in Theorem 2.3)
is done using a standard amplification lemma (Lemma 10.2) similar to that in [5, 8]. For simplicity, we
will use big “O” notation to hide constants depending on δ (only for this overview).
We now describe each of these steps in more detail. The fact that V is a code over R is only used
in the clustering step. The restriction step works over any field, provided that the triples are already
clustered. A recurring theme in the proof is that we are always free to assume that V does not have a
large subset of low dimension. Another recurring operation is “sending a subset U of V to zero.” By this
statement we mean: pick a linear map A whose kernel is span(U) and apply it to all the elements of V .
We will use the simple fact that, if dim(U) = r and dim(V ) = d then dim(A(V )) is at least d − r, where
A(V ) is the list of vectors A(v), v ∈ V .
The clustering step is given by Lemma 8.2 which we state now in an informal form. We will elaborate
below on the two conditions appearing in the lemma (the well-spread vectors condition and the low
triple-multiplicity condition). Recall that V is associated with n 3-matchings Mv , v ∈ V used in the
decoding.
Lemma 3.1 (Informal statement of Lemma 8.2). Suppose V is a (3, δ )-LCC that satisfies the well-spread
vectors condition and the low triple-multiplicity condition and suppose that d > n1/2−ε . Then there are
subsets S1 , . . . , Sm ⊂ V (not necessarily disjoint) so that
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 6
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
1. for each i ∈ [m], |Si | ≤ O(n1/2+ε );
2. Ω(n1/2−ε ) ≤ m ≤ O(n1/2+ε );
3. each triple in each matching Mv has two of its elements in one of the sets Si .
Before we explain the two conditions in the lemma, i. e., the well-spread vectors condition and the
low triple-multiplicity condition, notice that the existence of sets S1 , . . . , Sm as above is something that
does not hold for a “typical” family of Ω(n2 ) triples. In fact, if the triples were chosen at random there
would not be such sets with probability close to one. Referring to the sets Si as “clusters” is also justified
by the fact that they actually form clusters in Rd (i. e., they are all correlated with some fixed point). This
geometric fact, however, is not used anywhere in the proof—all we need is the combinatorial structure.
We now explain the two conditions on the code V mentioned in the lemma.
• Well-spread vectors condition. The vectors v1 , . . . , vn comprising V should be is some sense well
spread. Observe that w. l. o. g. by a suitable scaling to each vector, we can assume that the vectors
v1 , . . . , vn are unit vectors, and we will make this assumption. Formally, we require that for every
unit vector w ∈ Rd we have ∑i∈[n] hvi , wi2 ≤ O(n1/2+ε ). This means, in particular, that every small
ball can contain at most O(n1/2+ε ) vectors. Clearly, a general LCC V does not need to satisfy this
condition. For example, if V has a large subset of low rank such a statement cannot hold (using a
pigeon hole argument on the unit sphere in low dimension). We are able, however, to reduce to
this case using Lemma 6.1, which uses a powerful result of Barthe (Lemma 5.1) that is developed
in Section 5. Roughly speaking, Barthe’s theorem can be used to show that, unless V has a large
subset of low rank there is an invertible linear map M on Rd so that, if we replace each vi with
Mvi /kMvi k, the well-spread vectors condition is satisfied. The proof of this result (part of which
appear in Section 5) uses tools from convex geometry. We derive a particularly convenient form of
Barthe’s theorem as Theorem 6.4 which might be of independent interest.
• Low triple-multiplicity condition. This condition requires that a single triple does not appear in
“too many” (roughly nO(ε) ) different matchings. In Section 7 we prove Lemma 7.2 which shows
how to reduce to this case, assuming V does not have a large subset of low rank. The reduction
uses the fact that if a single triple is used in too many matchings, then projecting the elements in
this triple to zero causes many other points to go to zero. If a point v is mapped to zero as a result,
and if v is used in many triples (say Ω(n)) all of these triples “become” pairs when v maps to zero.
Using this observation, we show that we can send a relatively small number of points to zero and
construct a 2-query locally decodable code (LDC) of relatively high dimension. We then apply the
known bounds for 2-query LDCs (these are variants of LCCs and described in Section 4) to get a
contradiction. This reduction is also field independent and does not use any properties of the real
numbers.
The main observation leading to clustering is that we can assume, w. l. o. g., that all triples (i, j, k) ∈ Mv
are so that the three vectors vi , v j , vk are almost orthogonal to v. This follows directly from the well-spread
vectors condition by bounding from above the number of vectors correlating with v and discarding the
corresponding triples from Mv (for each v ∈ V ). Once we have this condition, we observe that since
v, vi , v j , vk are linearly dependent and, since v is not correlated with the other three vectors, we must have
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 7
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
that vi , v j , vk are close to being in a two dimensional plane. (Recall that these are all unit vectors.) This
means that in each triple there must be two elements that are correlated with each other! This is already a
non trivial fact, in particular since we know (by the well-spread vectors condition) that each point cannot
be correlated with many other points.
Proceeding with a more careful analysis of the different types of triples that can arise, and using
some graph theoretic arguments, we arrive at the required clusters. In this step we use the bound on the
maximum triple-multiplicity.
Note that the clustering lemma implies that there are many pairs in V ×V that appear in many triples.
This is due to the simple upper bound of n1.5+O(ε) on the total number of possible pairs in all of the
clusters S1 , . . . , Sm and the fact that together they cover pairs from a quadratic number of triples. This
should be contrasted with the results of [5, 15] which prove strong lower bounds for q-LCC’s (for any
constant q) in which every pair is in a bounded number of triples (these are called “design” LCCs).
3.1 Restriction step
The restriction step (given in Lemma 9.1) shows that if V satisfies the clustering condition (given in
Lemma 8.2) then it contains a large subset of low rank. We now state a simplified form of this lemma.7
Lemma 3.2 (Informal statement of Lemma 9.1). Let F be a field. Let V = (v1 , . . . , vn ) ∈ (Fd )n be a (3, δ )-
LCC with matchings Mv , v ∈ V . Suppose there exist sets S1 , . . . , Sm ⊂ [n] as in Lemma 8.2, clustering the
triples in the matchings Mv . Then, there is a subset V 0 ⊂ V of size |V 0 | ≥ (δ /2)n and dimension at most
n1/2−ε .
This step is called the “restriction step” since it uses the “clusters” S1 , . . . , Sm found in the clustering
step to show (Lemma 9.2) that there is a small set U ⊂ V (of size roughly n1/4+7ε ) such that, projecting
all elements of U to zero, reduces the dimension of V to at most n10ε . This will imply a dimension bound
of n1/4+7ε + n10ε on the initial dimension of V . (The reason we do not get a n1/4+7ε upper bound on the
dimension of V is due to the clustering step.)
The starting point for the proof of this lemma is the following simple observation. If v is spanned by a
triple (vi , v j , vk ), then projecting two elements of that triple, say vi , v j , to zero makes the two vectors v, vk
proportional to each other. (This uses the fact that v is not spanned by any proper subset of the triple, and
we can easily reduce to this case.) Now, suppose that there are t triples in the code that have at least two
element in U. Then projecting U to zero makes makes t pairs of vectors proportional to each other (as in
the v, vk example). Consider the graph on vertex set V in which we add an edge for each proportional
pair v, vk obtained by sending a pair vi , v j ∈ U in a triple (vi , v j , vk ) ∈ Mv to zero. Since the property of
being proportional to each other is an equivalence relation on Rd , we can bound the dimension of V after
projecting U to zero by the number of connected components of the graph.
This leaves us with the task of finding a set U so that the resulting graph has at most n10ε components.
To find such a U we use a probabilistic argument. We will pick U at random according to a particular
distribution and then argue that the expected number of connected components is small. To pick the
random U we proceed in r ∼ n4ε steps as follows. In each step pick one of the clusters Si at random and
7 One should not expect things to get better the larger ε is (as this lemma might suggest) since the condition d > n1/2−ε
appearing in the clustering lemma prevents ε from being too large.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 8
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
then pick a random subset of Si of size ∼ n1/4+3ε . The union of these sets will be U. The upper bound on
the expected number of components is derived by considering the (expected) reduction in the number of
connected components in each of the r steps. Consider some connected component and let v be some
vector in it. We can assume the component is not too large, since the number of large components is
trivially bounded (large being close to n1−ε ). Since each Mv is a matching, the random choice of the
vectors in the i’th step will (with good probability) add an edge to v with a neighbor that is not likely to
land in the connected component containing v. Hence, with good probability the connected component
will “merge” with another component. Carefully analyzing this process gives us the required bound.
3.2 Organization
We begin with some general preliminaries and notation in Section 4. In Section 5 we describe (and sketch
the proof of) Barthe’s theorem which is used in Section 6 to reduce to the case that the points in V are
well-spread. In Section 7 we show how to reduce to the case that V has low triple multiplicities. Section 8
contains the proof of the clustering step and Section 9 contains the proof of the restriction step. Finally,
in Section 10 we show how to put all the ingredients together and prove Theorem 2.3.
4 General preliminaries
4.1 Choice of notation
Lists vs. multisets. The reason we are treating V as a list and not as a set is that V might have repetitions.
For instance u and v might be distinct elements in the list V , but might correspond to the same vector in
Fd . The repetition corresponds to the fact that there might be repeated columns in the generator matrix
of the code, which may potentially make the property of local correction easier to satisfy. Indeed in the
recent lower bounds for 2-query LCCs [8, 5], handling the fact that there might be repetitions added
significant complexity to the proofs of the lower bounds. In the current paper too we deal with repetitions
by treating V as a list. An equivalent treatment would be to treat V as a multiset, and we make no
distinction between these notions. We think of a multiset as an ordered list of elements which might
contain repeated elements. If A is a multiset/list, we call B a subset of A if B is another multiset/list
obtained by taking a subset of A. We will say that B and C are disjoint subsets of A if they are both
obtained from sub-lists on disjoint subsets of the indices. When referring to the size of a multiset we will
always count the number of elements with multiplicities (unless we state explicitly that we are counting
distinct elements).
Although we defined a matching to be a set of tuples in [n], when we are dealing with a specific list
V = (v1 , . . . , vn ), we might identify a tuple ( j1 , . . . , jq ) of a matching with the tuple (v j1 , . . . , v jq ), and we
use these two notions interchangeably. Moreover, a matching Mv denotes the matching corresponding to
a particular element v ∈ V , and if u and v are different elements of V , even if they correspond to the same
vector in Fd , then Mu and Mv could be different matchings.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 9
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
4.2 Basic operations on LCCs
For a list V ∈ (Rd )n we denote by span(V ) the subspace spanned by elements of V and by dim(V ) the
dimension of this span.
The following simple observation shows that a sufficiently large subset of an LCC is also an LCC.
Claim 4.1. If V = (v1 , . . . , vn ) ∈ (Fd )n is a (3, δ )-LCC and U ⊂ V is of size |U| ≥ (1 − δ /2)n then U
is a (3, δ /2)-LCC of the same dimension as V . Moreover, if Mv , v ∈ V are any matchings used in the
decoding of V then we can take the matchings for the new code U to be subsets of the old matchings.
Proof. Observe that in each matching Mv , there are at most (δ /2)n triples that contain an element outside
U. Thus, in U we could construct matchings of size (δ /2)n ≥ (δ /2)|U|. The claim about the dimension
follows from the fact that U contains triples spanning all of the elements of V (not just those in U).
Another simple observation is that applying an invertible linear map to the elements of V preserves
the property of being an LCC.
Observation 4.2. If V = (v1 , . . . , vn ) ∈ (Rd )n is a (3, δ )-LCC then, for any invertible linear map M :
Rd → Rd the list V̂ = (v̂1 , . . . , v̂n ) ∈ (Rd )n , with v̂ j = Mv j /kMv j k, is also a (3, δ )-LCC.
4.3 Lower bounds for 2-query LDCs
One of the ingredients in the proof will be a strong (exponential) lower bound on the length of linear
2-query Locally Decodable Codes (LDCs), which are weaker versions of LCCs. As with LCCs there are
two ways of defining LDCs.
Definition 4.3 (linear q-LDC, decoder definition). A linear (q, δ )-LDC over a field F is a linear d-
dimensional subspace U ⊂ Fn , and a set of d coordinates j1 , j2 , . . . jd ∈ [n] such that the projection of U
on to those d coordinates is full dimensional,8 and such that there exists a randomized decoding procedure
D : Fn × [d] → F with the following properties:
1. For all x ∈ U, for all i ∈ [d] and for all y ∈ Fn with w(y) ≤ δ n we have that D (x + y, i) = x ji with
probability at least 3/4. (The probability is taken only over the internal randomness of D.)
2. For every y ∈ Fn and i ∈ [d], the decoder D(y, i) reads at most q positions in y.
Let {e1 , e2 , . . . , ed } be the set of standard basis vectors in Rd .
As with LCCs, taking the rows of the generating matrix (and possibly applying an invertible linear
map that sends them to the ei s) allows us to move to the geometric form. This might require us to replace
δ with δ /q.
Definition 4.4 (linear q-LDC, geometric definition). Let V = (v1 , . . . , vn ) ∈ (Fd )n be a list of n vectors
spanning Fd . We say that V is a linear (q, δ )-LDC in geometric form if for every i ∈ [d] there exists a
q-matching Mi in [n] of size at least δ n such that for every q-tuple {v j1 , v j2 , . . . , v jq } ∈ Mi it holds that
ei ∈ span{v j1 , v j2 , . . . , v jq }. We denote by d = dim(V ).
8 If the LDC was systematic, then the first d coordinates would suffice.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 10
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Theorem 4.5 (lower bounds for 2-LDC [16]). Let δ ∈ [0, 1], F be a field, and let V = (v1 , . . . , vn ) ∈ (Fd )n
be a linear (2, δ )-LDC in geometric form. Then
δd
n ≥ 2 16 −1 .
4.4 Codes in regular form
In the restriction step, it is convenient for us to assume that for each triple (vi , v j , vk ) ∈ Mv each element
of the triple is “used” in decoding to v. Indeed in Claim 4.7, we show how we can easily reduce to this
case provided that no large subset of V has low rank. More precisely, for x, y, z ∈ Rd , let us denote by
span∗ {x, y, z} the set of all elements of the form αx + β y + γz with α, β , γ ∈ R, such that α, β , γ are all
nonzero.
Definition 4.6. Let V = (v1 , . . . , vn ) ∈ (Fd )n be a (3, δ )-LCC with decoding matchings Mv , v ∈ V . We
say that V (with these matchings) is in regular form if, in each triple (x, y, z) ∈ Mv we have that v ∈
span∗ {x, y, z}.
Claim 4.7. Let V = (v1 , . . . , vn ) ∈ (Fd )n be a (3, δ )-LCC so that every subset U ⊂ V of size |U| ≥ (δ /2)n
has dimension at least ω((1/δ ) log(n)). Then, there exists a (3, δ /4)-LCC V 0 ⊂ V of size n0 ≥ (1−δ /2)n,
and dimension d 0 = d, that is in regular form. Moreover, given any matchings Mv for the code V we can
take the new (regular) matchings Mv0 for V 0 to be sub-matchings of the original ones.
Proof. Call a triple (x, y, z) ∈ Mv bad if there is a proper subset of it that spans v, i. e., v 6∈ span∗ {x, y, z}. If
there were (δ /2)n points v ∈ V , each with at least (δ /10)n bad triples in Mv , then we could use these bad
triples to construct a (2, δ /10)-LDC of size less than n decoding ω((1/δ ) log(n)) linearly independent
elements of V . This would give a contradiction using Theorem 4.5 and the assumption on the dimension
of any set of size (δ /2)n in V . Therefore, there are at most (δ /2)n points v ∈ V with many (at least
(δ /10)n) bad triples. Throwing away this set, and removing all triples containing them (as well as all bad
triples from the other matchings) gives us the code V 0 a required (as in Claim 4.1).
5 Barthe’s theorem
The main purpose of this section is to derive Lemma 5.1, a result of F. Barthe [6] which, given a set of
points sufficiently close to being in general position, finds a linear transformation that “moves” these points
so that their “directions” point in a close to uniform way. More precisely, for a set U = (u1 , . . . , un ) ∈ (Rd )n
let B(U) be the set of all subsets of [n] of size d such that the corresponding vectors of U form a basis
of Rd . Suppose that there is a distribution µ supported on B(U) such that when sampling a random
basis from µ, each element of U is chosen with some good probability. Then there is an invertible linear
transformation such that after normalizing, the new points are “approximately isotropic.” This result is
formalized in Lemma 5.1 which we state below.
Lemma 5.1. Let U = (u1 , . . . , un ) ∈ (Rd )n . Let S ⊆ [n], and suppose µ is a distribution supported on
B(U) such that for all j ∈ S
α ≤ Pr [ j ∈ I] .
I∼µ
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 11
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Then, there exists an invertible linear map M : Rd → Rd so that, denoting û j = Mu j /kMu j k, we have for
all unit vectors w ∈ Rd
2
∑ hû j , wi2 ≤ α .
j∈S
Observe that if the vectors are in general position then the uniform distribution on distinct d-tuples
gives α = d/n, in which case we would get
2n
∑ hû j , wi2 ≤ d .
j∈[n]
One can just assume the lemma above which follows in a straightforward way from from [6], and
skip to the next section. However for completeness, we present a proof here. Before we give the proof,
we first set up some notation.
For a finite set S, a distribution supported on S is a function µ : S → [0, 1] so that ∑x∈S µ(x) = 1.
For two vectors u, v ∈ Rd we denote by u ⊗ v the tensor product of u and v, namely the d × d matrix
with entries Ai j = ui v j . We denote by Id×d the d × d identity matrix. For u ∈ Rd we denote by kuk the
Euclidean (or `2 ) norm.
Definition 5.2 (B(U), K(U)). Let U = (u1 , . . . , un ) ∈ (Rd )n be a list of n points. Let I ⊆ [n]. We denote
by UI = (ui )i∈I the sub-list of U with indices in I. We denote by
B(U) = {I ⊂ [n] | UI is a basis of Rd }
the set of index sets corresponding to sub-lists of U of length d which are linearly independent (and so
span Rd ). For each I ⊂ [n] we let 1I ∈ Rn denote the indicator vector of the set I. Finally we denote by
K(U) ⊂ Rn the convex hull of the vectors 1I for all I ∈ B(U). We denote by K(U)o the relative interior
of K(U).9
Claim 5.3 (Properties of K(U)). Let U = (u1 , . . . , un ) ∈ (Rd )n be a list of n points spanning Rd . Let µ
be a distribution supported on B(U). For each j ∈ [n], let γ j ∈ [0, 1] be the probability that j ∈ I, when
I ⊂ [n] is sampled according to µ. Then γ = (γ1 , . . . , γn ) is in K(U).
Proof. The vector γ is easily seen to be equal to the convex combination
∑ µ(I) · 1I .
I∈B(U)
Theorem 5.4 ([6]). Let U = (u1 , . . . , un ) ∈ (Rd )n be a list of n points spanning Rd and let
γ = (γ1 , . . . , γn ) ∈ K(U)o .
Then there exists a real invertible d × d matrix M such that, denoting û j = Mu j /kMu j k, we have
n
∑ γ j · (û j ⊗ û j ) = Id×d . (5.1)
j=1
9 The relative interior of a set is a subset of the points of the set that are not on the boundary of the set, relative to the smallest
subspace containing the set.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 12
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Proof. We will show how the proof follows from one of the propositions proved in [6] (whose proof we
will not repeat here). The idea is to define a certain optimization problem parametrized by γ and to show
that the maximum is achieved for all γ ∈ K(U). Then, the matrix M will arise from equating the gradient
to zero at the maximum and solving the resulting equations.
We start by defining the optimization problem. For t ∈ Rn we define
n
X = X(t) = ∑ et j · (u j ⊗ u j ) .
j=1
Notice that X(t) has a positive determinant for all t ∈ Rn , since U spans Rd . Let f : Rn × Rn → R be
defined as
f (γ,t) = hγ,ti − ln det(X(t)) .
The optimization problem is defined as
φ ∗ (γ) = sup f (γ,t) .
t∈Rn
We now state a claim from [6] which gives sufficient conditions for the supremum φ ∗ (γ) to be realized.
Claim 5.5 (Rephrased from Proposition 6 in [6]). If γ ∈ K(U)o then the supremum φ ∗ (γ) is achieved.
That is, there exists t ∗ ∈ Rn such that f (γ,t ∗ ) = φ ∗ (γ).
Let t ∗ ∈ Rn be a maximizer given by the claim. We can now use the fact that the partial derivatives
∂ f (γ,t)
∂t j
all vanish at the point t ∗ . Recall that
d −1 d
ln det(A) = tr A A
ds ds
at all points where A is invertible [24, Ch. 9, Thm. 4]. Taking the derivative of f at t ∗ then gives
∂ f (γ,t) ∗ ∗
0= (t ) = γ j − tr X(t ∗ )−1 et j (u j ⊗ u j ) .
∂t j
Since X(t ∗ )−1 is positive definite, there exists a symmetric matrix M so that M 2 = X(t ∗ )−1 . Plugging this
into the last equation and using properties of the trace function, we get
∗
0 = γ j − et j kMu j k2 .
This means that
n n
−2 ∗ γj uj uj
M = X(t ) = ∑ 2
· (u j ⊗ u j ) = ∑ γ j · ⊗ .
j=1 kMu j k j=1 kMu j k kMu j k
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 13
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Multiplying by M from both sides we get
n
Mu j Mu j
Id×d = ∑ γ j · ⊗
j=1 kMu j k kMu j k
as was required.
Proof of Lemma 5.1. Let γ ∈ Rn be such that γ j = PrI∼µ [ j ∈ I] for all j ∈ [n]. By Claim 5.3, γ ∈ K(U).
This means we can find γ 0 ∈ K(U)o of distance at most ε from γ for all ε > 0. Hence, we can choose ε
sufficiently small so that α/2 ≤ γ 0j for all j ∈ S. Using Theorem 5.4 we get that there exists an invertible
M so that
n
Id×d = ∑ γ 0j · (û j ⊗ û j ) .
j=1
Multiplying by the column vector w from the left and by the row vector wt from the right we get that
n
1 = hw, wi = ∑ γ 0j hû j , wi2 ≥ (α/2) ∑ hû j , wi2 .
j=1 j∈S
This completes the proof.
6 Reducing to the well-spread vectors case
In this section we prove a lemma saying that, when analyzing an LCC V = (v1 , . . . , vn ) over R, we
can assume that the elements of V are unit vectors pointing in well-spread directions. The notion of
well-spread vectors that we use is that given by Barthe’s theorem (Lemma 5.1). More formally, the lemma
will say that any list of vectors can be transformed into a list that is well spread as long as it does not
contain a large subset of low rank. We formalize this result in Theorem 6.4. Below we state a lemma
which basically follows as a corollary of the above theorem when the original list of vectors is an LCC.
We first state and prove this lemma.
Lemma 6.1. Let V = (v1 , . . . , vn ) ∈ (Rd )n be a (3, δ )-LCC be such that any subset V 0 ⊂ V with |V 0 | ≥
(δ /4)n satisfies dim(V 0 ) > 4β d. Then, there exists a subset U = (u1 , . . . , un0 ) ⊂ V that is a (3, δ /2)-LCC
with |U| = n0 ≥ (1−δ /2)n, and an invertible linear map M : Rd → Rd so that, denoting û j = Mu j /kMu j k,
we have for all unit vectors w ∈ Rd .
n
∑0 hû j , wi2 ≤ β d .
j∈[n ]
Recall that (Observation 4.2) applying an invertible linear map to the elements of an LCC V preserves
the property of being an LCC. Hence, if we are aiming to prove that a (3, δ )-LCC V has a large subset of
low rank we could use Lemma 6.1 to reduce to the case that the points of V are well spread.
We will prove Lemma 6.1 using Lemma 5.1. Recall that, Lemma 5.1 provides us with sufficient
conditions under which a linear map M as in the lemma exists. Namely, that there exists a distribution µ
on spanning d-tuples of V which hits each element in V with probability not too small. We will show
that, if this condition does not hold (that is, if such a µ does not exist), we can find a large low-rank
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 14
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
subset V 0 . The high-level idea is to consider the greedy distribution on d-tuples that is sampled as follows:
iteratively pick a random unspanned element from V and add it to the spanning set until we cover all of V .
If this distribution gives low probabilities for many elements of V then we show that it must be due to the
fact that these elements lie in some low-dimensional subspace. The following definition will be crucial
for this argument.
Definition 6.2 ((η, τ)-independent set). Let U = (u1 , . . . , un ) ∈ (Rd )n be a list of n points spanning Rd .
We say that U is (η, τ)-independent, if there exists a distribution µ supported on B(U), and a set S ⊆ [n]
with |S| ≥ (1 − η)n such that for all j ∈ S
d
τ ≤ Pr [u j ∈ I] .
n I∼µ
Since every I ∼ µ has exactly d elements, observe that for every distribution µ,
E j Pr [u j ∈ I] = d/n .
I∼µ
Moreover, if the points were in “general position,” i. e., every d of the points were linearly independent,
then by taking the distribution µ to be the uniform distribution on d-tuples with distinct elements, we
would get a (0, 1)-independent set.
Lemma 6.3. Let U = (u1 , . . . , un ) ∈ (Rd )n . If U is not (η, τ)-independent, then there exists a subspace
W of dimension at most τd which contains at least ηn elements of U.
Proof. We construct a subset S ⊂ [n] by the following greedy process. Start with S = 0. / At the jth step
we check whether the vectors {ui | i 6∈ S} span a subspace of dimension at least τd. If they do, we add
to S a tuple S j of size dτde that is linearly independent. (That is, {ui | i ∈ S j } are linearly independent
vectors.) If {ui | i 6∈ S} have dimension lower than τd we halt. Let W be the subspace spanned by the
complement of S at the end of this process. Notice that W has dimension at most τd.
Now, consider the following distribution on B(U). We first pick uniformly at random one of the sets
S j described above and add to our basis the corresponding (linearly independent) elements of U. Then
we complete this set to a basis in some fixed way. For example, this can be done by taking the first basis
in some fixed order that contains the elements of S j . For each element in S, the probability of picking it
to be in the basis is dτde/|S| ≥ τd/n. Since we are assuming that U is not (η, τ)-independent, the size of
Sc must be at least ηn. By the definition of W , this completes the proof.
Proof of Lemma 6.1. Applying Lemma 6.3 we get that V must be (δ /2, 2β )-independent. Otherwise, V
would contain a subset V 0 of size (δ /4)n and dimension at most 4β d (contradicting the assumption in
the lemma). Hence, there exists a distribution µ on B(U) and a set S ⊂ [n] with |S| ≥ (1 − δ /2)n such
that for all j ∈ S
d
2β ≤ Pr [ j ∈ I] .
n I∼µ
Let U = VS = {vi | i ∈ S} = (u1 , . . . , un0 ) with n0 = |S|. Lemma 5.1 now implies that there there exists an
invertible linear map M so that, denoting û j = Mu j /kMu j k, we have for all unit vectors w ∈ Rd
n
∑ hû j , wi2 ≤ β d .
j∈S
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 15
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Notice that U is a (3, δ /2)-LCC since the complement of U can intersect at most δ n/2 triples from each
matching in V . This completes the proof of the lemma.
6.1 A convenient form of Barthe’s theorem
The proof of Lemma 6.1 actually gives a more general result (not mentioning LCCs) that might be of
independent interest.
Theorem 6.4. Let V = (v1 , . . . , vn ) ∈ (Rd )n with dim(V ) = d be so that any subset U ⊂ V of size |U| ≥ αn
has dim(U) ≥ β d. Then, there exists an invertible linear map M : Rd → Rd and a subset S ⊂ V of size
|S| ≥ (1 − 2α)n so that, if we denote by v̂ = Mv/kMvk, we have for all unit vectors w ∈ Rd
4n
∑ hv̂, wi2 ≤ β d .
v∈S
Proof. The conditions on V and Lemma 6.3 imply that V is (2α, β /2)-independent. Then, using
Lemma 5.1, we get the map M and a set S as required.
7 Reduction to the low triple-multiplicity case
In this section we prove a lemma that shows that, when analyzing a (3, δ )-LCC V over any field F, it is
enough to consider codes in which the matchings Mv , v ∈ V used in the decoding are such that each triple
appears in a small number of matchings. (Otherwise we can find a large subset of low rank.)
Definition 7.1 (Triple-multiplicity). We say that a (3, δ )-LCC V with matchings Mv , v ∈ V has triple-
multiplicity at most r if each triple in each Mv appears in at most r of the matchings.
Lemma 7.2. Let F be a field, n ≥ (1/δ )ω(1) and β > 0 a constant. Let V = (v1 , . . . , vn ) ∈ (Fd )n be a
(3, δ )-LCC with matchings Mv , v ∈ V . Suppose that any subset V 0 ⊂ V with |V 0 | > (δ 2 /36)n satisfies
dim(V 0 ) > n1/2−β /4 . Then, there exists a (3, δ /24)-LCC U ⊂ V with |U| ≥ (δ /4)n and matchings
Mv0 , v ∈ U so that U (with the matchings Mv0 ) has triple-multiplicity at most nβ and the matchings Mv0 are
subsets of the corresponding matchings Mv .
Proof. We first reduce to the situation where every element participates in many triples. Unless mentioned
otherwise, we will count triples with multiplicity. Let 0 < γ = δ 2 /6 be a real number. Iteratively delete
vertices from V that participate in less than γn triples (counted with multiplicity), and the triples they
participate in. Let B ⊆ V be the subset of deleted elements, and let V 0 = V \ B. Since each deleted vertex
only gets rid of γn triples, the total number of triples which include some vertex of B is at most γn2 . Thus
each element in V 0 participates in at least γn triples, and at least (δ − γ)n2 > (2δ /3)n2 of the triples in V
are supported entirely in V 0 . Call this set of triples T 0 .
Claim 7.3. |V 0 | > 2δ n.
Proof. This is because there must be some v ∈ V with at least (2δ /3)n triples in its matching that still
survive in T 0 —if this was not the case, we would have |T 0 | < (2δ /3)n2 . Since the triples in the matching
corresponding to v are disjoint, |V 0 | ≥ 2δ n.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 16
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Let B0 ⊂ V 0 be the subset of points in V 0 which have less than δ n/2 of the triples in their matching
supported in V 0 . Let V 00 = V 0 \ B0 .
Claim 7.4. |V 00 | ≥ δ n, and V 00 is a (3, (δ /6)(n/|V 00 |))-LCC.
Proof. There can be at most δ n/3 elements in V 0 such that δ n/2 triples in their matchings include an
element from B—if there were more than that, then the total number of triples including a element from
B would be greater than δ n/3 · δ n/2 ≥ δ 2 n2 /6 ≥ γn2 , which is not possible. Thus, at least |V 0 | − δ n/3
of the elements in V 0 have a matching of size at least δ n/2 decoding them, lying wholly within V 0 . Thus
|B0 | ≤ δ n/3. Hence |V 00 | ≥ |V 0 | − |B0 | ≥ |V 0 | − δ n/3 > δ n. Moreover, for each v ∈ V 00 , it has a matching
of size at least δ n/2 − |B0 | ≥ δ n/6 supported in V 00 . Thus V 00 is a (3, (δ /6)(n/|V 00 |))-LCC. Let T 00 be
the union of all the triples in the LCC V 00 .
We will call a triple in T 00 a high-multiplicity triple if it has multiplicity at least nβ in T 00 ; otherwise
we will call it a low-multiplicity triple).
Claim 7.5. At least (1 − δ /24)|V 00 | of the elements in V 00 have a matching of size (δ /12)|V 00 | of low-
multiplicity triples decoding them.
Proof. Suppose the claim does not hold. That is, at least (δ /24)|V 00 | of the elements in V 00 have at least
half of their matchings (in T 00 ) composed of high multiplicity triples.
We now delete all the triples of low multiplicity from T 00 . Since there are at least (δ 2 /288)|V 00 |2
triples (counting multiplicity) of multiplicity at least nβ in the LCC V 00 , by averaging, there exists v ∈ V 00
that participates in at least (δ 2 /288)|V 00 | triples (counted with multiplicity), and each of the triples has
multiplicity at least nβ . Observe that since all these triples contain v, no two triples are part of a matching
corresponding to the same element.
By greedily choosing distinct triples containing v of highest multiplicity, one can pick a set T ∗ of
distinct triples of size at most n1/2−β /2 such that together they span at least n1/2+β /2 distinct elements of
V 00 . This is true since n1/2+β /2 ≤ (δ 2 /288)|V 00 |, each triple of multiplicity nβ spans at least nβ distinct
elements and distinct triples sharing an element must span distinct elements. By “distinct” here we mean
distinct LCC indices (not necessarily distinct vectors).
Let L be a linear transformation of co-rank at most 3n1/2−β /2 which maps each element participating
in a triple of T ∗ to 0. Since all the elements spanned by the triples of T ∗ also get mapped to 0, at least
n1/2+β /2 elements of V 00 get mapped to 0 under L. Let this set be V ∗ . Recall that each element of V 0 (and
hence of V ∗ ) participates in γn triples which together decode γn distinct elements of V .
Let S ⊂ V be the subset of all elements whose matching contains at least (γ/6)n1/2+β /2 triples that
each contain some element from V ∗ . Since the total number of triples containing some element from V ∗
is at least |V ∗ | · γn/3, by a simple counting argument we get that |S| ≥ (γ/6)n.
To finish the proof of Claim 7.5 we will now argue that
dim(S) ≤ 2n1/2−β /3 < n1/2−β /4 .
For contradiction, assume dim(S) > 2n1/2−β /3 , then
dim(L(S)) > 2n1/2−β /3 − 3n1/2−β /2 > n1/2−β /3 .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 17
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Moreover, since L sends V ∗ to 0, all triples containing some element of V ∗ now have at most 2 nonzero
elements, and thus the triples can be replaced by pairs. Thus L(V ) is a (2, (γ/6)n−1/2+β /2 )-LDC of size
n, decoding to linearly independent vectors spanning at least n1/2−β /3 dimensions. Using Theorem 4.5
(lower bound for 2-query LDCs) we get that
γ/6nβ /6
−1
n≥2 16 .
Since n ≥ (1/δ )ω(1) , γ = poly(δ ) and β = Ω(1), this is a contradiction (for large enough n).
Thus, the set S has size at least (γ/6)n = δ 2 n/36 and dimension at most n1/2−β /4 , contradicting the
assumption in Lemma 7.2. This completes the proof of Claim 7.5
Applying Claim 7.5, we see that one can delete all triples of multiplicity greater than nβ and delete at
most δ |V 00 |/24 elements to get a subset U such that each element of U has a matching of δ |U|/24 triples
decoding to it where the triples are supported in U. Thus U is a (3, δ /24)-LCC with |U| ≥ δ n/4, and
with all triples of multiplicity at most nβ . This completes the proof of Lemma 7.2.
8 LCCs over R can be clustered
In this section we prove the “clustering step” described in the introduction.
Definition 8.1 (Clustering). Let S1 , . . . , Sm ⊂ [n]. We say that a triple τ ∈ [n]
3 is clustered by the family
of sets S1 , . . . , Sm if there exists an i ∈ [m] so that |τ ∩ Si | ≥ 2. If M is a multiset of triples, we say that M
is clustered by S1 , . . . , Sm if every triple in M is clustered.
We prove the clustering result as a sequence of three lemmas. First we state the final clustering lemma
that will be used later in the proof of our main result. This result was informally stated as Lemma 3.1.
Lemma 8.2 (Final clustering). Let n > (1/δ )ω(1) and let β > 0 be a constant. Let V = (v1 , . . . , vn ) ∈
(Rd )n be a (3, δ )-LCC so that every subset U ⊂ V of size |U| ≥ (δ 2 /288)n has dimension at least
max{8δ 6 d, n1/2−β /4 }. Then, there exists a (3, δ̂ )-LCC V̂ = (v̂1 , . . . , v̂n̂ ) ⊂ V of dimension dˆ ≤ d, size
n̂ ≥ (δ /10)n and δ̂ ≥ δ 2 /4 and sets S1 , . . . , Sm ⊂ [n̂] so that
ˆ for all i ∈ [m];
1. |Si | ≤ O(n̂/δ̂ 6 d)
2. Ω(δ̂ 19 dˆ3 /n̂1+2β ) ≤ m ≤ O(n̂1+2β /δ̂ 10 d);
ˆ
3. if M̂v̂ , v̂ ∈ V̂ are the matchings used to decode V̂ , then each M̂v̂ is clustered by S1 , . . . , Sm .
We will prove this lemma using the following lemma, which adds conditions on the given code.
Lemma 8.3 (Intermediate Clustering). Let n ≥ (1/δ )ω(1) and β > 0 a constant. Let V = (v1 , . . . , vn ) ∈
(Rd )n be a (3, δ )-LCC with triple-multiplicity at most nβ and so that for each unit vector w ∈ Rd
n
n
∑ hv j , wi2 ≤ δ 6 d .
j=1
Let t = n/(δ 6 d) and suppose that d > 108 · 200/δ 8 . Then, there exist m subsets S1 , . . . , Sm ⊂ V such that
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 18
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
1. |Si | ≤ O(t) for all i ∈ [m];
2. Ω(δ n2−β /t 3 ) ≤ m ≤ O(t · nβ /δ 4 );
S
3. if M = v∈V Mv is the multiset of all triples in all matchings used to decode V , then there are at
most δ 2 n2 /100 triples in M that are not clustered by S1 , . . . , Sm .
To prove the intermediate clustering lemma we first prove a basic clustering lemma.
Lemma 8.4 (Basic Clustering). Let n,t, β , δ and V ∈ (Rd )n be as in Lemma 8.3 and let M be the multiset
of triples obtained by taking the union of all Mv , v ∈ V . Let M̄ ⊂ M be of size at least δ 2 n2 /100 and
suppose that d > 108 · 200/δ 8 . Then there exists a subset S ⊂ V with |S| ≤ O(t) and a subset T ⊂ M̄ with
|T | ≥ Ω(δ 4 n2−β /t) such that each triple in T contains at least two elements from S.
First, we show how to use the intermediate clustering lemma to prove the final Lemma 8.2. After that,
we will prove the basic clustering lemma and, using it, easily derive the intermediate clustering lemma.
Proof of Lemma 8.2. At a high level, the proof follows by first applying Lemma 6.1 to get the well-spread
vectors condition on the points in a large sub-LCC V 0 of V . Then we use Lemma 7.2 on V 0 to get a
subcode V 00 with low triple-multiplicity. (This does not ruin the well-spread vectors condition by much.)
Finally, we apply Lemma 8.3 on V 00 to get clustering for almost all triples. The only reason why one
of these steps could fail is if we found a large low dimensional subset in V (which will contradict our
assumptions). A final refinement step, using Claim 4.1 shows the existence of a subcode V̂ as required.
The details follow.
Reducing to the well-spread vectors case. We apply Lemma 6.1 on V , with β = 2δ 6 , to obtain a
subset V 0 of size n0 ≥ (1 − δ /2)n so that V 0 is a (3, δ 0 = δ /2)-LCC and so that for each unit vector
w ∈ Rd we have
n
∑ hv0 , wi2 ≤ 6 .
v0 ∈V 0 2δ d
If we cannot apply Lemma 6.1, it means that there is a subset U in V of size |U| ≥ (δ /4)n and dimension
at most 8δ 6 d, which would contradict our assumptions.
Reducing to low triple-multiplicity. We now apply Lemma 7.2 on the LCC V 0 to get a (3, δ /48)-LCC
V 00 ⊂ V 0 of size n00 ≥ (δ /8)n and with triple-multiplicity at most (n0 )β ≤ (n00 )2β . If we cannot apply
the lemma, it means that there is a subset U ⊂ V 0 of size |U| ≥ (δ 02 /36)n0 ≥ (δ 2 /288)n and dimension
dim(U) ≤ (n0 )1/2−β /4 ≤ n1/2−β /4 , which would contradict our assumptions. Let d 00 = dim(V 00 ) and
00
δ 00 = δ 2 /2. We can think of V 00 as a (3, δ 00 )-LCC over Rd in which the well-spread vectors condition
above can be written as
n n00
∑ hv00 , wi2 ≤ 6 ≤ 006 00 ,
v00 ∈V 00 2δ d δ d
00
for all unit vectors w ∈ Rd . (We took δ 00 = δ 2 /2 to compensate for the drop in n00 in the above inequality.)
00
Notice that moving from Rd to Rd is not a problem since we can orthogonally project all vectors on the
span of V 00 and maintain all inner products with all unit vectors.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 19
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Clustering. We can now apply Lemma 8.3 on V 00 to find sets S1 , . . . , Sm that cluster all but (δ 002 /100)n002
of the triples in the decoding matchings of V 00 . With |Si | ≤ O(n00 /δ 006 d 00 ) for all i ∈ [m] and (using
t = n00 /δ 006 d 00 ) we obtain !
0019 003
δ d n001+2β 00
Ω ≤m≤O ·d .
n001+2β δ 0010
If we cannot apply the lemma, it means that d 00 ≤ (1/δ 00 )O(1) , which would contradict our assumptions
on V (since it would have a subset V 00 of size n00 ≥ (δ /8)n and dimension (1/δ )O(1) < n1/4 ).
Refinement. To complete the proof, observe that, there are at least (1 − δ 00 /10)n00 points in V 00 that have
at least half of their matchings clustered by S1 , . . . , Sm . Hence, we can use Claim 4.1 to find a (3, δ̂ )-LCC
V̂ ⊂ V 00 of size n̂ ≥ (1 − δ 00 /10)n00 ≥ (δ /10)n with δ̂ ≥ δ 00 /2 ≥ δ 2 /4 so that the sets S1 , . . . , Sm (restricted
to indices in V̂ ) cluster all the triples in the matchings of V̂ . Notice that, since dˆ = d 00 , δ̂ = Θ(δ 00 ) and
n̂ = Θ(n00 ), the bounds on the sizes of the sets Si and on m still hold (the difference in constants will be
swallowed by the big “O”). This completes the proof of Lemma 8.2.
8.1 Preliminaries for the proof of the clustering lemmas
We denote by kvk the `2 norm of a vector v. Notice that for two unit vectors u and v, ku − vk2 = 2 − 2hu, vi.
We denote the correlation between two unit vectors v, u as |hv, ui|.
Let V be as in Lemma 8.3 with matchings Mv , v ∈ V . The conditions of Lemma 8.3 (which we will
assume to hold for the rest of this section) tell us that for all unit vectors u ∈ Rd we have
n
n
∑ hv j , ui2 ≤ δ 6 d = t . (8.1)
j=1
This has the following useful consequence.
Claim 8.5. For every unit vector u ∈ Rd we have
|{v ∈ V | |hv, ui| ≥ α}| ≤ t/α 2 .
We can also bound the number of points in V that correlate with a given plane.
Claim 8.6. Let P ⊂ Rd be a two dimensional subspace and define
K = {v ∈ V | |hv, ui| ≥ α for some unit vector u ∈ P} .
Then |K| ≤ (80/α 3 ) · t.
Proof. For each v ∈ K let u(v) ∈ P be a unit vector with |hv, u(v)i| ≥ α. Now, cover the boundary of
the unit circle in P with at most 20/α balls10 of radius at most α/2. By a pigeon hole argument, one
of these balls must contain at least α|K|/20 of the points u(v). Now, the center of this ball must have
correlation at least α/2 with all the α|K|/20 corresponding vectors v. Applying Claim 8.5 we get that
|K| ≤ (80/α 3 )t.
10 We consider balls in Rd .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 20
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
For every unit vector u ∈ Rd , let
Cor(u) = {v ∈ V | |hu, vi| ≥ 1/104 } .
For every v ∈ V , let Mv∗ ⊆ Mv be defined as
Mv∗ = {(vi , v j , vk ) ∈ Mv | vi , v j , vk ∈ V \ Cor(v)} .
That is, let Mv∗ be the subset of the triples decoding v where each vector in each triple has low correlation
with v. Intuitively, such triples must be close to a two dimensional plane and hence “almost” dependent.
The following is an immediate corollary of Claim 8.5.
Claim 8.7. For every v ∈ V , |Mv∗ | ≥ |Mv | − 108t ≥ δ n − 108t.
Let M ∗ be the (multiset) union of all triples in Mv∗ for all v ∈ V . By Claim 8.7, M ∗ has size at least
δ n2 − 108tn.
The following proposition bounds the number of triples in M ∗ containing a fixed pair of vertices.
Proposition 8.8. For all i 6= j ∈ [n], there are at most O(tnβ ) triples (counting multiplicities) in M ∗
containing the pair (vi , v j ).
Proof. We will show a bound of O(t) on the number of distinct triples containing (vi , v j ). The O(tnβ )
bound will then follow by our assumption on the maximum multiplicity of triples in M (and so also in
M ∗ ).
Let P = span{vi , v j }. Consider a triple (vi , v j , vk ) containing vi , v j and suppose this triple belongs to
some matching Mv∗ . Let Π = span{vk , v} and observe that both planes P and Π (both are indeed planes
since the property of the LCC being regular implies the distinctness of the points in a triple and the point
they are used to decode to) are contained in the three dimensional subspace span{vi , v j , vk }. Therefore,
they must intersect in some unit vector w ∈ P ∩ Π. Now, since |hvk , vi| ≤ 10−4 , a simple calculation
shows that w must have correlation at least 1/10 with either vk or v (since w belongs to their span and
they are close to being orthogonal). To summarize, we have shown that in every triple (vi , v j , vk ) ∈ Mv ,
one of the vectors v, vk has correlation at least 1/10 with the plane P. Now, the union of {v, vk } as we go
over all distinct triples containing {vi , v j } is at most O(t) by Claim 8.6. If the total number of distinct
triples is r, then at least r/2 of the vectors v will correlate with P or r/2 of the vk will correlate with P. In
either case we see that r/2 = O(t), and hence r = O(t).
Definition 8.9 (Triple types). We split the triples appearing in M ∗ into two types.
• A triple (vi , v j , vk ) ∈ M ∗ is defined to be of Type A if there exists a pair of vertices in the triple, say
(vi , v j ), such that
|hvi , v j i| ≥ 9/10 .
• A triple (vi , v j , vk ) ∈ M ∗ is defined to be of Type B if
|hvi , v j i| < 9/10 , |hv j , vk i| < 9/10 and |hvi , vk i| < 9/10 .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 21
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
When we refer to a triple as Type A or Type B, we will implicitly assume that this triple is in M ∗ .
We first state and prove three simple propositions that will be useful in the proof of the basic clustering
lemma. Below, we will sometimes refer to the elements of V as “vertices.” The reader not wishing to
follow the somewhat tedious calculations can recall the high level overview given in Section 3.
Proposition 8.10. Let (vi , v j , vk ) be a triple of Type B then either |hvi , v j i| ≥ 1/100 or |hvi , vk i| ≥ 1/100.
Proof. Suppose in contradiction that hvi , v j i < 1/100 and hvi , vk i < 1/100.
Suppose the triple decodes to the vector u and by an appropriate orthogonal change of basis (which
does not change distances or inner products), let us assume that the vectors all lie in the 3 dimensional
space spanned by the unit vectors e1 , e2 and e3 . We can also assume that u = e1 , vi is a linear combination
of e1 and e2 , and v j and vk are linear combinations of e1 , e2 and e3 .
Since the vectors in the triple are uncorrelated to u, their inner product with e1 has absolute value at
most 1/104 . Since vi is a unit vector, hvi , e1 i2 + hvi , e2 i2 = 1 and hence |hvi , e2 i| > |hvi , e2 i|2 ≥ 1 − 1/108 .
Also since |hvi , v j i| < 1/100 and |hvi , vk i| < 1/100,
1 108 2
|hv j , e2 i| < × 8 < .
100 10 − 1 100
hv j , e1 i2 + hv j , e2 i2 + hv j , e3 i2 = 1 p
Similarly |hvk , e2 i| < 2/100. Also since v j is a unit vector, p and hence
2 8 4
hv j , e3 i ≥ 1 − 1/10 − 4/10 , implying that |hv j , e3 i| ≥ 99/100. Similarly |hvk , e3 i| ≥ 99/100.
Hence |hvk , v j i| ≥ 99/100, contradicting the property of being Type B.
Proposition 8.11. Suppose T is a set of m distinct triples of Type B, each sharing the pair (vi , v j ). Let S
be the set of size m containing all the vertices of the triples in T except vi and v j . Then there is a ball of
radius at most 5/104 containing at least m/105 points of S.
Proof. We will first show that every point of S is close to the subspace through vi and v j , and then apply
a pigeon hole argument.
Let vk ∈ S. Then (vi , v j , vk ) is a triple of Type B, and in particular the triple is in Mu∗ for some vertex
u.
By an appropriate orthogonal change of basis (which does not change distances or inner products),
we can assume that the vectors all lie in the 3 dimensional space spanned by the unit vectors e1 , e2 and
e3 . We can also assume that vi = e1 , v j is a linear combination of e1 and e2 , and u and vk are linear
combinations of e1 , e2 and e3 .
Since we have a triple of Type B, |hvi , v j i| < 9/10. Thus |hv j , e1 i| < 9/10. Since hv j , e1 i2 +hv j , e2 i2 =
1, this implies that |hv j , e2 i| > 2/5. Also since |hu, vi i| < 1/104 and |hu, v j i| < 1/104 , thus |hu, e1 i| <
1/104 and |hu, e2 i| < 5/2 × |hu, v j i| < 5/2 × 1/104 . Hence
q
|hu, e3 i| = 1 − |hu, e1 i|2 − |hu, e2 i|2 ≥ 1 − 1/107 .
Since |hu, vk i| < 1/104 , we get that |hvk , e3 i| ≤ 1/104 × 107 /(107 − 1) ≤ 2/104 . Notice that |hvk , e3 i| is
precisely the distance of vk to the subspace spanned by vi and v j .
Now consider the unit circle C in the subspace spanned by e1 and e2 . We will show that each element
of S is at distance at most 4/104 from C. To see this, observe that for vk ∈ S, the projection v̄k of vk onto
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 22
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
the subspace spanned by e1 and e2 is of length at least 1 − 2/104 (by the triangle inequality). Thus v̄k is
at distance at most 2/104 from C and also at distance at most 2/104 from vk . Thus again by the triangle
inequality, the distance between vk and C is at most 4/104 . Now cover C with 105 2-dimensional discs of
radius 1/104 . Clearly this can be done. Thus each element vk in S is at distance at most 5/104 from the
center of one of these discs. Thus for one of these discs, there are m/105 points of S that are at distance at
most 5/104 from the center of the disc.
Proposition 8.12. Let G be an edge-weighted k-uniform hypergraph on n vertices with k ≥ 2. Define
the degree of a vertex to be the sum of the weights of all hyperedges containing it. Suppose the average
degree of a vertex in G is D. Then, there exists a vertex induced subgraph G0 of G in which every vertex
has degree at least D/k.
Proof. To obtain G0 we iteratively delete vertices whose degree in G is less than D/k. Observe that, after
each deletion, the average degree in the hypergraph strictly increases. Indeed, after removing a vertex of
degree D0 < D/k, the new average is
n · D − kD0
> D.
n−1
Thus the process must terminate when all vertices have degree at least D/k.
8.2 Basic clustering: proof of Lemma 8.4
At this point, we assume that V is well spread over the unit sphere, has low-multiplicity triples that are
nearly orthogonal to their associated vectors in V . Each triple is either of Type A—containing a very
correlated pair—or of Type B—consisting of uncorrelated vectors.
We first show that having many triples of the same type implies that we can find a small set of vertices
such that many of the triples intersect the set in at least two of their elements. This will be the main
step in the proof of Lemma 8.4 which is given below. Recall that we have an upper bound of nβ on the
multiplicity of each triple in M ∗ .
Lemma 8.13. Suppose there is a subset T of γn2 triples (counting multiplicities) in M ∗ of the same type
(either Type A or Type B), then there is a set S ⊆ V such that |S| = O(t), and at least Ω(γ 2 n2−β /t) triples
in T intersect S in at least two of their elements.
Proof. We separate into two cases according to the type of the triples in T . In both cases, we will first
refine to the situation where every vertex is incident to many (γn) triples. In both cases we will find a
cluster V ∗ of nearby vertices, and let S be some kind of neighborhood of V ∗ such that every triple which
intersects V ∗ will also intersect S in two elements. Since V ∗ will be incident to many triples, we will
conclude that many triples intersect S in two elements. Moreover we will ensure that every vertex in S
will have some constant correlation with some fixed carefully chosen vertex w. Since every element in S
correlates with vertex w, Claim 8.5 implies that S cannot be too large. In the case of Type A triples, the
argument is fairly straightforward, whereas in the case of Type B triples the argument is more delicate.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 23
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Case 1: T has only triples of Type A. Consider the following weighted graph H on vertex set V in
which the edges are all pairs vi , v j with |hvi , v j i| ≥ 9/10 and the weight of an edge (vi , v j ) is the number
of triples in T , counting multiplicities, that contain this pair (we can discard edges of weight zero). We
define the degree of a vertex deg(v) as the sum of weights over all edges of H that contain v. Since
(1/2) ∑v deg(v) ≥ |T | we have that the average degree in H is at least D = 2|T |/n ≥ 2γn.
Let H 0 be a vertex induced subgraph of H in which every vertex has degree at least D/2 (such a
subgraph exists by Proposition 8.12). Let w be any vertex in H 0 and observe that, by Proposition 8.8, w
must have at least r = Ω(γn1−β /t) distinct neighbors u1 , . . . , ur (since the maximal weight of an edge is
O(tnβ )). Let V ∗ = {u1 , . . . , ur }. We define the set S to contain these vertices u1 , . . . , ur ∈ V ∗ as well as all
of their neighbors.
First, we argue that S cannot be√too large. To see this, observe that, if (vi , v j ) is an edge in H then
v j must have `2 distance at most 1/ 5 from either vi or −vi . Thus, since all vertices in S are at (graph)
distance
√ less than two from w, we have that they are all contained in the union of two balls of radius
2/ 5 around w and around −w. This means that all points in S must have correlation at least 4/6 with w.
Using Claim 8.5 we get that |S| ≤ O(t).
To see that there are many triples with two elements in S observe that the sum over all weights
of edges touching u1 , . . . , ur is at least r · γn ≥ Ω(γ 2 n2−β /t) (using the fact that H 0 has high minimum
degree). Since every triple is counted at most 3 times in this sum we conclude that there are at least
Ω γ 2 n2−β /t triples with a pair in S.
Case 2: T has only triples of Type B. Consider the following 3-regular weighted hypergraph G. The
set of vertices of G is the set V . For each triple (vi , v j , vk ) ∈ T we have a hyper-edge in G with weight
equal to the multiplicity of that triple in T . By Proposition 8.12, there is a subgraph G0 of G such that
every vertex of G0 is incident to at least γn/3 triples (counting weights) lying within G0 .
Pick any vertex v ∈ G0 . Let Cv be the multiset {v0 ∈ V | |hv, v0 i| > 1/100} of vectors that are slightly
correlated with v. By Claim 8.5 (well-spread vectors condition) we have |Cv | < t ·104 . By Proposition 8.10,
every triple containing v has another vertex v0 such that |hv, v0 i| > 1/100 (and thus v0 ∈ Cv ). Thus by
a simple averaging argument, it must be that for some v0 ∈ Cv , the pair (v, v0 ) participates in at least
γn/(3|Cv |) triples (counting multiplicities). Using the bound on triple-multiplicity, we get that there is a
set T ∗ of at least γn/(3|Cv |nβ ) distinct triples containing v and v0 . Thus
γn γn1−β
|T ∗ | ≥ ≥
3|Cv |nβ 104 · t
and, by Proposition 8.11, at least |T ∗ |/105 vertices (of G0 ) lie in a ball of radius 5/104 . Call this set of
vertices V ∗ . Thus what we have so far is a set V ∗ of vertices of G0 all lying in a ball of radius 5/104 ,
where
γn1−β
|V ∗ | ≥ .
3 · 109 · t
Recall that every point vk in V ∗ is incident to at least γn/3 triples lying within G0 , and, by Propo-
sition 8.10, for each of the triples there exists a vertex v0k distinct from vk in that triple such that
|hvk , v0k i| > 1/100.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 24
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Let S = {u ∈ V | ∃w ∈ V ∗ s. t. |hu, wi| > 1/100} be the set of all vertices that have correlation at least
1/100 with some vertex of V ∗ . Fix w ∈ V ∗ . Then for any u ∈ S, by definition of S, there exists w0 ∈ V ∗
such that hu, w0 i > 1/100. Also, since radius of V ∗ is at most 5/104 we have kw − w0 k ≤ 1/103 . Together,
these imply that |hu, wi| > 1/103 . Since this holds for all u ∈ S (and for the same fixed w), by Claim 8.5
we get that |S| < 106t.
Moreover, observe that each triple that intersects V ∗ must intersect S in two elements. Since each
tripe in V ∗ is incident to at least γn/3 triples, and each triple is counted at most 3 times, there must be at
least !
γn1−β
Ω γn × 9 = Ω(γ 2 n2−β /t)
10 · t
triples with a pair in S.
Proof of Lemma 8.4. Since d > 200 · 108 /δ 8 we have that
n δ 2n
t= < .
δ 6 d 200 · 108
Thus, by Claim 8.7 we have that for each v ∈ V
|Mv \ Mv∗ | ≤ 108t ≤ δ 2 n/200 .
So, the set M̄ ∗ = M̄ ∩ M ∗ must have size at least |M̄| − δ 2 n2 /200 ≥ δ 2 n2 /200 triples. At least half of
these triples are of the same type (A or B) and so we can apply Lemma 8.13 with γ = δ 2 /400 to get the
required sets S and triples T .
8.3 Intermediate clustering: proof of Lemma 8.3
We prove Lemma 8.3 by iteratively applying Lemma 8.4 until we have gathered “enough” clustered
triples, where we call a triple “clustered” if it has intersection size at least 2 with one of the sets Si .
We start with M̄ = M, which is initially of size |M̄| ≥ δ n2 ≥ δ 2 n2 /100. Applying Lemma 8.4 we get
sets T1 ⊂ M̄ and S1 ⊂ V with |S1 | ≤ O(t) and so that all triples in T1 are clustered. We now let M̄ = M̄ \ T1
and continue in this manner to generate S2 , S3 , . . . , Sm and (disjoint) T2 , T3 , . . . , Tm , removing the triples in
the Ti from M̄ as we proceed, until there are at most δ 2 n2 /100 triples in M that are not clustered.
This only leaves the task of bounding the number of iterations, m. The upper bound follows
from the fact that the sets Ti are disjoint, each of size at least Ω(δ 4 n2−β /t) and that |M| ≤ δ n2 . The
lower bound follows from the observation that, by Proposition 8.8, each Ti can have size at most
|Si |2 · O(t · nβ ) = O(nβ t 3 ). Since the union of the Ti contains at least Ω(|M|) ≥ Ω(δ n2 ) triples, we get
that m ≥ Ω(δ n2−β /t 3 ). This completes the proof of Lemma 8.3.
9 Clustering implies large low-rank subset
The main result of this section is the following lemma that gives a dimension upper bound for LCCs in
which the triples are “clustered.” An informal statement of this lemma was given as Lemma 9.1.
Notice that this lemma works over any field F.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 25
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Lemma 9.1 (Clustering implies large low-rank subset). Let F be a field, 0 < ε < 1/50, 0 < β < ε/2 and
suppose n > (1/δ )ω(1) . Let V = (v1 , . . . , vn ) ∈ (Fd )n be a (3, δ )-LCC with matchings Mv , v ∈ V . Suppose
there exist sets S1 , . . . , Sm ⊂ [n] with
1. |Si | ≤ O(n/δ 6 d) for all i ∈ [m];
2. Ω(δ 19 d 3 /n1+β ) ≤ m ≤ O(n1+β /δ 10 d);
3. every triple in each Mv is clustered by S1 , . . . , Sm .
Then there is a subset V 0 ⊂ V of size |V 0 | ≥ (δ /2)n and rank at most n1/2−ε .
This lemma will be an easy corollary to the following lemma, which shows that there is a small subset
in V so that, when projecting this set to zero, the dimension of V drops by a lot.
Lemma 9.2 (Restriction lemma). Let n, β , ε, V and S1 , . . . , Sm satisfy the conditions of Lemma 9.1.
Assume further that the matchings Mv are in regular form (no “2-query” triples). If d > n1/2−ε then there
exists a subset U ⊂ V with
|U| ≤ n1/4+7ε
such that, if L : Fd → Fd is any linear map with U ⊂ ker(L) then L(V ) = {L(v) | v ∈ V } is contained in
a subspace of dimension at most n10ε
We prove the Restriction lemma (Lemma 9.2) below, following the short proof of Lemma 9.1 from
Lemma 9.2.
Proof of Lemma 9.1. Using Claim 4.7 we can reduce to the case that the code V and the matchings Mv
are in regular form (that is, there are no “2-query” triples). Indeed, replacing V with the code given in
Claim 4.7 leaves us with a new code (with n and δ the same up to a constant) satisfying the same clustering
requirements (using the same sets S1 , . . . , Sm ) and with the same dimension. If we cannot apply Claim 4.7
it is because there is a subset U ⊂ V of size (δ /2)n and dimension at most O((1/δ ) log(n)) < n1/2−ε , in
which case the proof is done.
Next, suppose in contradiction that d > n1/2−ε (otherwise we let V 0 = V ). Apply Lemma 9.2 to get
a subset U ⊂ V with |U| ≤ n1/4+7ε , such that, if we send U to zero by a linear map, the dimension of
span{V } goes down to at most n10ε . The existence of such a U implies that
d = dim(V ) ≤ |U| + n10ε ≤ n1/4+7ε + n10ε
which gives a contradiction if ε < 1/50.
9.1 Proof of Lemma 9.2
Using the assumption d > n1/2−ε we get that for each i ∈ [m],
|Si | = O(δ −6 n1/2+ε )
and the number of sets, m, is between
Ω(δ 19 n1/2−3ε−β ) ≤ m ≤ O(δ −10 n1/2+ε+β ) .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 26
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
For each v ∈ V we know that all δ n triples in Mv contain two elements in one of the sets S1 , . . . , Sm .
Let Pv denote the set of all these pairs. That is, for each Si , add to Pv all the pairs in Si that are contained
in a triple from Mv . We fix some arbitrary way to associate each pair in Pv with a single set Si . (If this pair
is in more than one set Si just pick one arbitrarily.)
The properties of the sets Pv , v ∈ V are summarized in the following claim.
Claim 9.3. Each Pv is a matching of at least δ n pairs, each pair (u, w) ∈ Pv is associated with a unique
Si such that u, w ∈ Si and there exists a triple in Mv containing both u and w.
Recalling the high level overview given in Section 3, we now define a way to sample a random subset
in V that, using the clustering assumption, “hits” many pairs in many triples. This sampling process is
given below.
The distribution µ. We denote by neg(n) any function of n that is less than exp(−nα ) for some
constant α > 0 and all sufficiently large n. We use the notation A ∼ µ to mean “the random variable A is
sampled according to the distribution µ.”
We now define a distribution µ on subsets of V . To pick a set A ∼ µ we first pick an index i ∈ [m]
uniformly at random and then pick A ⊂ Si to contain each element of Si independently with probability
n−1/4+ε . If Si happens to be empty, we let A be the empty set. It will be convenient to treat µ also as a
distribution on pairs of the form (A, i) with A ⊂ V and i ∈ [m] so, we will sometimes write (A, i) ∼ µ to
denote that i is the random index chosen in the sampling process of A and, other times just write A ∼ µ.
Claim 9.4. Let A ∼ µ. Then
Pr[|A| ≥ n1/4+3ε ] ≤ neg(n) .
Proof. Conditioning on the choice of the set Si , the expectation of |A| is at most
|Si | · n−1/4+ε ≤ O(δ 6 n1/4+2ε ) < n1/4+3ε /100 .
Thus, by a Chernoff bound, the probability that the size of A exceeds n1/4+3ε is at most neg(n). Taking a
union bound over the m possible choices of Si the probability is still neg(n).
Observation 9.5. We can define a new distribution µ 0 that samples A according to µ until it gets a set A
of size at most n1/4+3ε . By the claim, the statistical distance between µ and µ 0 is at most neg(n). Hence,
as long as we can tolerate a neg(n) error in our probabilities, we can switch between µ and µ 0 as needed.
The functions fA,i (v). For each set A ⊂ Si we define a partial function fA,i : V → V . The value fA,i (v)
is defined as follows: Consider the pairs in Pv that are associated with Si . If one of these pairs is contained
in A then fA,i (v) is defined to be the third element of the triple of Mv associated with that pair. More
formally, if there is a pair u, w ∈ Si so that a triple (u, w, z) is in Mv then we define fA,i (v) = z. If there is
more than one such pair, we pick one arbitrarily, for instance the first one in some fixed order. If there is
no such pair, we let fA,i (v) = ⊥ (undefined).
We use the notation x ∼ y, with x, y ∈ Fd , to denote that x is a constant multiple of y and y is a constant
multiple of x. That is, either they are both zero, or they are both non-zero multiples of each other. Notice
that the relation ∼ is an equivalence relation.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 27
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Claim 9.6. Let i ∈ [m], A ⊂ Si and let fA,i be defined as above. If L : Fd → Fd is any linear map sending
A to zero, then L(v) ∼ L( fA,i (v)) for all v for which fA,i (v) 6= ⊥ .
Proof. If fA,i (v) 6= ⊥ then there is a triple (x, y, z) ∈ Mv with x, y ∈ A and fA,i (v) = z. Since v ∈ span{x, y, z}
we get that L(v) ∈ span{L(x), L(y), L(z)} = span{L( fA,i (v))}. Similarly, since we are assuming that v
is not in the span of x, y (since the matchings Mv are in regular form), z is in the span of v, x, y and so
L(z) ∈ span{L(v)}.
Probability bounds. The following three claims give bounds on certain probabilities involving the
functions fA,i , when (A, i) ∼ µ 0 .
Claim 9.7. Let (A, i) ∼ µ 0 and let v ∈ V . Then, Pr[ fA,i (v) 6= ⊥] ≥ Ω(δ 17 n−3ε ) .
Proof. By Observation 9.5, it is enough to analyze the probability for the distribution µ. Fixing v ∈ V we
call a set Si heavy if it contains at least n1/2−2ε pairs from Pv (recall Claim 9.3). Since we are choosing
each element of Si with probability n−1/4+ε , the probability to “miss” a single pair from Pv is exactly
(1 − n−1/2+2ε ). If Si is heavy, then (using the fact that Pv is a matching) the probability that A contains at
least one of the pairs in Pv is at least
A
n1/2−2ε
Pr Pv ∩ 6= 0/ ≥ 1 − 1 − n−1/2+2ε ≥ 1/2 . (9.1)
2
We now bound from below the probability that Si is heavy. Recall that |Pv | ≥ δ n and that m ≤
O(δ −10 n1/2+ε+β ). Let mh + m` = m so that mh is the number of heavy sets Si . Since each Si can contain
at most |Si |/2 = O(δ −6 n1/2+ε ) disjoint pairs, we have that
δ n ≤ m` · n1/2−2ε + mh · O(δ −6 n1/2+ε )
≤ O(δ −10 n1−ε+β ) + mh · O(δ −6 n1/2+ε ) .
This implies (since β < ε/2) that
mh ≥ Ω(δ 7 n1/2−ε ) .
Therefore, !
mh δ 7 n1/2−ε
≥Ω = Ω(δ 17 n−3ε ) .
m δ −10 n1/2+ε+β
Combining the above two bounds, we get that the probability of picking a heavy cluster and then
picking some pair in Pv is at least Ω(δ 17 n−3ε ).
Claim 9.8. Let (A, i) ∼ µ 0 . Then, for all v, z ∈ V ,
Pr[ fA,i (v) = z] ≤ O(δ −19 n−1+6ε ) .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 28
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Proof. By Observation 9.5, it is enough to analyze the probability for the distribution µ. Suppose z
appears in a triple (u, w, z) ∈ Mv that is associated with Sî for some î ∈ [m]. (If there is no such î then
the probability in question is equal to zero.)By our definition of the functions fA,i , it is only possible for
fA,i (v) = z to hold if i = î and both u and w are chosen to be in the set A ⊂ Sî . The probability to pick i = î
is 1/m ≤ O(δ −19 n−1/2+3ε+β ). Now, conditioned on picking this event, the probability of picking both u
and w to be in A is n−1/2+2ε . Multiplying, and using the bound β < ε/2, we get the required bound.
Claim 9.9. Let (A, i) ∼ µ 0 and let B ⊂ V be a set with |B| ≤ n1−10ε . Then, for every v ∈ V ,
Pr[ fA,i (v) 6= ⊥ ∧ fA,i (v) 6∈ B] ≥ Ω(δ 17 n−3ε ) .
Proof. Let p = Pr[ fA,i (v) 6= ⊥ ∧ fA,i (v) 6∈ B]. Then, by Claims 9.7 and 9.8, we have
1 − p = Pr[ fA,i (v) = ⊥ ∨ fA,i (v) ∈ B]
≤ Pr[ fA,i (v) = ⊥] + Pr[ fA,i (v) ∈ B]
≤ 1 − Ω(δ 17 n−3ε ) + |B| · O(δ −19 n−1+6ε )
≤ 1 − Ω(δ 17 n−3ε ) + O(δ −19 n−4ε ) .
Rearranging, and using the fact that n ≥ (1/δ )ω(1) , we get that p ≥ Ω(δ 17 n−3ε ).
The set U. To define the set U required in Lemma 9.2, we proceed as follows. Let r be an integer to
be determined later, and pick r sets A1 , . . . , Ar ⊂ V and r indices i1 , . . . , ir ∈ [m] so that each (A j , i j ) is
sampled independently according to the distribution µ 0 . Let U = rj=1 A j . Let f1 = fA1 ,i1 , . . . , fr = fAr ,ir
S
be the corresponding (partial) functions on V . Our goal is to show that, with probability greater than zero,
setting U to zero by a linear map, reduces the dimension of V to n10ε .
We begin by defining a sequence of undirected graphs H0 , H1 , . . . , Hr on vertex set V which will
depend on the choice of the sets A1 , . . . , Ar . The first graph H0 is the empty graph (containing no edges).
We define H j inductively by adding to H j−1 all edges of the form (v, f j (v)) over all v ∈ V . For j = 1, . . . , r,
let k j denote the number of connected components of H j .
Claim 9.10. If L : Fd → Fd is any linear map sending U to zero, then span{L(V )} has dimension at
most kr .
Proof. This is an easy corollary of Claim 9.6. If L(U) = 0 then, for every edge (x, y) in Hr , we
have L(x) ∼ L(y). Since the relation ∼ is transitive, each connected component is contained in a one
dimensional subspace after applying L.
Let k0j denote the number of connected components of H j of size at most n1−10ε . Call these the “small”
components of H j . The next claim bounds the expectation of k0j .
Claim 9.11. Let 1 ≤ j ≤ r. Then,
E[k0j ] ≤ k0j−1 (1 − Ω(δ 17 n−3ε )) .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 29
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Proof. Let s = k0j−1 and let K1 , . . . , Ks be the small components of H j−1 . Pick representatives ui ∈ Ki in
each of the components. For each i = 1, . . . , s, let Xi be an indicator variable so that Xi = 1 if f j (ui ) ∈ V \Ki
(that is, f j (ui ) is defined and does not belong to Ki ) and Xi = 0 otherwise (if either f j (ui ) = ⊥ or if it is
defined but in Ki ). By Claim 9.9, we have that
E[Xi ] = Pr[Xi = 1] ≥ Ω(δ 17 n−3ε ) .
Since having an edge (ui , f j (ui )) going from ui to some vertex outside Ki “merges” Ki with another
component, we have that
1 s
k0j ≤ s − ∑ Xi .
2 i=1
Taking expectations, and using the above bound on the expectations of the Xi , we get
E[k0j ] ≤ s(1 − Ω(δ 17 n−3ε ))
as was required.
Thus, for each j = 1, 2, . . . , r there is a choice of a set A j ⊂ Si j such that H j has at most k0j−1 (1 −
Ω(δ 17 n−3ε ))) small components. Taking r = n4ε , we get that there is a choice of U for which Hr does
not have any small components. Since the number of large components is at most n10ε , we get:
Claim 9.12. There is a choice of U for which Hr has at most n10ε connected components.
To conclude, we observe that, since we are using the modified distribution µ 0 , we have
|U| ≤ r · n1/4+3ε ≤ n1/4+7ε
and, using Claim 9.10, we have that, setting U to zero by a linear map, reduces the dimension of V to at
most n10ε . This completes the proof of Lemma 9.2.
10 Putting it all together: proof of Theorem 2.3
We will first prove that any (3, δ )-LCC over R contains a large subset of small dimension. Later we will
iterate this to get a global dimension bound.
Lemma 10.1. Suppose n > (1/δ )ω(1) and let 0 < ε < 1/50. Let V = (v1 , . . . , vn ) ∈ (Rd )n be a (3, δ )-LCC.
Then, there exists a subset U ⊂ V of size at least
|U| ≥ (δ 3 /300)n
and dimension at most
dim(U) ≤ max{8δ 6 d, n1/2−ε/16 } .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 30
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
Proof. We will prove the lemma by first applying Lemma 8.2 to show that V has a large sub-LCC V 0 in
which the triples cluster. Then, we will apply Lemma 9.1 to show that V 0 has a large low-rank sublist.
The details follow.
Set β1 = ε/4 and apply Lemma 8.2 with β = β1 . To apply the lemma we require that V does not
contain a subset U of size (δ 2 /288)n and rank at most max{8δ 6 d, n1/2−β1 /4 } = max{8δ 6 d, n1/2−ε/16 }.
If this is the case, then our proof is done and there is no need to continue.
Having applied Lemma 8.2, we obtain a (3, δ 0 )-LCC V 0 ⊂ V with n0 = |V 0 | ≥ (δ /10)n, d 0 = dim(V 0 ) ≤
d, δ 0 ≥ δ 2 /4 and sets S1 , . . . , Sm which cluster all the triples in the matchings Mv0 , v0 ∈ V 0 used to decode
V 0 so that
|Si | ≤ O(n0 /δ 06 d 0 )
and
Ω(δ 019 d 03 /n01+2β1 ) ≤ m ≤ O(n01+2β1 /δ 010 d 0 ) .
We now apply Lemma 9.1 with β = 2β1 < ε/2 and the same ε to conclude that there exist a subset
V 00 ⊂ V 0 of size
n00 = |V 00 | ≥ (δ 0 /2)n0 ≥ (δ 2 /8)(δ /10)n ≥ (δ 3 /80)n
and dimension
dim(V 00 ) ≤ n001/2−ε ≤ max{8δ 6 d, n1/2−ε/16 } ,
as was required.
We now prove an amplification lemma which uses Lemma 10.1 iteratively. For this lemma we will
use the following convenient notation. If S ⊂ V is a subset of V , we denote by spanV (S) ⊂ V the subset
of elements of V that are spanned by elements of S. (We think of all these as lists/multisets.)
Lemma 10.2 (Amplification lemma). Suppose n > (1/δ )ω(1) and let 0 < ε < 1/50. Let V = (v1 , . . . , vn ) ∈
(Rd )n be a linear (3, δ )-LCC. Suppose S ⊂ V is such that spanV (S) = S and S 6= V . Then there is a set
S ⊆ S0 ⊆ V with spanV (S0 ) = S0 such that
1. either S0 = V or |S0 | ≥ |S| + (δ 4 /400)n;
2. dim(S0 ) ≤ dim(S) + max{δ 6 d, n1/2−ε/16 }.
We defer the proof of the lemma to the end of this section and proceed with the proof of Theorem 2.3.
Proof of Theorem 2.3. Let V = (v1 , . . . , vn ) ∈ (Rd )n be a linear (3, δ )-LCC. We will prove the theorem
with ε = 1/1000 We now apply Lemma 10.2 with ε1 = 1/51 iteratively. Start with S1 = 0/ and apply
Lemma 10.2 repeatedly to obtain sets S2 , S3 , . . . , such that for all i,
|Si | ≥ |Si−1 | + (δ 4 /400)n
and
dim(Si ) ≤ dim(Si−1 ) + max{δ 6 d, n1/2−ε1 /16 } .
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 31
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Since the size of Si cannot grow beyond n, the process will terminate after at most m = b400/δ 4 c steps,
yielding Sm = V . We then get that
dim(Sm ) = dim(V ) ≤ (400/δ 4 ) max{δ 6 d, n1/2−ε1 /16 } = max{(400δ 2 )d, (400/δ 4 )n1/2−ε1 /16 } .
Without loss of generality, for the proof of the theorem we can assume that δ 2 < 1/500. Thus it must
be that
d = dim(V ) ≤ (400/δ 4 )n1/2−ε1 /16 ≤ n1/2−ε .
This completes the proof of Theorem 2.3.
10.1 Proof of Lemma 10.2
Observe that for v ∈ V \ S, all 3 points of any triple in Mv cannot be in S since spanV (S) = S. Thus we
may assume that |S| ≤ (1 − δ )n, since otherwise each vector in V \ S would be spanned by the points of S
and we would be done.
Case 1: There exists a v ∈ V \ S such that δ n/4 of the triples in Mv have two of their points contained
in S. In this case let S0 = spanV ({v} ∪ S). Then |S0 | ≥ |S| + (δ /4)n, and dim(S0 ) ≤ dim(S) + 1.
If Case 1 does not hold then each v ∈ V \ S, Mv has 3δ n/4 of its triples intersecting S in either one
or zero points. Let us call a point v type-zero if if has at least 3δ n/8 of its triples contained in V \ S and
type-one otherwise. Notice that, if v is type-one, then it must have at least 3δ n/8 of its triples intersecting
S in exactly one point. We now separate into two additional cases.
Case 2: There are at most δ n/4 type-one points. Let V 0 ⊂ V \ S be the set of all type-zero points.
Observe that, since |S| ≤ (1 − δ )n, we have |V 0 | ≥ 3δ n/4. Also observe that the vectors in V 0 form a
(3, δ /8)-LCC since each point in V 0 has at least 3δ n/8 − δ n/4 = δ n/8 ≥ (δ /8)|V 0 | triples in its matching
contained in V 0 . Using Lemma 10.1 on V 0 we conclude that there is a subset U ⊂ V 0 of size
|U| ≥ (δ 3 /300)|V 0 | ≥ (δ 4 /400)n
and dimension
dim(U) ≤ max{8(δ /8)6 d 0 , |V 0 |1/2−ε/16 } ≤ max{δ 6 d, n1/2−ε/16 } .
Setting S0 = S ∪U we are done.
Case 3: There are at least δ n/4 type-one points. In this case, there are δ n/4 points v in V \ S,
each having at least 3δ n/8 of the triples in Mv intersecting S in exactly one point. Let A be a linear
transformation whose kernel equals span(S). After applying A to V \ S we obtain a (2, 3δ /4) LDC
decoding the δ n/4 type-one points. Thus the δ n/4 points (after we apply the mapping A to them) must
span at most poly(1/δ ) log n ≤ max{δ 6 d, n1/2−ε/16 } dimensions by Theorem 4.5. Thus, adding them to
S will increase the dimension of its span by at most this number. This completes the proof also in this
case.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 32
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
References
[1] S ANJEEV A RORA , C ARSTEN L UND , R AJEEV M OTWANI , M ADHU S UDAN , AND M ARIO
S ZEGEDY: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555,
1998. Preliminary versions in FOCS’92 and ECCC. [doi:10.1145/278298.278306] 2
[2] S ANJEEV A RORA AND S HMUEL S AFRA: Probabilistic checking of proofs: A new characterization
of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]
2
[3] L ÁSZLÓ BABAI , L ANCE F ORTNOW, AND C ARSTEN L UND: Non-deterministic exponential time
has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. Preliminary version in
FOCS’90. [doi:10.1007/BF01200056] 2
[4] L ÁSZLÓ BABAI , L ANCE F ORTNOW, N OAM N ISAN , AND AVI W IGDERSON: BPP has subexponen-
tial time simulations unless EXPTIME has publishable proofs. Comput. Complexity, 3(4):307–318,
1993. Preliminary version in SCT’91. [doi:10.1007/BF01275486] 2
[5] B OAZ BARAK , Z EEV DVIR , A MIR Y EHUDAYOFF , AND AVI W IGDERSON: Rank bounds for
design matrices with applications to combinatorial geometry and locally correctable codes. In Proc.
43rd STOC, pp. 519–528. ACM Press, 2011. [doi:10.1145/1993636.1993705, arXiv:1009.4375] 2,
3, 6, 8, 9
[6] F RANCK BARTHE: On a reverse form of the Brascamp-Lieb inequality. Inventiones Math.,
134(2):335–361, 1998. [doi:10.1007/s002220050267, arXiv:math/9705210] 11, 12, 13
[7] D ONALD B EAVER AND J OAN F EIGENBAUM: Hiding instances in multioracle queries. In Proc. 7th
Symp. Theoretical Aspects of Comp. Sci. (STACS’90), volume 415 of LNCS, pp. 37–48. Springer,
1990. [doi:10.1007/3-540-52282-4_30] 2
[8] A RNAB B HATTACHARYYA , Z EEV DVIR , A MIR S HPILKA , AND S HUBHANGI S ARAF: Tight lower
bounds for 2-query LCCs over finite fields. Combinatorica, 36(1):1–36, 2016. Preliminary version
in FOCS’11. [doi:10.1007/s00493-015-3024-z] 3, 6, 9
[9] M ANUEL B LUM AND S AMPATH K ANNAN: Designing programs that check their work. J. ACM,
42(1):269–291, 1995. Preliminary version in STOC’89. [doi:10.1145/200836.200880] 2
[10] M ANUEL B LUM , M ICHAEL L UBY, AND RONITT RUBINFELD: Self-testing/correcting with appli-
cations to numerical problems. J. Comput. Sys. Sci., 47(3):549–595, 1993. Preliminary version in
STOC’90. [doi:10.1016/0022-0000(93)90044-W] 2
[11] B ENNY C HOR , E YAL K USHILEVITZ , O DED G OLDREICH , AND M ADHU S UDAN: Private
information retrieval. J. ACM, 45(6):965–981, 1998. Preliminary version in FOCS’95.
[doi:10.1145/293347.293350] 2
[12] Z EEV DVIR: On matrix rigidity and locally self-correctable codes. Comput. Complexity, 20(2):367–
388, 2011. Preliminary version in CCC’10. [doi:10.1007/s00037-011-0009-1] 2
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 33
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
[13] Z EEV DVIR , PARIKSHIT G OPALAN , AND S ERGEY Y EKHANIN: Matching vector codes. SIAM J.
Comput., 40(4):1154–1178, 2011. Preliminary version in FOCS’10. [doi:10.1137/100804322] 2
[14] Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON: Breaking the quadratic bar-
rier for 3-LCC’s over the reals. In Proc. 46th STOC, pp. 784–793. ACM Press, 2014.
[doi:10.1145/2591796.2591818, arXiv:1311.5102] 1
[15] Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON: Improved rank bounds for de-
sign matrices and a new proof of Kelly’s theorem. Forum of Math., Sigma, 2(4), 2014.
[doi:10.1017/fms.2014.2, arXiv:1211.0330] 2, 3, 8
[16] Z EEV DVIR AND A MIR S HPILKA: Locally decodable codes with 2 queries and polynomial identity
testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Preliminary version in
STOC’05. [doi:10.1137/05063605X] 2, 3, 11
[17] K LIM E FREMENKO: 3-query locally decodable codes of subexponential length. SIAM J. Comput.,
41(6):1694–1703, 2012. Preliminary version in STOC’09. [doi:10.1137/090772721] 2
[18] O DED G OLDREICH , H OWARD J. K ARLOFF , L EONARD J. S CHULMAN , AND L UCA T REVISAN:
Lower bounds for linear locally decodable codes and private information retrieval. Comput. Com-
plexity, 15(3):263–296, 2006. Preliminary version in CCC’02. [doi:10.1007/s00037-006-0216-3]
3
[19] J ONATHAN K ATZ AND L UCA T REVISAN: On the efficiency of local decoding procedures for error-
correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000. [doi:10.1145/335305.335315]
2, 3
[20] N EERAJ K AYAL AND S HUBHANGI S ARAF: Blackbox polynomial identity testing for
depth 3 circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.67] 2
[21] I OANNIS K ERENIDIS AND RONALD DE W OLF: Exponential lower bound for 2-query locally
decodable codes via a quantum argument. J. Comput. Sys. Sci., 69(3):395–420, 2004. Preliminary
version in STOC’03. [doi:10.1016/j.jcss.2004.04.007, arXiv:quant-ph/0208062] 3
[22] S WASTIK KOPPARTY: List-decoding multiplicity codes. Theory of Computing, 11(5):149–182,
2015. [doi:10.4086/toc.2015.v011a005] 2
[23] S WASTIK KOPPARTY, S HUBHANGI S ARAF, AND S ERGEY Y EKHANIN: High-rate codes with
sublinear-time decoding. J. ACM, 61(5):28:1–28:20, 2014. Preliminary version in STOC’11.
[doi:10.1145/2629416] 2
[24] P ETER D. L AX: Linear Algebra and Its Applications. Wiley, 2007. 13
[25] R ICHARD J. L IPTON: Efficient checking of computations. In Proc. 7th Symp. Theoretical Aspects
of Comp. Sci. (STACS’90), volume 415 of LNCS, pp. 207–215. Springer, 1990. [doi:10.1007/3-540-
52282-4_44] 2
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 34
L OWER B OUND FOR 3-Q UERY L OCALLY C ORRECTABLE C ODES OVER THE R EALS
[26] C ARSTEN L UND , L ANCE F ORTNOW, H OWARD J. K ARLOFF , AND N OAM N ISAN: Algebraic
methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in
FOCS’90. [doi:10.1145/146585.146605] 2
[27] RONITT RUBINFELD AND M ADHU S UDAN: Robust characterizations of polynomi-
als with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996.
[doi:10.1137/S0097539793255151] 2
[28] A DI S HAMIR: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146609] 2
[29] L ESLIE G. VALIANT: Graph-theoretic arguments in low-level complexity. In Proc. 6th Symp. Math.
Found. Comput. Sci. (MFCS’77), volume 53 of LNCS, pp. 162–176. Springer, 1977. [doi:10.1007/3-
540-08353-7_135] 2
[30] DAVID P. W OODRUFF: New lower bounds for general locally decodable codes. Electron. Colloq.
on Comput. Complexity (ECCC), 14(6), 2007. Available at ECCC. 3
[31] DAVID P. W OODRUFF: A quadratic lower bound for three-query linear locally decodable codes
over any field. J. Comput. Sci. Techn., 27(4):678–686, 2012. Preliminary version in RANDOM’10.
[doi:10.1007/s11390-012-1254-8] 3
[32] S ERGEY Y EKHANIN: Towards 3-query locally decodable codes of subexponential length. J. ACM,
55(1):1:1–1:16, 2008. Preliminary version in STOC’07. [doi:10.1145/1326554.1326555] 2
AUTHORS
Zeev Dvir
Associate professor
Department of Computer Science and Department of Mathematics
Princeton University
zdvir princeton edu
http://www.cs.princeton.edu/~zdvir/
Shubhangi Saraf
Assistant professor
Department of Computer Science and Department of Mathematics
Rutgers University
shubhangi saraf rutgers edu
https://www.math.rutgers.edu/~ss1984/
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 35
Z EEV DVIR , S HUBHANGI S ARAF, AND AVI W IGDERSON
Avi Wigderson
Professor
School of Mathematics
Institute for Advanced Study
avi ias edu
http://www.math.ias.edu/~avi
ABOUT THE AUTHORS
Z EEV DVIR was born in Jerusalem, Israel. He received his Ph. D. from the Weizmann
Institute in Israel in 2008. His advisors were Ran Raz and Amir Shpilka. He has a broad
interest in theoretical computer science and mathematics and especially in computational
complexity, pseudorandomness, coding theory and discrete mathematics.
S HUBHANGI S ARAF grew up in Pune, India. She received her Ph. D. from the Massachusetts
Institute of Technology under the guidance of Madhu Sudan. Details about Shubhangi’s
early career can be found in her bio sketch in Volume 13, Article 6 of Theory of Comput-
ing.
Shubhangi is broadly interested in complexity theory, coding theory and pseudorandom-
ness. Recently she has been captivated by questions related to understanding the power
and limitations of algebraic computation, as well as to understanding the potential of
“locality” in algorithms for codes. In her spare time Shubhangi enjoys reading, cooking,
long walks, and exploring cafés and restaurants. Her little toddler is a constant source of
joy and amazement, and also makes sure there isn’t much time to spare.
AVI W IGDERSON was born in Haifa, Israel in 1956, and received his Ph. D. in 1983 at
Princeton University under Dick Lipton. He enjoys and is fascinated with studying the
power and limits of efficient computation, and the remarkable impact of this field on
understanding our world. Avi’s other major source of fascination and joy are his three
kids, Eyal, Einat, and Yuval.
T HEORY OF C OMPUTING, Volume 13 (11), 2017, pp. 1–36 36