Authors Jop Bri{\"e}t, Zeev Dvir, Sivakanth Gopi,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24
www.theoryofcomputing.org
Outlaw Distributions and
Locally Decodable Codes
Jop Briët∗ Zeev Dvir† Sivakanth Gopi‡
Received August 11, 2017; Revised June 20, 2019; Published October 29, 2019
Abstract: Locally decodable codes (LDCs) are error correcting codes that allow for decod-
ing of a single message bit using a small number of queries to a corrupted encoding. Despite
decades of study, the optimal trade-off between query complexity and codeword length is far
from understood. In this work, we give a new characterization of LDCs using distributions
over Boolean functions whose expectation is hard to approximate (in L∞ norm) with a small
number of samples. We coin the term “outlaw distributions” for such distributions since they
“defy” the Law of Large Numbers. We show that the existence of outlaw distributions over
sufficiently “smooth” functions implies the existence of constant query LDCs and vice versa.
We give several candidates for outlaw distributions over smooth functions coming from finite
field incidence geometry, additive combinatorics and hypergraph (non)expanders.
We also prove a useful lemma showing that (smooth) LDCs which are only required to
work on average over a random message and a random message index can be turned into
true LDCs at the cost of only constant factors in the parameters.
A conference version of this paper appeared in the Proc. of the 8th Innovations in Theoretical Computer Science Conf. ITCS
2017 [7]. The present version includes a new application of the results to a problem from additive combinatorics (Corollary 1.7)
and corrects a minor error in the proof of Theorem 3.1.
∗ Supported by a VENI grant and the Gravitation-grant NETWORKS-024.002.003 from the Netherlands Organisation for
Scientific Research (NWO).
† Research supported by NSF CAREER award DMS-1451191 and NSF grant CCF-1523816.
‡ Research supported by NSF grant CCF-1523816 and by the Sloan foundation.
ACM Classification: G.2
AMS Classification: 68Q87, 68R05, 05D40, 68R10, 05E99, 05B25
Key words and phrases: locally decodable codes, Boolean functions, incidence geometry, pseudoran-
domness, influence, gaussian width, hypergraphs
© 2019 Jop Briët, Zeev Dvir, and Sivakanth Gopi
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a012
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
1 Introduction
Error correcting codes (ECCs) solve the basic problem of communication over noisy channels by encoding
a message into a codeword from which, even if the channel partially corrupts it, the message can later be
retrieved. Pioneering work of Shannon [32] showed the existence of optimal (capacity-achieving) ECCs,
giving one of the earliest applications of the probabilistic method. The problem of explicitly constructing
such codes has fueled the development of coding theory ever since. Similarly, the exploration of many
other fascinating structures, such as Ramsey graphs, expander graphs, two-source extractors, etc., began
with a striking existence proof via the probabilistic method, only to be followed by decades of catch-up
work on explicit constructions. Locally decodable codes (LDCs) are a special class of error correcting
codes whose development has not followed this line. The defining feature of LDCs is that they allow for
ultrafast decoding of single message bits, a property that typical ECCs lack, as their decoders must read an
entire (possibly corrupted) codeword to achieve the same. They were first formally defined in the context
of channel coding in [25], although they (and the closely related locally correctable codes) implicitly
appeared in several previous works in other settings, such as computation and program checking [4, 5],
probabilistically checkable proofs [3, 2] and private information retrieval schemes (PIRs) [11]. More
recently, LDCs have even found applications in Banach-space geometry [9] and LDC-inspired objects
called local reconstruction codes found applications in fault tolerant distributed storage systems [21].
See [40] for a survey of LDCs and some of the applications.
Despite their many applications, our knowledge of LDCs is very limited; the best constructions
we know are far from what is currently known about their limits. Although standard random (linear)
ECCs do allow for some weak local-decodability, they are outperformed by even the earliest explicit
constructions [26]. All the known constructions of LDCs were obtained by explicitly designing such
codes using some algebraic objects like low-degree polynomials or matching vectors [40].
In this paper, we give a characterization of LDCs in probabilistic and geometric terms, making them
amenable to probabilistic constructions. On the flip side, these characterizations might also be easier to
work with for the purpose of showing lower bounds. We will make this precise in the next section. Let us
first give the formal definition of an LDC.
Definition 1.1 (Locally decodable code). For positive integers k, n, q and parameters η, δ ∈ (0, 1/2],
a map C : {0, 1}k → {0, 1}n is a (q, δ , η)-locally decodable code if, for every i ∈ [k], there exists a
randomized decoder (a probabilistic algorithm) Ai such that:
• For every message x ∈ {0, 1}k and string y ∈ {0, 1}n that differs from the codeword C(x) in at
most δ n coordinates,
1
Pr[Ai (y) = xi ] ≥ + η. (1.1)
2
• The decoder Ai non-adaptively1 queries at most q coordinates of y.2
1 Any adaptive q-query decoder can be converted into a (2q − 1)-query non-adaptive decoder. Since in this paper we only
deal with constant q, we will assume that the decoders are always non-adaptive.
2 We can assume that on input y ∈ {0, 1}n , the decoder A first samples a set S ⊆ [n] of at most q coordinates according to a
i
probability distribution depending on i only and then returns a random bit depending only on i, S and the values of y at S.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 2
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
Known results. The main parameters of LDCs are the number of queries q and the length n of the
encoding as a function of k and q, typically the parameters δ , η are fixed constants. The simplest example
is the Hadamard code, which is a 2-query LDC with n = 2k . The 2-query regime is the only nontrivial
case where optimal lower bounds are known: it was shown in [27, 20] that exponential length is necessary.
In general, Reed-Muller codes of degree q − 1 are q-query LDCs of length n = exp(O(k1/q−1 )). For a
long time, these were the best constructions for constant q, until in breakthrough works, Yekhanin [39]
√
and Efremenko [16] constructed 3-query LDCs with subexponential length n = exp(exp(O( log k))).
More generally they constructed 2r -query LDCs with length n = exp(exp(O(log1/r k))). For q ≥ 3, the
best currently known lower bounds leave huge gaps, giving only polynomial bounds. A 3-query LDC
must have length n ≥ Ω̃(k2 ), and more generally for a q-query LDC, n ≥ Ω̃(k1+1/(dq/2e−1) ) [27, 38].3
LDCs where the codewords are over a large alphabet are studied because of their relation to private
information retrieval schemes [11, 25]. In [15], 2-query LDCs of length n = exp(ko(1) ) over an alphabet
of size exp(ko(1) ) were constructed. There is also some exciting recent work on LDCs where the number
of queries grows with k, in which case there are explicit constructions with constant rate (that is, n = O(k))
√
and query complexity q = exp(O( log n)); in fact we can even achieve the optimal rate-distance tradeoff
of traditional error correcting codes [29, 28, 22]. We cannot yet rule out the exciting possibility that
constant rate LDCs with polylogarithmic query complexity exist.
1.1 LDCs from distributions over smooth Boolean functions
Our main result shows that LDCs can be obtained from “outlaw” distributions over “smooth” functions.
The term outlaw refers to the Law of Large Numbers, which says that the average of independent samples
tends to the expectation of the distribution from which they are drawn. Roughly speaking, a probability
distribution is an outlaw if many samples are needed for a good estimation of the expectation and a smooth
function over the n-dimensional Boolean hypercube is one that has no influential variables. Paradoxically,
while many instances of the probabilistic method use the fact that sample means of a small number of
independent random variables tend to concentrate around the true mean, as captured for example by
the Chernoff bound, our main result requires precisely the opposite. We show that if at least k samples
from a distribution over smooth functions are needed to approximate the mean, then there exists an
O(1)-query LDC sending {0, 1}Ω(k) to {0, 1}n , where the hidden constants depend only the smoothness
and mean-estimation parameters.
To make this precise, we now formally define smooth functions and outlaw distributions. Given a
function f : {−1, 1}n → R, its spectral norm is defined by
k f ksp = ∑ | fb(S)|,
S⊂[n]
where fb(S) are the Fourier coefficients of f (see Section 2 for basics on Fourier analysis). In words,
the spectral norm of f is the `1 -norm of its spectrum (i.e., its Fourier coefficients).4 We also consider
the supremum norm, k f kL∞ = sup{| f (x)| : x ∈ {−1, 1}n }. It follows from the Fourier inversion formula
that k f kL∞ ≤ k f ksp . The discrete derivative of f in direction i ∈ [n] is the function (Di f )(x) = ( f (x) −
3 We use Ω̃( ), Õ( ), ω̃( ), õ( ) to hide polylogarithmic factors through out this paper.
4 The spectral norm is also known as the algebra norm or Wiener norm and is also denoted by k f k or || fˆ|| [23, 33].
A 1
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 3
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
f (xi ))/2, where xi is the point that differs from x on the i-th coordinate. Smooth functions are functions
whose discrete derivatives have small spectral norms.
Definition 1.2 (σ -smooth functions). For σ > 0, a function f : {−1, 1}n → R is σ -smooth if for every
i ∈ [n], we have kDi f ksp ≤ σ /n.
Intuition for the above definition may be gained from the fact that smooth functions have no influential
variables. The influences, (Ex∈{−1,1}n [(Di f )(x)2 ])1/2 , measure the extent to which changing the i-th
coordinate of a randomly chosen point changes the value of f . Since kDi f kL∞ ≤ kDi f ksp , the directional
derivatives of σ -smooth functions are uniformly bounded by σ /n, which is a much stronger condition
than saying that the derivatives are small on average. Outlaws are defined as follows.
Definition 1.3 (Outlaw). Let n be a positive integer and µ be a probability distribution over real-valued
functions on {−1, 1}n . For a positive integer k and ε > 0, say that µ is a (k, ε)-outlaw if for independent
random µ-distributed functions f1 , . . . , fk and f¯ = Eµ [ f ],
" #
1 k
E ∑ ( fi − f¯) L∞ ≥ ε.
k i=1
Denote by κµ (ε) the largest integer k such that µ is a (k, ε)-outlaw.
To approximate the true mean of an outlaw µ to within ε on average in the L∞ -distance, one thus
needs κµ (ε) + 1 samples. Note that if µ is a distribution over σ -smooth functions, then the distribution µ̃
obtained by scaling functions in the support of µ by 1/σ is a distribution over 1-smooth functions and
κµ̃ (ε/σ ) = κµ (ε).
Our main result is then as follows.
Theorem 1.4 (Main theorem). Let n be a positive integer and ε > 0. Let µ be a probability distribution
over 1-smooth functions on {−1, 1}n and k = κµ (ε). Then, there exists a (q, δ , η)-LDC sending {0, 1}l
to {0, 1}2n where l = Ω(ε 2 k/ log(1/ε)), q = O(1/ε), δ = Ω(ε) and η = Ω(ε). Additionally, if µ is
supported on degree-d polynomials, then we can take q = d.
Note that the smoothness requirement is essential. For example the uniform distribution over the
n dictator functions fi (x) = xi for i ∈ [n] is an (n/2, 1)-outlaw, but it cannot imply constant rate since
constant query LDCs which we know do not exist. In fact we establish a converse to Theorem 1.4, showing
that its hypothesis is essentially equivalent to the existence of LDCs in the small query complexity regime.
Theorem 1.5. If there exists a C : {0, 1}k → {0, 1}n is a (q, δ , η)-LDC, then there exists a probability
distribution µ over 1-smooth degree-q polynomials on {−1, 1}n such that
κµ (ε) ≥ ηk
where ε = ηδ /(q2q/2 ).
Theorem 1.5 can in turn convert the problem of proving lower bounds on the length of LDCs to a
problem on Banach space geometry. In particular, for a distribution µ over 1-smooth degree-q polynomials
on {0, 1}n , one can upper bound κµ (ε) in terms of type constants of the space formed by the q-fold
injective tensor product of `nq with itself (or the space of q-tensors of size n viewed as multilinear forms
on `nq ) [6]. Unfortunately, little is known about these constants, however.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 4
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
Candidate outlaws. One scenario in which outlaw distributions can be obtained is using incidence
geometry in finite fields. In particular, the following result can be derived from our main theorem (stated
a bit informally here, see Section 6.1 for the formal version).
Corollary 1.6. Let p > 2 be a fixed prime. Suppose that for a random set of directions, D ⊆ Fnp , of size
|D| ≤ k, with probability at least 1/2, there exists a set B ⊂ Fnp of size |B| ≥ Ω(pn ) which does not contain
n
any lines with direction in D. Then, there exists a p-query LDC sending {0, 1}Ω(k) to {0, 1}2p .
The assumption in Corollary 1.6 that D be random is essential for it to be potentially interesting for
LDCs. If we instead ask that every set D of directions satisfy the condition—as we did in the conference
version of this paper—then letting D be a subspace shows that k must be smaller than a constant depending
only on p and ε by Theorem 6.2 below.
The analogue of Corollary 1.6 in Z/NZ where lines correspond to arithmetic progressions and
directions correspond to common differences can also be used to construct LDCs. This setting was
studied in [17], where it is shown that if D is a random subset of Z/NZ of size ω(log N), then almost
surely every dense subset of Z/NZ contains a 3-term arithmetic progression with common difference
in D. In [18], the same authors showed that for every fixed integer q ≥ 4, the same holds for q-term
arithmetic progressions if D has of size ω(N 1−1/q ).5 Our main result, together with the best currently
known lower bounds on LDCs [27, 38] can be used to improve the bounds of [18] on random differences
in Szemerédi’s theorem as shown in the following corollary.6
Corollary 1.7. Let q ≥ 3 be an integer and α ∈ (0, 1]. Let D ⊆ Z/NZ be a uniformly random subset
of size ω̃(N 1−1/dq/2e ). Then, almost surely as N −→ ∞, it holds that every subset A ⊂ Z/NZ of size at
least αN contains a q-term arithmetic progression with common difference in the set D.
Another setting in which our approach leads to interesting open problems is in relation to pseudoran-
dom hypergraphs. Consider a partition of the complete bipartite graph Kn,n into n perfect matchings. It is
known that picking k = O(log n) of these matchings at random will give us a pseudorandom (expander)
graph (of degree k). For some particular partitions (e.g., given by an Abelian group) this bound is tight.
The questions arising from our approach can be briefly summarized as follows: Can one find an n-vertex
hypergraph H (say three uniform to be precise) and a partition of H into matchings so that, to get a
pseudorandom hypergraph (defined appropriately) one needs at least k random matchings. This would
give a code sending Ω(k)-bit messages with encoding length O(n) and so, becomes interesting when k is
super-polylogarithmic in n. We elaborate on this in Section 6.2.
1.2 Techniques
Our proof of Theorem 1.4 proceeds in two steps. The first step consists of turning an outlaw over smooth
functions into a seemingly crude type of LDC that is only required to work on average over a uniformly
distributed message and a uniformly distributed message index. We call such codes average-case smooth
5 Their results are actually stated slightly differently. Instead, their random set D is formed by putting each element of Z/NZ
in it independently with probability p = ω(N −1/q ). However, standard arguments show that the two statements are equivalent.
6 In [8], the first and third authors derive Corollary 1.7 in addition to another result in probabilistic combinatorics from first
principles (which is to say, not through LDCs).
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 5
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
codes (see below). The second step consists of showing that such codes are in fact not much weaker than
honest LDCs.
From outlaws to average-case smooth codes. The key ingredient for the first step is symmetrization,
a basic technique from probability theory. We briefly sketch how this is used (we refer to Section 3 for
the full proof). Suppose that f1 , . . . , fk are independent samples distributed according to a (k, ε)-outlaw
with expectation f¯ and supported on 1-smooth functions. We introduce an independent copy7 fi0 of fi
for each i ∈ [k] and consider the symmetrically distributed random functions fi − fi0 . Since f¯ = E[ fi0 ] for
each i ∈ [k], Jensen’s inequality and Definition 1.3 imply that
E k( f1 − f10 ) + · · · + ( fk − fk0 )kL∞ ≥ E k( f1 − E[ f10 ]) + · · · + ( fk − E[ fk0 )kL∞ ≥ εk.
Since the random functions fi − fi0 are independent and symmetric, we get that for independent uniformly
random signs x1 , . . . , xk ∈ {−1, 1}, the above left-hand side equals
E kx1 ( f1 − f10 ) + · · · + xk ( fk − fk0 )kL∞ .
The triangle inequality and the Averaging Principle then give that there exist fixed smooth functions
f1? , . . . , fk? such that on average over the random signs, we have
E kx1 f1? + · · · + xk fk? kL∞ ≥ εk/2.
(1.2)
To get an average-case smooth code out of this, we view each sequence x = (x1 , . . . , xk ) as a k-bit message
and choose an arbitrary n-bit string for which the L∞ -norm in (1.2) is achieved to be the its encoding, C(x).
This gives a map C : {−1, 1}k → {0, 1}n satisfying
E x1 f1? (C(x)) + · · · xk fk? (C(x)) ≥ εk/2.
Equivalently, for uniform x and i, we have
1 ε
Pr[A( fi? (C(x))) = xi ] ≥ +
2 4
where A(α) (for α ∈ [−1, 1]) is a ±1-valued random variable with expected value α.8 Finally, we use
the smoothness property to transform the fi? into decoders with the desired properties. This is done in
Section 3. It is in the application of the Averaging Principle where the probabilistic method appears in
our construction of LDCs.
7 in this context sometimes referred to as a “ghost copy” as it will later disappear again
8 Note that a 1-smooth function is bounded by 1 since k f k ≤ k f k ≤ n kD f k ≤ n · (1/n) ≤ 1.
L∞ sp ∑i=1 i sp
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 6
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
Average-case smooth codes are LDCs. Katz and Trevisan [25] observed that LDC decoders must
have the property that they select their queries according to distributions that do not favor any particular
coordinate. The intuition for this is that if they did favor a certain coordinate, then corrupting that
coordinate would cause the decoder to err with too high a probability. If instead, queries are sampled
according to a “smooth” distribution, they will all fall on uncorrupted coordinates with good probability
provided the fraction δ of corrupted coordinates and query complexity q aren’t too large. The following
definition allows us to make this intuition precise.
Definition 1.8 (Smooth code). For positive integers k, n, q and parameters η ∈ (0, 1/2] and c > 0, a map
C : {0, 1}k → {0, 1}n is a (q, c, η)-smooth code if, for every i ∈ [k], there exists a randomized decoder
Ai : {0, 1}n → {0, 1} such that:
• For every x ∈ {0, 1}k ,
1
Pr xi = Ai C(x) ≥ + η.
(1.3)
2
• The decoder Ai non-adaptively queries at most q coordinates of C(x).
• For each j ∈ [n], the probability that Ai queries the coordinate j ∈ [n] is at most c/n.
The formal version of Katz and Trevisan’s observation is as follows.
Theorem 1.9 (Katz–Trevisan). If C : {0, 1}k → {0, 1}n is a (q, δ , η)-LDC, then C is a (q, q/δ , η)-smooth
code. Conversely, if C : {0, 1}k → {0, 1}n is a (q, c, η)-smooth code, then C is a (q, η/2c, η/2)-LDC.
Our second step in the proof of Theorem 1.4 is a stronger form of the converse part of Theorem 1.9.
We show that even smooth codes that are only required to work on average can be turned into LDCs,
losing only a constant factor in the rate and success probability.
Definition 1.10 (Average-case smooth code). A code as in Definition 1.8 is a (q, c, η)-average-case
smooth code if instead of the first item, (1.3) is required to hold only on average over uniformly distributed
x ∈ {0, 1}k and uniformly distributed i ∈ [k], which is to say that
1
Pr xi = Ai C(x) ≥ + η,
2
where the probability is taken over x, i and the randomness used by Ai .
Lemma 1.11. Let C : {0, 1}k → {0, 1}n be a (q, c, η)-average-case smooth code. Then, there exists an
(q, Ω(η/c), Ω(η))-LDC sending {0, 1}l to {0, 1}n where l = Ω(η 2 k/ log(1/η)).
The idea behind the proof of Lemma 1.11 is as follows. We first switch the message and codeword
alphabets to {−1, 1} and let fi : {−1, 1}k → [−1, 1] be the expected decoding function fi (z) = E[Ai (z)].
The properties of C then easily imply that the set T ⊆ [−1, 1]k given by T = {( f1 (z), . . . , fk (z)) : z ∈
{−1, 1}k } has large Gaussian width, in particular it holds that for a standard k-dimensional Gaussian
vector g, we have E[supt∈T hg,ti] & εk.9 Next, we employ a powerful result of [31] showing that T
9 We write A & B and A = Ω(B) interchangeably to mean that A ≥ cB for some absolute constant c > 0 independent of all
parameters involved.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 7
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
contains an l-dimensional hypercube-like structure with edge length some absolute constant c ∈ (0, 1], for
l & k. Roughly speaking, this implies that C is a smooth code on {−1, 1}l whose decoding probability
depends on ε and c. Finally, we obtain an LDC via an application of Theorem 1.9. The full proof is given
in Section 4.
1.3 Organization
Section 2 contains some preliminaries in Fourier analysis over the Boolean cube. In Section 3, we prove
our main theorem (Theorem 1.4) by first showing that outlaw distributions over smooth functions imply
existence of average-case smooth codes and using Lemma 1.11 to convert them to LDCs. In Section 4, we
prove Lemma 1.11 showing how to convert average-case smooth-codes to LDCs. In Section 5, we show
the converse to our main theorem (Theorem 1.5) showing how to get outlaw distributions over smooth
functions from LDCs. Finally in Section 6, we give some candidate constructions of outlaw distributions
over smooth functions using incidence geometry and hypergraph pseudorandomness.
2 Preliminaries
We recall a few basic definitions and facts from analysis over the n-dimensional Boolean hyper-
cube {−1, 1}n . Equipped with the coordinate-wise multiplication operation, the hypercube forms an
Abelian group whose group of characters is formed by the functions χS (x) = ∏i∈S xi for all S ⊆ [n]. The
characters form a complete orthonormal basis for the space of real-valued functions on {−1, 1}n endowed
with the inner product
h f , gi = Ex∈{−1,1}n [ f (x)g(x)],
where we use the notation Ea∈S to denote the expectation with respect to a uniformly distributed element a
over a set S. The Fourier transform of a function f : {−1, 1}n → R is the function fb : 2[n] → R defined
by fb(S) = h f , χS i. The Fourier inversion formula (which follows from orthonormality of the character
functions) asserts that
f = ∑ fb(S)χS .
S⊆[n]
Parseval’s Identity relates the L2 -norms of f and its Fourier transform by
1/2 1/2
Ex∈{−1,1}n [ f (x)2 ] = ∑ | fb(S)|2 .
S⊆[n]
A function f has degree q if fb(S) = 0 when |S| > q and the degree-q truncation of f , denoted f ≤q , is the
degree-q polynomial defined by
f ≤q = ∑ fb(S)χS .
|S|≤q
A function f is a q-junta if it depends only on a subset of q of its variables, or equivalently, if there exists
a subset T ⊆ [n] of size |T | ≤ q such that fb(S) = 0 for every S 6⊆ T . The i-th discrete derivative Di f is
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 8
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
the function (Di f )(x) = ( f (x) − f (xi ))/2, where xi is the point that differs from x on the i-th coordinate.
It is easy to show that the i-th discrete derivative in of a function f is given by
Di f = ∑ fb(S)χS .
S3i
Hence, it follows that kDi f kSpec = ∑S3i | fb(S)|.
3 From outlaws to average-case smooth codes
In this section we prove Theorem 1.4. For convenience, in the remainder of this paper, we switch the
message and codeword alphabets of all codes from {0, 1}n to {−1, 1}n . We begin by showing that
outlaw distributions over degree-q polynomials give q-query average-case smooth codes. Combined with
Lemma 1.11, this implies the second part of Theorem 1.4.
Theorem 3.1. Let µ be a probability distribution on 1-smooth degree-q polynomials on {−1, 1}n , let
ε ∈ (0, 1] and let k = κµ (ε). Then, there exists a (q, 2, ε/4)-average-case smooth code sending {−1, 1}k
to {−1, 1}2n .
Proof. The proof uses a symmetrization argument. Let F = ( f1 , . . . , fk ) and F0 = ( f10 , . . . , fk0 ) be two
k-tuples of independent µ-distributed random variables and let f¯ = Eµ [ f ]. Then, by definition of κµ (ε)
and triangle inequality for L∞ norm,
h 1 k i
ε ≤ EF ∑ ( fi − f¯)
k i=1 L∞
h 1 k i
fi − EF0 [ fi0 ]
= EF ∑
k i=1 L∞
h 1 k i
≤ EF,F0 ( fi − fi0 ) .
k∑i=1 L ∞
The random variables fi − fi0 are symmetrically distributed, which is to say that they have the same
distribution as their negations fi0 − fi . Since they are independent, it follows that for every x ∈ {−1, 1}k ,
the random variable x1 ( f1 − f10 ) + · · · + xk ( fk − fk0 ) has the same distribution as ( f1 − f10 ) + · · · + ( fk − fk0 ).
Therefore,
h 1 k i h h 1 k ii
0 0
EF,F0 ∑ ( f i − f i ) = Ex∈{−1,1} k EF,F 0 ∑ x i ( f i − f i )
k i=1 L∞ k i=1 L∞
h h 1 k ii
≤ 2EF Ex∈{−1,1}k ∑ xi fi .
k i=1 L∞
Applying the Averaging Principle to the outer expectation, we find that there exist 1-smooth degree-q
polynomials f1? , . . . , fk? : {−1, 1}n → R such that
h 1 k i ε
Ex∈{−1,1}k ∑ xi fi?
k i=1 L∞
≥ .
2
(3.1)
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 9
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
Let C̃ : {−1, 1}k → {−1, 1}n and σ : {−1, 1}k → {−1, 1} be such that for each x ∈ {−1, 1}k , we have
1 k ? 1 k ? 1 k
∑ xi fi? L∞ .
σ (x) ∑ iix f C̃(x) = ∑ iix f C̃(x) = (3.2)
k i=1 k i=1 k i=1
Let C : {−1, 1}k → {−1, 1}2n be the code given by C(x) = (C̃(x), σ (x)C̃(x)), that is, the concatenation
of C̃(x) and either an unchanged or a coordinate-wise negated copy of C̃(x) depending on the value
of σ (x). For each i ∈ [k], define the decoder Ai as follows. Let νi : 2[n] → [0, 1] be the probability
distribution defined by νi (S) = | fbi? (S)|/k fi? ksp . Given a string (z, z0 ) ∈ {−1, 1}2n , with probability
1 − k fi? ksp , the decoder Ai returns a uniformly random sign, and with probability k fi? ksp , it samples a set
S ⊆ [n] according to νi and a uniformly random s ∈ S, and returns χSr{s} (z) z0s . To see that k fi? ksp ≤ 1,
observe that for any 1-smooth function f , we have
n
1
k f ksp = ∑ | fb(S)| ≤ ∑ |S|| fb(S)| = ∑ ∑ | fb(S)| ≤ n = 1.
S⊂[n] S⊂[n] i=1 S3i n
Then, Ai queries at most q coordinates of (z, z0 ) and since fi? is 1-smooth, the probability that it
queries any coordinate j ∈ [2n] is at most kD j fi? ksp ≤ 1/n. k
For each x ∈ {−1, 1} , the expected output
of Ai on input C(x) satisfies E[Ai (C(x))] = σ (x) fi C̃(x) . Therefore, by (3.1) and (3.2), we have
?
1 1
Ex∈{−1,1}k ,i∈[k] [Pr[xi = Ai (C(x))]] = + E k [xi E[Ai (C(x))]]
2 2 x∈{−1,1} ,i∈[k]
1 1
= + Ex∈{−1,1}k ,i∈[k] xi σ (x) fi? C̃(x)
2 2
1 1 h 1 k i
?
= + Ex∈{−1,1}k x f
∑ i i L∞
2 2 k i=1
1 ε
≥ + .
2 4
Hence, C is a (q, 1/2, ε/4)-average-case smooth code.
The final step before the proof of Theorem 1.4 is to show that for any distribution µ over smooth
functions, there exists a distribution µ̃ over smooth functions of bounded degree that is not much more
concentrated than µ.
Lemma 3.2. Let µ be a probability distribution over 1-smooth functions and let ε > 0. Then, there exists
a probability distribution µ̃ over 1-smooth functions of degree q = 4/ε such that κµ̃ (ε/2) ≥ κµ (ε).
Proof. We first establish that smooth functions have low-degree approximations in the supremum norm.
If f : {−1, 1}n → R is 1-smooth, then
n n
q ∑ | fb(S)| ≤ ∑ |S|| fb(S)| = ∑ ∑ | fb(S)| = ∑ kDi f ksp ≤ 1.
|S|>q S⊂[n] i=1 S3i i=1
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 10
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
It follows that the degree-q truncation f ≤q satisfies
1 ε
f − f ≤q L∞ ≤ ∑ | fb(S)| ≤ = . (3.3)
|S|>q
q 4
Define µ̃ as follows: sample f according to µ and output f ≤q . Clearly, µ̃ is also a distribution over
1-smooth functions. For k = κµ (ε), we have
" #
1 k
E f1 ,..., fk ∼µ ∑ fi − E[ fi ] L∞ ≥ ε.
k i=1
Hence, by the triangle inequality and (3.3), we have
" #
1 k ε
E f1 ,..., fk ∼µ̃ ∑ fi − E[ fi ] ≥ ,
k i=1 L∞ 2
giving the claim.
Proof of Theorem 1.4. By applying Lemma 3.2 to µ, we get a distribution µ̃ over 1-smooth degree
q = O(1/ε) polynomials with k0 = κµ̃ (ε/2) ≥ κµ (ε) = k. By Theorem 3.1, we get a (q, 2, Ω(ε))-
0
average-case smooth code C0 : {−1, 1}k → {−1, 1}2n . Finally we use Lemma 1.11 to convert C0 to a
(q, Ω(ε), Ω(ε))-LDC C : {−1, 1}` → {−1, 1}2n where ` = Ω(ε 2 k0 / log(1/ε)). For the last part of the
theorem we can apply Theorem 3.1 and Lemma 1.11 directly.
4 From average-case smooth codes to LDCs
In this section, we prove Lemma 1.11. For this, we need the notion of the Vapnik–Chervonenkis dimension
(VC-dimension).
Definition 4.1 (VC-dimension [31]). Let T ⊂ [−1, 1]k and w > 0. Then, vc(T, w) is defined as the size
of the largest subset σ ⊂ [k] such that for some shift s ∈ [−1, 1]k , it holds that for every x ∈ {−1, 1}σ ,
there exists t ∈ T such that for every i ∈ σ , (ti − si )xi ≥ w/2.
Observe that if T is convex, then vc(T, w) is the maximum dimension of a shifted hypercube with
edge lengths at least w contained in T . Note that usually VC-dimension for a subset T ⊂ {0, 1}n is
defined as the size of the largest subset σ ⊂ [n] which is fully shattered by T (i.e., T |σ = {0, 1}σ ). This
coincides with Definition 4.1 for any w ∈ (0, 1] (by the taking the shift s = (1/2, 1/2, . . . , 1/2)). Thus
Definition 4.1 can be seen as a generalization of the usual definition to more general sets.
Definition 4.2 (Gaussian width). Let g be a k-dimensional standard Gaussian vector, with independent
standard normal distributed entries. The Gaussian width of a set T ⊆ Rk is defined as
E(T ) = Eg [suphg,ti].
t∈T
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 11
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
It can be shown that large VC-dimension implies large Gaussian width. The following theorem shows
the converse: containing a hypercube-like structure is the only way to have large Gaussian width.
Theorem 4.3 ([31]). Let T ⊂ [−1, 1]k . Then, the Gaussian width of T is bounded as
√ Z1 p
E(T ) . k vc(T, w) log(1/w)dw
αE(T )/k
for some absolute constant α > 0.
Finally, we use that fact that, as for LDCs, we can assume that on input y ∈ {0, 1}n , the decoder Ai of
a smooth code first samples a set S ⊆ [n] of at most q coordinates according to a probability distribution
that depends on i only and then returns a random sign depending only on i, S and the values of y at S.
Proof of Lemma 1.11. For the proof we show that the average-case smoothness property implies that
the image of the (average) decoding functions has large Gaussian width. Then, Theorem 4.3 gives a
hypercube like structure inside the image, which we use to construct a smooth code. Finally we use
Theorem 1.9 to convert the smooth code to an LDC.
Recall the switch of the message and codeword alphabets to {−1, 1}. For each i ∈ [k], let fi :
{−1, 1}n → [−1, 1] be the expected decoding function fi (z) = E[Ai (z)]. Let g be a standard k-dimensional
Gaussian vector and T = {( f1 (z), . . . , fk (z)) : z ∈ {−1, 1}n }. By the definition of average-case smooth
code we have
" #
k
2ηk ≤ Ex∈{−1,1}k ∑ xi fi (C(x)) ≤ Ex∈{−1,1}k suphx,ti . Eg suphg,ti .
i=1 t∈T t∈T
(See for instance [34, Lemma 3.2.10] for the last inequality.) By Theorem 4.3, for some constant α > 0,
we have
√ Z1 p √ p
ηk . k vc(T, w) log(1/w)dt ≤ k · vc(T, αη) log(1/αη)
αη
where we used the fact that vc(T, w) is decreasing in w. So for τ = αη, we have vc(T, τ) & η 2 k/ log(1/η).
By the definition of VC-dimension, there exists a subset σ ⊂ [k] of size |σ | ≥ vc(T, τ) and a shift
s ∈ [−1, 1]k such that for every x ∈ {−1, 1}σ there exists t ∈ T such that (ti − si )xi ≥ τ/2 for every i ∈ σ .
Now we will define the code C0 : {−1, 1}σ → {−1, 1}n . Given x ∈ {−1, 1}σ , there exists t(x) ∈ T
such that (t(x)i − si )xi ≥ τ/2 for every i ∈ σ . Define C0 (x) ∈ {−1, 1}n to be one of the preimages of t(x)
under f , that is,
f1 (C0 (x)), . . . , fk (C0 (x)) = t(x).
Let Wp denote a {−1, 1}-valued random variable with mean p. The decoding algorithms A0i (y) run Ai (y)
internally and give their output as follows:
(
Output W(1−si )/2 if Ai (y) returns 1,
A0i (y) =
Output −W(1+si )/2 if Ai (y) returns − 1.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 12
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
Therefore, for every x ∈ {−1, 1}σ and for every i ∈ σ ,
(1 + Ai (C0 (x))) (1 − Ai (C0 (x)))
xi E[A0i (C0 (x))] = xi E W(1−si )/2 − W(1+si )/2
2 2
xi
= E Ai (C0 (x)) − si
2
xi
= ( fi (C0 (x)) − si )
2
xi
= (t(x)i − si )
2
τ
≥ & η.
4
Since the probability that A0i (C0 (x)) queries any particular location of C0 (x) is still at most c/n, it follows
that C0 is a (q, c, Ω(η))-smooth code. By Theorem 1.9, C0 is also a (q, Ω(η/c), Ω(η))-LDC.
5 From LDCs to outlaws
In this section we prove Theorem 1.5, the converse of our main result.
Proof of Theorem 1.5. By Theorem 1.9, the map C : {−1, 1}k → {−1, 1}n is also a (q, q/δ , η)-smooth
code. For each i ∈ [k], let Bi be its decoder for the i-th index. Let νi : 2[n] → [0, 1] be the probability
distribution used by Bi to sample a set S ⊆ [n] of at most q coordinates and let fi,S : {−1, 1}n → [−1, 1] be
function whose value at y ∈ {−1, 1}n is the expectation of the random sign returned by Bi (y) conditioned
on the event that it samples S. Since this value depends only on the coordinates in S, the function fi,S is a
q-junta.
Fix an i ∈ [k] and let fi : {−1, 1}n → [−1, 1] be the function given by fi = ES∼νi [ fi,S ]. Then, since a
q-junta has degree at most q, so does fi . We claim that fi is (q2q/2 )/δ -smooth. Since the functions fi,S :
{−1, 1}n → {−1, 1} are q-juntas, it follows from Parseval’s identity that they have spectral norm at most
2q/2 . Moreover, for each j ∈ [n], we have PrS∼νi [ j ∈ S] ≤ q/(δ n). Hence, since fi,S depends only on the
coordinates in S, we have
q2q/2
D j fi sp ≤ ∑ νi (S) k fi,S ksp ≤ ,
S3 j δn
which gives the claim. By (1.3), it holds for every x ∈ {−1, 1}k and every i ∈ [k] that
xi fi C0 (x) ≥ 2η.
(5.1)
Define the distribution µ to correspond to the process of sampling i ∈ [k] uniformly at random
and returning fi . Let ḡ = ( f1 + · · · + fk )/k be the mean of µ. We show that κµ (η) ≥ ηk. To this
end, let l = ηk, let σ : [l] → [k] be an arbitrary map and define the functions g1 , . . . , gl by gi = fσ (i) .
Let x ∈ {−1, 1}k be such that for each i ∈ [l], we have xσ (i) = 1 and x j = −1 elsewhere. It follows
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 13
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
from (5.1) that fσ (i) C(x) ∈ [2η, 1] for every i ∈ [l] and that fi C(x) ≤ 0 for every other i ∈ [k]. Hence,
1 l 1 l
∑ (gi − ḡ) ≥ ∑ (g i − ḡ) C(x)
l i=1 L∞ l i=1
1 l 1 k
= ∑ fσ (i) C(x) − ∑ fi C(x)
l i=1 k i=1
l
≥ 2η − = η.
k
If σ maps each element in [l] to a uniformly random element in [k], then g1 , . . . , gl are independent,
µ-distributed and satisfy
" #
1 l
E ∑ (gi − ḡ) L∞ ≥ η,
l i=1
which shows that κµ (η) ≥ l. Finally we can scale all the functions in µ to make them 1-smooth, and get
a distribution µ̃ over 1-smooth functions with κµ̃ (ηδ /(q2q/2 )) ≥ ηk.
6 Candidate outlaws
In this section we elaborate on the candidate outlaws mentioned in the introduction.
6.1 Incidence geometry
We begin by describing a variant of Corollary 1.6 based on a slightly different assumption and show
conditions under which this assumption holds. Let p be an odd prime, let F p be a finite field with p
elements and let n be a positive integer. For x, y ∈ Fnp and y 6= 0, the line with origin x in direction y,
denoted `x,y , is the sequence (x + λ y)λ ∈F p .
Corollary 6.1. For every odd prime p and ε ∈ (0, 1], there exist a positive integer n1 (p, ε) and a
c = c(p, ε) ∈ (0, 1/2] such that the following holds. Let n ≥ n1 (p, ε) and k be positive integers. Assume
that for independent uniformly distributed elements z1 , . . . , zk ∈ Fnp , with probability at least 1/2, there
exists a set B ⊆ Fnp of size ε pn such that every line passing through some point of the set {z1 , . . . , zk }
n
contains at most p − 2 points of B. Then, there exists a (p − 1, c, c)-LDC sending {0, 1}l to {0, 1}2p ,
where l = Ω(c2 k/ log(1/c)).
The proof uses the following version of Szemerédi’s Theorem, which follows easily from the density
Hales–Jewett theorem [19] (see also [35, Theorem 1.5.4]), and its standard “Varnavides-type” corollary
(see for example [37, Exercise 10.1.9]).
Theorem 6.2 (Szemerédi’s theorem for finite vector spaces). For every odd prime p and any ε ∈ (0, 1],
there exists a positive integer n0 (p, ε) such that the following holds. Let n ≥ n0 (p, ε) and let S ⊆ Fnp be a
set of size |S| ≥ ε pn . Then, S contains a line.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 14
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
Corollary 6.3. For every odd prime p and any ε ∈ (0, 1], there exists a positive integer n1 (p, ε) and a
c(p, ε) ∈ (0, 1] such that the following holds. Let n ≥ n1 (p, ε) and let S ⊆ Fnp be a set of size |S| ≥ ε pn .
Then, S contains at least c(p, ε)p2n lines, that is,
h i
Prx∈Fnp ,y∈Fnp r{0} {(x + λ y)λp−1
=0 } ⊂ S ≥ c(p, ε).
Proof of Corollary 6.1. Abusing notation, we identify functions f : Fnp → {−1, 1} with vectors in
n
{−1, 1}F p . Let φ : {−1, 1} → {0, 1} be the map φ (α) = (α + 1)/2. For a function f : Fnp → {−1, 1}, let
φ ( f ) : Fnp → {0, 1} be the function φ ( f )(x) = φ ( f (x)) and for f : Fnp → {0, 1}, define φ −1 ( f ) : Fnp →
{−1, 1} analogously.
n
For every x ∈ Fnp , let Fx : {−1, 1}F p → R be the degree-(p − 1) polynomial
" #
Fx ( f ) = Ey∈Fnp r{0} ∏ φ ( f )(x + λ y) . (6.1)
λ ∈F∗p
Then, for a set B ⊆ Fnp , the value Fx (φ −1 (1B )) equals the fraction of all lines `x,y through x of which B
contains the p − 1 points {x + λ y : λ ∈ F∗p }. If B has size at least ε pn , it follows from Corollary 6.3
that Ex∈Fnp [Fx (φ −1 (1B ))] ≥ c(p, ε). Moreover, since the monomials in the expectation of (6.1) can be
expanded as
1
∏∗ φ ( f )(x + λ y) = 2 p−1 ∑∗ ∏ f (x + λ y),
λ ∈F
p S⊆F λ ∈S p
p−1
it follows that each Fx is 2(1−p −n ) -smooth.
Let µ be the uniform distribution over Fx . We claim that κµ (c(p, ε)) ≥ k, which implies the result
by Theorem 1.4 since µ is supported on degree (p − 1)-polynomials. For every set A ⊆ Fnp , let BA ⊆ Fnp
be a set of maximum size such that every line through A contains at most p − 2 points of BA , and
let fA = φ −1 (1BA ). Let z be a uniformly distributed random variable over Fnp , let z1 , . . . , zk be independent
copies of z and let A = {z1 , . . . , zk }. Then, Fz1 , . . . , Fzk are independent µ-distributed random functions.
Moreover, in the event that |BA | ≥ ε pn , we have
(Ez [Fz ] − Fzi )( fA ) = Ez Fz (φ −1 (1BA )) − Fzi (φ −1 (1BA )) = Ez Fz (φ −1 (1BA )) ≥ c(p, ε)
for every i ∈ [k]. Since this event happens with probability at least 1/2, we have
h 1 k i h 1 k i c(p, ε)
E ∑ Fzi − E[Fz ] ≥E ∑ Fzi − E[Fz ] ( fA ) ≥ ,
k i=1 L∞ k i=1 2
which gives the claim.
The proof of the formal version of Corollary 1.6 (given below) is similar to that of Corollary 6.1,
so we omit it. In the following, PFn−1
p is the projective space of dimension n − 1, which is the space of
directions in Fnp . The formal version of Corollary 1.6 is then as follows.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 15
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
Corollary 6.4. For every odd prime p and ε ∈ (0, 1], there exist a positive integer n1 (p, ε) and a
c = c(p, ε) ∈ (0, 1/2] such that the following holds. Let n ≥ n1 (p, ε) and k be positive integers. Suppose
that for independent uniformly distributed elements z1 , . . . , zk ∈ PFn−1
p , with probability at least 1/2, there
n n
exists a set B ⊂ F p of size |B| ≥ ε p which does not contain any lines with direction in {z1 , . . . , zk }. Then,
n
there exists a (p, c, c)-LDC sending {0, 1}l to {0, 1}2p , where l = Ω(c2 k/ log(1/c)).
Feasible parameters for Corollary 6.1. Proving lower bounds on k for which the assumption of
Corollary 6.1 holds true thus allows one to infer the existence of (p − 1)-query LDCs with rate Ω(k/N)
for N = pn , provided p and ε are constants independent of n. We establish the following bounds, which
imply the (well-known) existence of (p − 1)-query LDCs with message length k = Ω((log N) p−2 ).
Theorem 6.5. For every odd prime p there exists an ε(p) ∈ (0, 1] such that the following holds. For
every set A ⊆ Fnp of size |A| ≤ n+p−3 n n
p−2 − 1, there exists a set B ⊆ F p of size ε(p)p such that every line
through A contains at most p − 2 points of B.
The proof uses some basic properties of polynomials over finite fields. For an n-variate polynomial
f ∈ F p [x1 , . . . , xn ] denote Z( f ) = {x ∈ Fnp : f (x) = 0}. The starting point of the proof is the following
standard result (see for example [36]), showing that small sets can be “captured” by zero-sets of nonzero,
homogeneous polynomials of low degree.
Lemma 6.6 (Homogeneous Interpolation). For every A ⊆ Fnp of size |A| ≤ n+d−1
d − 1, there exists a
nonzero homogeneous polynomial f ∈ F p [x1 , . . . , xn ] of degree d such that A ⊆ Z( f ).
The next two lemmas show that if f is nonzero, homogeneous and degree d, and if a ∈ F∗p is such
that f −1 (a) is nonempty, then lines through Z( f ) meet f −1 (a) in at most d points.
Lemma 6.7. Let f ∈ F p [x1 , . . . , xn ] be a nonzero homogeneous polynomial of degree d. Let a ∈ F∗p be
such that the set f −1 (a) is nonempty. Then, every line that meets f −1 (a) in d + 1 points must have
direction in Z( f ).
Proof. The univariate polynomial g(λ ) = f (x + λ y) formed by the restriction of f to a line `x,y has
degree at most d. By the Factor Theorem, such a polynomial must be the constant polynomial g(λ ) = a
to assume the value a for d + 1 values of λ . Since f is homogeneous, the coefficient of λ d , which must
be zero, equals f (y), giving the result.
The following lemma, which is inspired by the solution of the finite-field Kakeya problem in [14], is
essentially contained in [10].
Lemma 6.8 (Briët–Rao). Let f ∈ F p [x1 , . . . , xn ] be a nonzero homogeneous polynomial of degree d. Let
a ∈ F∗p be such that f −1 (a) is nonempty. Then, there exists no line that intersects Z( f ), meets f −1 (a) in
at least d points and has direction in Z( f ).
Proof. For a contradiction, suppose there exists a line `x,y through Z( f ) that meets f −1 (a) in d points
and has direction y ∈ Z( f ). Observe that for every λ ∈ F p , the shifted line `x+λ y,y also meets f −1 (a) in d
points. Hence, without loss of generality we may assume that the line starts in Z( f ), that is x ∈ Z( f ).
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 16
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
Let g(λ ) = a0 + a1 λ + · · · + ad λ d = f (x + λ y) ∈ F p [λ ] be the restriction of f to `x,y . It follows that
a0 = g(0) = f (x) = 0 and, since f is homogeneous, that ad = f (y) = 0. Moreover, there exist distinct
elements λ1 , . . . , λd ∈ F∗p such that g(λi ) = f (x + λi y) = a for every i ∈ [d]. Then g(λ ) − a is a degree
d − 1 polynomial with d distinct roots. But it cannot be the zero polynomial since it takes value −a when
λ = 0.
The final ingredient for the proof of Theorem 6.5 is a variant of the DeMillo–Lipton–Schwartz–Zippel
Lemma; see for instance [12, Appendix C] for a proof.
Lemma 6.9. Let f ∈ F p [x1 , . . . , xn ] be a nonzero polynomial of degree d. Then,
1
|Z( f )| ≤ 1 − pn .
pd/(p−1)
Proof of Theorem 6.5. Let A ⊆ Fnp be a set of size |A| ≤ n+p−3
p−2 − 1. Let f ∈ F p [x1 , . . . , xn ] be a nonzero
degree-(p − 2) homogeneous polynomial such that A ⊆ Z( f ), as promised to exist by Lemma 6.6. By
Lemma 6.9, there exists an a ∈ F∗p such that the set B = f −1 (a) has size at least |B| ≥ pn /p(2p−3)/(p−1) .
By Lemma 6.7, every line that meets B in p − 1 points must have direction in Z( f ), but by Lemma 6.8 no
such line can pass through Z( f ). Hence, every line through A meets B in at most p − 2 points.
6.2 Hypergraph pseudorandomness
A second candidate for constructing outlaws comes from special types of hypergraphs. A hypergraph
H = (V, E) is a pair consisting of a finite vertex set V and an edge set E of subsets of V that allows for
parallel (repeated) edges. A hypergraph is t-uniform if all its edges have size t. For subsets W1 , . . . ,Wt ⊆ V ,
define the induced edge count by
eH (W1 , . . . ,Wt ) = ∑ · · · ∑ 1E ({v1 , . . . , vt }).
v1 ∈W1 vt ∈Wt
A perfect matching in a t-uniform hypergraph is a family of vertex-disjoint edges that intersects every
vertex. We shall use the following notion of pseudorandomness.
Definition 6.10 (Relative pseudorandomness). Let H = (V, E), J = (V, E 0 ) be t-uniform hypergraphs
with identical vertex sets. Then J is ε-pseudorandom relative to H if for all W1 , . . . ,Wt ⊆ V , we have
eJ (W1 , . . . ,Wt ) eH (W1 , . . . ,Wt )
− < ε. (6.2)
|E 0 | |E|
The left-hand side of (6.2) compares the fraction of edges that the sets W1 , . . . ,Wt induce in J with the
fraction of edges they induce in H. Standard concentration arguments show that if |E| ≥ |V |, then a random
hypergraph J whose edge set E 0 is formed by independently putting each edge of E in E 0 with probability
p = p(ε,t), is ε-pseudorandom relative to H with high probability. A deterministic hypergraph J is thus
pseudorandom relative to H if it mimics this property of truly random sub-hypergraphs. For graphs,
relative ε-pseudorandomness turns into a common notion sometimes referred to as ε-uniformity when H
is the complete graph with all loops, in which case (6.2) says that the number of edges induced by a pair of
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 17
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
vertex-subsets W1 ,W2 is roughly equal to the product of their densities (|W1 |/|V |)(|W2 |/|V |). Uniformity
in graphs is closely connected to the perhaps better-known notion of spectral expansion [24]. These
two notions were recently shown to be equivalent (up-to universal constants) for all vertex-transitive
graphs [13].
We shall be interested in hypergraphs whose edge set can be partitioned into a family of “blocks,” such
that randomly removing relatively few of the blocks likely leaves a hypergraph that is not pseudorandom
relative to the original. (Think of a Jenga tower10 that’s already in a delicate balance, so that there are only
few ways, or perhaps even no way, to remove many blocks without having it collapse.) Our blocks will
be formed by perfect matchings. For technical reasons, the formal definition takes the view of building a
new hypergraph out of randomly selected matchings, as opposed to obtaining one by randomly removing
matchings.
Definition 6.11 (Jenga hypergraph). A t-uniform hypergraph H is (k, ε)-jenga if its edge set can be
partitioned into a family M of perfect matchings such that, with probability at least 1/2, the disjoint
union of k independent uniformly distributed matchings from M forms a hypergraph which is not
ε-pseudorandom relative to H.
We have the following simple corollary to Theorem 1.4.
Corollary 6.12. Let n, k,t be positive integers and ε ∈ (0, 1]. Assume that there exists a t-uniform
n-vertex hypergraph that is (k, ε)-jenga. Then, there exists a (t, 1, Ω(ε/t 2 ))-LDC sending {0, 1}l to
{0, 1}2tn , where l = Ω(ε 2 k/t 4 log(t 2 /ε)).
Proof. Let H = (V, E) be a hypergraph as assumed in the corollary. Let M be a partition of E into
perfect matchings such that if M1 , . . . , Mk are independent and uniformly distributed over M, then with
probability at least 1/2, the hypergraph J = (V, M1 ] · · · ] Mk ) is not ε-pseudorandom relative to H.11
Let V1 , . . . ,Vt be copies of V . For each M ∈ M, define fM : RV1 ∪···∪Vt → R by
1
fM (x[1], . . . , x[t]) = · · · ∑ 1M ({v1 , . . . , vt }) x[1]v1 · · · x[t]vt , x[i] ∈ RVi .
|M| v1∑
∈V1 vt ∈Vt
Denote by fM± the restriction of fM to the Boolean hypercube {−1, 1}tn , which is a degree-t polynomial
in tn variables. Then, for each variable x[i]vi for vi ∈ Vi , the spectral norm Dx[i]vi fM± equals |M|−1 times
sp
the number of monomials containing x[i]vi . Since every one of the tn variables appears in exactly one
monomial and |M| = n/t, it follows that fM± is σ -smooth for σ = tn/|M| = t 2 . Moreover, for J = (V, M)
and W1 , . . . ,Wt ⊆ V , we have
eJ (W1 , . . . ,Wt )
fM (1W1 , . . . , 1Wt ) = .
|M|
Let M1 , . . . , Mk be independent uniformly distributed matchings from M and consider the random
hypergraph J = (V, M1 ] · · · ] Mk ). Let f¯ = E[ fM1 ] be the expectation of the random function fM1 and note
10 Jenga R is a game of dexterity in which players begin with a tower of wooden blocks and take turns trying to remove a
block without making the tower collapse.
11 M ] · · · ] M is the disjoint union of the matchings (i.e., we repeat an edge r times if it occurs in r matchings).
1 k
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 18
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
that E[ fMi ] = f¯ for each i ∈ [k]. Let f¯± denote the restriction of f¯ to {−1, 1}tn and note that f¯± = E[ fM±i ].
Then, since the functions fMi − f¯ are multilinear,
h 1 k i h 1 k i
± ¯ ± ¯
E (
∑ Mi f − f ) = E max ∑ Mi ( f − f )(x[1], . . . , x[t])
k i=1 L∞ x[1],...,x[t]∈{−1,1}n k i=1
h 1 k ¯
i
≥E max ∑ i( f M − f )(1W1 , . . . , 1Wt )
W1 ,...,Wt ⊆V k
i=1
h eJ (W1 , . . . ,Wt ) eH (W1 , . . . ,Wt ) i
=E max −
W1 ,...,Wt ⊆V k|M| |E|
ε
≥ .
2
The result now follows from Theorem 1.4.
In the context of outlaws and LDCs, the relevant question concerning Jenga hypergraphs is the
following. Let κ J (n,t, ε) denote the maximum integer k such that there exists an n-vertex t-uniform
hypergraph that is (k, ε)-jenga.
Question 6.13. For integer t ≥ 2 and parameter ε ∈ (0, 1], what is the growth rate of κ J (n,t, ε) as a
function of n ∈ N?
For t = 2 (graphs), the answer to Question 6.13 follows from a famous result of Alon and Roichman [1]
on expansion of random Cayley graphs. In particular, the proof of this result, due to Landau and
Russell [30], based on the matrix Chernoff bound of Ahlswede and Winter, implies that for constant
ε ∈ (0, 1] we have κ(n, 2, ε) = Θ(log n). Indeed, the matrix Chernoff bound shows that any partitioning
of the complete graph on n vertices into perfect matchings is (O(log n), O(1))-Jenga. The lower bound
follows for instance by partitioning the edge
set of the complete graph with vertex set V = Fm2 into the
m m
collection of matchings of the form My = {x, x + y} : x ∈ F2 for each y ∈ F2 r {0}. Any m − 1 of such
matchings give a graph with two disconnected components of equal size, making it (m − 1, 1/4)-jenga.
Via Corollary 6.12, this arguably gives the most round-about way to prove the existence of 2-query LDCs
matching the parameters of the Hadamard code! Generalizing the above example, [10] considered the
p-uniform hypergraph on Fmp whose edges are the (unordered) lines. It was shown that this hypergraph is
(m p−1 , ε)-jenga for some ε = ε(p) depending on p only, by partitioning the edge set according to the
directions of the lines, that is, partitioning it with the matchings My = {x + λ y : λ ∈ F p } : x ∈ Fmp ,
y ∈ Fmp r {0}. To the best of our knowledge, the best upper bounds on κ J (n,t, ε) for constant t ≥ 3 and
ε ∈ (0, 1] follow from upper bounds on LDCs, via Corollary 6.12.
We end with the following natural question concerning Jenga hypergraphs.
Question 6.14. Is κ J (n,t, ε) largest for the complete hypergraph?
Acknowledgements. J. B. and S. G. thank the Simons Institute for hosting them during the 2017
Pseudorandomness program, where part of this work was done. We thank Jacob Fox for pointing out
to us that randomness is essential in Corollary 1.6, Quentin Guilmant for pointing out an error in an
earlier version of the proof of Theorem 3.1 and the anonymous referees for helpful remarks that greatly
improved the exposition of this paper.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 19
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
References
[1] N OGA A LON AND Y UVAL ROICHMAN: Random Cayley graphs and expanders. Random Struct.
Algorithms, 5(2):271–284, 1994. [doi:10.1002/rsa.3240050203] 19
[2] 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 version in FOCS’92. [doi:10.1145/278298.278306] 2
[3] 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
[4] L ÁSZLÓ BABAI , L ANCE F ORTNOW, L EONID A. L EVIN , AND M ARIO S ZEGEDY: Checking
computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–31. ACM Press, 1991.
[doi:10.1145/103418.103428] 2
[5] 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
[6] J OP B RIËT: On embeddings of `k1 from locally decodable codes, 2016. [arXiv:1611.06385] 4
[7] J OP B RIËT, Z EEV DVIR , AND S IVAKANTH G OPI: Outlaw distributions and locally decodable codes.
In Proc. 8th Symp. Innovations in Theoret. Comp. Sci. (ITCS’17), pp. 20:1–20:19. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.20, arXiv:1609.06355]
1
[8] J OP B RIËT AND S IVAKANTH G OPI: Gaussian width bounds with applications to arithmetic
progressions in random settings. Internat. Math. Res. Notices, 2018. [doi:10.1093/imrn/rny238,
arXiv:1711.05624] 5
[9] J OP B RIËT, A SSAF NAOR , AND O DED R EGEV: Locally decodable codes and the failure of
cotype for projective tensor products. Electron. Res. Announc. Math. Sci., 19:120–130, 2012.
[doi:10.3934/era.2012.19.120, arXiv:1208.0539] 2
[10] J OP B RIËT AND S HRAVAS R AO: Arithmetic expanders and deviation bounds for random tensors,
2016. [arXiv:1610.03428] 16, 19
[11] B ENNY C HOR , O DED G OLDREICH , E YAL K USHILEVITZ , AND M ADHU S UDAN: Private
information retrieval. J. ACM, 45(6):965–982, 1998. Preliminary version in FOCS’95.
[doi:10.1145/293347.293350] 2, 3
[12] G IL C OHEN AND AVISHAY TAL: Two structural results for low degree polynomials and appli-
cations. In Proc. Internat. Workshop on Approximation, Randomization, and Combinat. Op-
tim. (RANDOM’15), pp. 680–709. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
[doi:10.4230/LIPIcs.APPROX-RANDOM.2015.680, arXiv:1404.0654] 17
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 20
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
[13] DAVID C ONLON AND Y UFEI Z HAO: Quasirandom Cayley graphs. Discrete Analysis, pp. 6:1–6:14,
2017. [doi:10.19086/da.1294, arXiv:1603.03025] 18
[14] Z EEV DVIR: On the size of Kakeya sets in finite fields. J. Amer. Math. Soc., 22(4):1093–1097,
2009. [doi:10.1090/S0894-0347-08-00607-3, arXiv:0803.2336] 16
[15] Z EEV DVIR AND S IVAKANTH G OPI: 2-Server PIR with subpolynomial communication. J. ACM,
63(4):39:1–39:15, 2016. Preliminary version in STOC’15. [doi:10.1145/2968443, arXiv:1407.6692]
3
[16] 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] 3
[17] N IKOS F RANTZIKINAKIS , E MMANUEL L ESIGNE , AND M ÁTÉ W IERDL: Random sequences and
pointwise convergence of multiple ergodic averages. Indiana Univ. Math. J., 61(2):585–617, 2012.
[doi:10.1512/iumj.2012.61.4571] 5
[18] N IKOS F RANTZIKINAKIS , E MMANUEL L ESIGNE , AND M ÁTÉ W IERDL: Random differences
in Szemerédi’s theorem and related results. J. d’Analyse Mathématique, 130(1):91–133, 2016.
[doi:10.1007/s11854-016-0030-z, arXiv:1307.1922] 5
[19] H ILLEL F URSTENBERG AND Y ITZHAK K ATZNELSON: A density version of the hales-jewett
theorem. J. d’Analyse Mathématique, 57(1):64–119, 1991. [doi:10.1007/BF03041066] 14
[20] O DED G OLDREICH , H OWARD 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
[21] PARIKSHIT G OPALAN , C HENG H UANG , H USEYIN S IMITCI , AND S ERGEY Y EKHANIN: On
the locality of codeword symbols. IEEE Trans. Inform. Theory, 58(11):6925–6934, 2012.
[doi:10.1109/TIT.2012.2208937, arXiv:1106.3625] 2
[22] S IVAKANTH G OPI , S WASTIK KOPPARTY, R AFAEL O LIVEIRA , N OGA RON -Z EWI , AND S HUB -
HANGI S ARAF : Locally testable and locally correctable codes approaching the Gilbert-Varshamov
bound. IEEE Trans. Inform. Theory, 64(8):5813–5831, 2018. Preliminary version in SODA’17.
[doi:10.1109/TIT.2018.2809788] 3
[23] B EN G REEN AND T OM S ANDERS: Boolean functions with small spectral norm. Geom. Funct.
Anal., 18(1):144–162, 2008. [doi:10.1007/s00039-008-0654-y, arXiv:math/0605524] 3
[24] S HLOMO H OORY, NATHAN L INIAL , AND AVI W IGDERSON: Expander graphs and their appli-
cations. Bull. Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]
18
[25] 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, 7
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 21
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
[26] TALI K AUFMAN AND M ADHU S UDAN: Sparse random linear codes are locally decod-
able and testable. In Proc. 48th FOCS, pp. 590–600. IEEE Comp. Soc. Press, 2007.
[doi:10.1109/FOCS.2007.8] 2
[27] I ORDANIS K ERENIDIS AND RONALD DE W OLF: Exponential lower bound for 2-query locally
decodable codes via a quantum argument. J. Comput. System Sci., 69(3):395–420, 2004. Preliminary
version in STOC’03. [doi:10.1016/j.jcss.2004.04.007, arXiv:quant-ph/0208062] 3, 5
[28] S WASTIK KOPPARTY, O R M EIR , N OGA RON -Z EWI , AND S HUBHANGI S ARAF: High-rate locally
correctable and locally testable codes with sub-polynomial query complexity. J. ACM, 64(2):11:1–
11:42, 2017. Preliminary version in STOC’16. [doi:10.1145/3051093, arXiv:1504.05653] 3
[29] 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] 3
[30] Z EPH L ANDAU AND A LEXANDER RUSSELL: Random Cayley graphs are expanders: A simple
proof of the Alon–Roichman theorem. Electron. J. Combin., 11(1):R62, 2004. 19
[31] S HAHAR M ENDELSON AND ROMAN V ERSHYNIN: Entropy and the combinatorial dimension.
Inventiones Math., 152(1):37–55, 2003. [doi:10.1007/s00222-002-0266-3, arXiv:math/0203275] 7,
11, 12
[32] C LAUDE E. S HANNON: A mathematical theory of communication. Bell System Tech. J., 27(3):379–
423, 623–656, 1948. [doi:10.1002/j.1538-7305.1948.tb01338.x] 2
[33] A MIR S HPILKA , AVISHAY TAL , AND B EN L EE VOLK: On the structure of Boolean functions with
small spectral norm. Comput. Complexity, 26(1):229–273, 2017. Preliminary version in ITCS’14.
[doi:10.1007/s00037-015-0110-y, arXiv:1304.0371] 3
[34] M ICHEL TALAGRAND: Upper and Lower bounds For Stochastic Processes. Springer, 2014.
[doi:10.1007/978-3-642-54075-2] 12
[35] T ERENCE TAO: Higher Order Fourier Analysis. Amer. Math. Soc., 2012. [doi:10.1090/gsm/142]
14
[36] T ERENCE TAO: Algebraic combinatorial geometry: The polynomial method in arithmetic combina-
torics, incidence combinatorics, and number theory. EMS Surveys in Math. Sciences, 1(1):1–46,
2014. [doi:10.4171/EMSS/1, arXiv:1310.6482] 16
[37] T ERENCE TAO AND VAN V U: Additive Combinatorics. Cambridge Univ. Press, 2006.
[doi:10.1017/CBO9780511755149] 14
[38] DAVID W OODRUFF: New lower bounds for general locally decodable codes. Electronic Colloq.
Comput. Complexity (ECCC’07), 14(6), 2007. 3, 5
[39] 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] 3
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 22
O UTLAW D ISTRIBUTIONS AND L OCALLY D ECODABLE C ODES
[40] S ERGEY Y EKHANIN: Locally decodable codes. Found. Trends Theor. Comput. Sci., 6(3):139–255,
2012. Preliminary version in CSR’11. [doi:10.1561/0400000030] 2
AUTHORS
Jop Briët
Senior researcher
Centrum Wiskunde & Informatica (CWI)
Amsterdam, The Netherlands
j briet cwi nl
https://homepages.cwi.nl/~jop/
Zeev Dvir
Associate professor
Department of Computer Science and Department of Mathematics
Princeton University
zdvir princeton edu
www.cs.princeton.edu/~zdvir/
Sivakanth Gopi
Postdoctoral Researcher
Microsoft Redmond
sigopi microsoft com
https://www.microsoft.com/en-us/research/people/sigopi/
ABOUT THE AUTHORS
J OP B RIËT was born in Leiden, The Netherlands. He spent a year in the United States
when he was one year old, but remembers nothing of it. He received his Ph. D. from
the University of Amsterdam in 2011 and was advised by Harry Buhrman. He met
his coauthors on this paper during a postdoc at the Courant Institute of Mathematical
Sciences in New York. He is interested in the interplay between mathematics and
theoretical computer science, especially for additive combinatorics, geometric function
analysis, coding theory and quantum information.
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.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 23
J OP B RI ËT, Z EEV DVIR , AND S IVAKANTH G OPI
S IVAKANTH G OPI (called “Gopi” by friends and colleagues) is a postdoctoral researcher
in the algorithms research group at Microsoft Research, Redmond. He received his
Ph. D. at Princeton University in 2018 under the supervision of Zeev Dvir; the title
of his dissertation was “Locality in coding theory.” His main research interests are in
coding theory, complexity theory, and additive combinatorics. He is also part of the
DNA Storage project and Project Laplace (differential privacy) at Microsoft. He enjoys
spending leisure time learning new things, staying fit, exploring nature and talking to his
family.
T HEORY OF C OMPUTING, Volume 15 (12), 2019, pp. 1–24 24