Authors Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25
www.theoryofcomputing.org
From Local to Robust Testing
via Agreement Testing
Irit Dinur* Prahladh Harsha† Tali Kaufman‡ Noga Ron-Zewi§
Received March 25, 2019; Revised January 1, 2021; Published June 6, 2022
Abstract. A local tester for an error-correcting code is a probabilistic procedure that queries
a small (sublinear) subset of coordinates, accepts codewords with probability one, and rejects
non-codewords with probability proportional to their distance from the code. The local tester
is said to be robust if for non-codewords it satisfies the stronger condition that the average
distance of local views from accepting views is proportional to the distance from the code.
Robust testing is an important component in constructions of locally testable codes and
probabilistically checkable proofs as it allows for composition of local tests.
We show that for certain codes, any (natural) local tester can be converted to a robust
tester with roughly the same number of queries. Our result holds for the class of affine-
invariant lifted codes which is a broad class of codes that includes Reed–Muller codes, as
well as recent constructions of high-rate locally testable codes (Guo, Kopparty, and Sudan,
ITCS 2013). Instantiating this with known local testing results for lifted codes gives a more
A conference version of this paper appeared in the Proceedings of the 10th Innovations in Theoretical Computer Science
Conference, 2019 [15].
* Supported by ERC-CoG grant number 772839.
† Supported by the Department of Atomic Energy, Government of India, under project no. RTI4001 and in part by the
UGC-ISF grant and the Swarnajayanti Fellowship.
‡ Supported by ERC and BSF grants.
§ Supported by ISF grant 735/20.
ACM Classification: G.3
AMS Classification: 68Q87
Key words and phrases: local testing, robust soundness, agreement testing, lifted codes, affine-invariant
codes
© 2022 Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a012
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
direct proof that improves some of the parameters of the main result of Guo, Haramaty, and
Sudan (FOCS 2015), showing robust soundness of lifted codes.
To obtain the above transformation, we relate the notions of local testing and robust
testing to the notion of agreement testing that attempts to find out whether valid partial
assignments can be stitched together to a global codeword. We first show that agreement
testing implies robust testing, and then show that local testing implies agreement testing.
Our proof is combinatorial, and is based on sampling properties of the collection of local
views of local testers. Thus, it immediately applies to local testers of lifted codes that query
random affine subspaces in Fm q , and moreover seems amenable to extension to other families
of locally testable codes with expanding families of local views.
1 Introduction
Our main result shows a transformation from local testing to robust testing for the class of affine-invariant
lifted codes. We start by describing the notions of local testing, robust testing, and lifted codes.
1.1 Local testing and robust testing
A code is a subset C ⊆ Σn . The elements of Σn are called words, the elements of C are called codewords,
Σ is the alphabet of the code, and n is the block length. The rate of the code is the ratio (log|Σ| |C|)/n.
The code is linear if Σ = Fq where Fq is the finite field of q elements, and C is an Fq -linear subspace
of Fnq . It will be convenient to think of codewords in C as functions f : U → Σ where U is a domain of
size n. For a pair of functions f , g : U → Σ, we let dist( f , g) denote their normalized Hamming distance,
i. e., the fraction of inputs x ∈ U for which f (x) 6= g(x). By the minimum distance mindist(C) of the
code we mean its minimum normalized distance, i. e., the minimum of dist( f , g) over all pairs of distinct
codewords f , g ∈ C. For a function f : U → Σ, we let dist( f ,C) denote the minimum of dist( f , g) over
all codewords g ∈ C.
Let Q ∈ Z+ and α > 0. A local tester for the code C with query complexity Q and soundness α is a
probabilistic oracle algorithm that on oracle access to a function f : U → Σ makes at most Q queries to f ,
and accepts f ∈ C with probability one (completeness), while rejecting all words f ∈ Σn with probability
at least α · dist( f ,C). In this article, we shall restrict our attention to local testers that pick a random
subset K ⊆ U of cardinality Q according to some distribution, and accept1 if and only if f |K ∈ C|K . Then
the completeness requirement is automatically satisfied ( f |K ∈ C|K with probability one whenever f ∈ C),
and we only need to consider the soundeness condition,
Pr[ f |K ∈
/ C|K ] ≥ α · dist( f ,C) (1.1)
K
for all words f .
1 Local testers may generally apply a more complex predicate on f | . However, natural local testers are typically of the
K
restricted form we consider, and moreover it can be shown that a local tester for a linear code must be of this form [8].
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 2
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
In this article we will be interested in the stronger notion of robust soundness.2 We say that a local
tester is robustly sound (or just robust) if for all words, the average distance of its local views from
accepting views is at least proportional to the distance of the given function from the code. That is, instead
of (1.1) we now require that
EK dist( f |K ,C|K ) ≥ α · dist( f ,C) (1.2)
for all words f . We refer to α as the robust soundness of the tester.
The notion of robust soundness was introduced by Ben-Sasson and Sudan [10] based on analogous
notions for probabilistically checkable proofs [7, 18]. Robust soundness is a natural property of local
testers that relates the global distance of a function from the code to its local distance from accepting
views on local views. Moreover, robust soundness is also an important ingredient in constructions of
locally testable codes and probabilistically checkable proofs as it allows for composition of local tests.
Specifically, it follows by definition that if a code C is robustly testable with query complexity Q and
soundness α, and additionally each local restriction C|K is locally testable with query complexity Q0 and
soundness α 0 , then the code C is locally testable with query complexity Q0 and soundness α · α 0 . This
property is useful when local restrictions can be tested efficiently, which can happen if the code has many
symmetries (as is the case with the class of lifted codes considered in this paper), or can be achieved, in
the case of probabilistically checkable proofs, by attaching a short proof of proximity.
One can easily observe that (1.2) implies (1.1) since f |K ∈ / C|K whenever dist( f |K ,C|K ) > 0, so robust
soundness is a stronger requirement than (standard) soundness in local testing. For the other direction,
note that a local tester with soundness α has robust soundness at least α/Q since dist( f |K ,C|K ) ≥ 1/Q
whenever f |K ∈ / C|K . A natural question is whether this loss in robust soundness is necessary, and whether
robust soundness is a strictly stronger notion than (standard) soundness for local testing.
In this paper we shall show that this loss is unnecessary for the class of lifted codes, discussed below.
1.2 Lifted codes
For sets B, Σ let {B → Σ} denote the set of all functions that map B to Σ. We can view this set as the set
of strings of length n = |B| over Σ. If Σ = Fq then this set is a vector space over Fq of dimension |B|.
Lifted codes are specified by a base code C ⊆ {F`q → Fq } and a dimension m ≥ `. We further assume
that the base code C is linear and affine invariant. That is, for any codeword f ∈ C, and for any affine
transformation A : F`q → F`q , it holds that f ◦ A ∈ C. Given these we define the lifted code C`%m to be
the code consisting of all functions f : Fm q → Fq that satisfy that f |L ∈ C for any `-dimensional affine
subspace L of the domain Fq . m
Lifted codes were first introduced by Ben-Sasson, Maatouk, Shpilka and Sudan [9], and their
local testability properties were further explored in subsequent work [24, 25, 23]. They are a natural
generalization of the well-studied family of Reed–Muller codes, and moreover they also give rise to new
families of locally testable codes that outperform Reed–Muller codes in a certain range of parameters [24].
Specifically, lifted codes lead to one of the two known constructions (the other one being tensor codes
[10, 11, 32, 29]) of high-rate locally testable codes (i. e., locally testable codes with rate approaching one
2 This strengthened notion of soundness has been referred to as robust soundness [7, 10] or just robustness [23] in earlier
work. To make precise the contrast with the standard notion of soundness (1.1), we will refer to it as “robust soundness” in this
paper.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 3
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
and locality nβ for any constant β > 0). Generally, lifted codes form a natural subclass of affine-invariant
codes having the ‘single-orbit characterization’ property that is known to imply local testability, as well
as local decodability [28].
There is a natural local test associated with lifted codes: on oracle access to a function f : Fm q → Fq ,
pick a uniform random `-dimensional affine subspace L ⊆ Fm q and accept if and only if f |L ∈ C. It follows
immediately by definition that this test accepts any valid codeword f ∈ C `%m with probability one, but
more work is required to show that this test is sound. Specifically, since the test forms a single-orbit
characterization, it follows from the work of Kaufman and Sudan [28] that it has soundness roughly q−2` .
The dependence of the soundness on the dimension ` was later eliminated by Haramaty, Ron-Zewi and
Sudan [25] who showed soundness that is only a function of q (though an extremely quickly decaying
one).
As for robust soundness, the above local testing results, together with the straightforward transfor-
mation from local testing to robust testing, immediately give robust soundness that is dependent on the
dimension `. This dependence was eliminated recently by Guo, Haramaty and Sudan [23] who showed
robust soundness of the form poly(δ ) (about δ 74 , where δ is the minimum distance of the code) for the
local test that queries subspaces of slightly larger dimension of 2`. Interestingly, Guo, Haramaty and
Sudan [23] did not rely on the aforementioned local testing results, but rather relied on viewing lifted
codes as the intersection of ‘modified tensor codes.’ They then proceeded by showing that these modified
tensor codes are robustly testable (using Viderman’s method [32] showing robust soundness of tensor
codes), and that this implies local testability of the lifted code. (See Section 2.4 for more details about the
method of Guo, Haramaty and Sudan [23].)
1.3 Our results
Our main result gives a transformation from local testing to robust testing, that does not suffer the factor
of Q (the query complexity) loss in robust soundness, for the class of lifted codes. The transformation
uses local testability in a ‘black-box’ manner, and shows that if a code in this family is locally testable
(using the natural subspace tester) then it is also robustly testable with roughly the same number of queries
and robust soundness.
For k ≥ `, let the k-dimensional test denote the local tester that on oracle access to a function
f : Fm m
q → Fq queries a uniform random k-dimensional affine subspace K ⊆ Fq and accepts if and only if
f |K ∈ C`%k .
Main Theorem 1.1. Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and m ≥ k ≥ `. Suppose
that C`%m is locally testable using the k-dimensional test with query complexity qk and soundness α,
and let δ := mink≤r≤m mindist(C`%r ). Then C`%m is robustly testable using the (2k + 2 + logq (4/δ ))-
dimensional test with query complexity O(q2k+2 /δ ) and robust soundness Ω(α · δ 3 ).
Note that if the minimum distance δ is constant, we only incur a constant multiplicative loss in robust
soundness and testing dimension.3 We conjecture that the testing dimension for proving robust soundness
may be as small as k + 1, and leave it as an interesting question for future research.
3 One natural example for codes with constant δ are the lifted Reed-Solomon codes of Guo, Kopparty and Sudan [24].
Furthermore, it was shown by them [24] that for any m ≥ `, mindist(C`%m ) ≥ mindist(C) − q−` (see Proposition 3.2 below).
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 4
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
To apply the above theorem one can instantiate it with the local testing result of Kaufman and Sudan
[28] that says that lifted codes are locally testable using the `-dimensional test with soundness ≈ q−2`
(see Theorem 3.4 below). However, to obtain constant robust soundness we need that the soundness of
the initial local tester be constant (independent of q and `), and for this we observe (in Proposition 6.1)
that the soundness of Kaufman and Sudan [28] can be easily amplified to Ω(1) at the cost of increasing
the testing dimension4 to ≈ 3`. Using this observation we obtain the following.
Main Corollary 1.2. There exists an absolute constant c > 1 so that the following holds. Let C ⊆ {F`q →
Fq } be an affine-invariant linear code of minimum distance δ , and m ≥ `. Then C`%m is robustly testable
using the (6` + 4 + logq (c/δ ))-dimensional test with robust soundness Ω(δ 3 ).
Compared to the above corollary, the Guo, Haramaty and Sudan [23] use a lower dimension of 2`,
but also obtain a lower robust soundness of Ω(δ 74 ).
As described next, our proof is combinatorial, relying mainly on sampling properties of the collection
of local views. In particular, it uses very little about the algebraic structure of lifted codes or the base
code. We thus hope that such techniques may prove useful in the future for showing robust soundness for
other families of locally testable codes with similar sampling properties.
2 Overview of the proof
Our proof is based on a new connection between the notions of local testing, robust testing, and agreement
testing. Specifically, we show that for the class of lifted codes, agreement testing implies robust testing,
and local testing implies agreement testing. The combination of these two implications gives our Main
Theorem 1.1. Next we elaborate on the notion of agreement testing, followed by an overview of each of
the implications.
2.1 Agreement testing
An agreement test attempts to find out whether assignments to local views can be stitched together to
a single global codeword. Let C ⊆ {U → Σ} be a code, and let S be a collection of subsets of U. An
agreement tester for (C, S) is a probabilistic oracle algorithm that receives oracle access to a collection
of partial assignments { fS : S → Σ | S ∈ S}, where fS ∈ C|S for any S ∈ S. The tester queries a few of
the fS and is required to accept with probability one any collection ( fS )S that is consistent with some
global codeword g ∈ C (that is, g|S = fS for any S ∈ S), while rejecting any inconsistent collection ( fS )S
with probability at least proportional to the minimal fraction of the fS that must be changed in order to
be consistent with some global codeword. In this paper, we focus on an agreement tester that picks a
pair of sets S, S0 ∈ S according to some distribution and accepts if and only if fS and fS0 agree on their
intersection S ∩ S0 .
Agreement testing has first appeared in PCP constructions [6, 5, 20, 3, 2] as so-called “low-degree
tests,” and is a key component in the proof of almost all PCP theorems. A prime example is the line
4 Such an amplification with a similar blow-up in query complexity can be easily obtained by repeating the test and accepting
if and only if all invocations accept; we, however, need that the tester be a subspace tester which can be obtained using sampling
properties of affine subspaces.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 5
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
vs. line low-degree test [21, 31] in the proof of the PCP theorem. In the PCP construction, a function
on a large vector space is replaced by an ensemble of (supposed) restrictions to all possible affine lines.
These restrictions are supplied by a prover and are not a priori guaranteed to agree with any single global
function. The “low-degree test” is run by the verifier to check that restrictions on intersecting lines agree
with each other, i. e., they give the same value to the point of intersection. The main point of the argument
is to show that the passing of the test implies agreement with a single global function. In these early
low-degree tests (including the linearity tester of Blum, Luby and Rubinfeld [12]) an agreement test
component can be discerned but quite implicitly. Indeed, it was only separated in the work of Raz, Safra,
Arora, and Sudan [30, 4] that looked at the so-called list-decoding regime,5 with the goal of proving a
large gap for the PCP.
Goldreich and Safra [22] tried to separate the algebraic aspect of the low-degree test from the
combinatorial, and formulated a more general “consistency test” which is also referred to as an agreement
test. They also proved a certain local to global result which was too weak to be useful for PCPs. In
hindsight it is clear that since their family of subsets consisted of axis-parallel lines, the expansion was
not strong enough for a good agreement test. Only recently [16, 13] has the role of expansion underlying
the family of subsets begun to be uncovered.
Work on agreement testing then continued the combinatorial direction of Goldreich and Safra [22]
mainly in the list-decoding regime for direct product testing [18, 14, 27, 19, 17]. The techniques developed
in this line of work turn out to be useful also for agreement testing in the unique-decoding regime (which
is the more standard testing regime), and in particular for our work here.
Our proof of agreement testing based on local testing (see Section 5) is significantly simpler than
general agreement testing theorems. The reason is that we avoid a major technical difficulty that stems
from the varying size of disagreement between pairs of local views. In the general setting this can
be anywhere from disagreement on only one point in the intersection to disagreement on the entire
intersection, leading to a very subtle argument. In contrast, in our setting the local view restricted to the
intersection is itself an error correcting code, so whenever local views disagree, they must disagree on a
constant fraction of the intersection. This makes the proof of the agreement theorem quite direct, and
much easier than the proofs in the aforementioned papers.
An agreement testing theorem that holds in quite broad generality was proven by Dikstein and Dinur
[13] (published after the conference version of the present paper [15]). This result (see Theorems 6.2 and
6.3 in [13]) is similar to what we prove here but the parameters of Dikstein and Dinur are slightly weaker.
2.2 Agreement testing implies robust testing
We begin with an overview of the simpler implication from agreement testing to robust testing. In what
follows, we say that a collection S of subsets of the ground set U samples well inside U, if, informally,
for all 0 ≤ γ ≤ 1 and for any subset A ⊆ U of density γ (i. e., |A|/|U| = γ), it holds that for most subsets
S ∈ S, the density of A inside S is approximately γ (i. e., |A ∩ S|/|S| ≈ γ).
Suppose that we have an agreement tester for (C, S) as described above. We would like to show
that the local tester that queries a random S ∈ S is robustly sound. Let T be the collection of subsets
5 In the list decoding regime one would like to reject a function that is (1 − ε)-far from the code with very high probability of
1 − O(ε).
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 6
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
of U formed by the pairwise intersections of distinct sets in S. The main properties of S, T we need
are sampling properties, specifically, that S samples well inside U and that for any S ∈ S, the sets in
T contained in S sample well inside S. The main property of the code C we need is that for any set
T ∈ T, the code C|T := {c|T | c ∈ C} has large distance. In the case of lifted codes these properties can
be guaranteed by letting S and T be families of affine subspaces of fixed dimensions s and t, respectively,
where6 s t.
To see that the proposed local tester is indeed robustly sound, suppose we have a function f : U → Σ
that is close to C|S on a typical S ∈ S. Our goal is to show that f is close to a codeword g ∈ C. We first
create an instance ( fS )S for the agreement tester by letting fS ∈ C|S be the closest valid assignment to
f |S . Next observe that since f |S is typically close to fS , and by assumption the sets T sample well inside
the sets S, for a typical T and S, S0 containing T , it holds that both fS |T and fS0 |T are close to f |T , and
by the property that C|T has large distance for any T ∈ T, this implies in turn that typically fS |T = fS0 |T .
Consequently, agreement testability implies the existence of a codeword g ∈ C that agrees with most fS ,
and so g|S = fS and fS is close to f |S for most S. But since S samples well inside U we conclude that f
must be close to g as required.
2.3 Local testing implies agreement testing
We now turn to the local testing to agreement testing implication which is a bit more involved. Suppose
that we have a local testing algorithm for C that queries a random set K ∈ K and accepts if and only if
f |K ∈ C|K . We would like to obtain an agreement tester for C with respect to some collection of subsets
S. As before, let T be the collection of subsets of U formed by the pairwise intersections of sets in S.
Once more the main properties of S, T, K we require are sampling properties. Specifically, we need that S
samples well inside U, and that for any T ∈ T, all sets in K contained in T sample well inside T . We
also require distance properties of C, specifically that C,C|T ,C|S all have large distance for any S ∈ S and
T ∈ T. Once more, in the case of lifted codes these properties can be guaranteed by letting S, T, K be
families of affine subspaces of fixed dimensions s,t, k, respectively, where s t k.
To show agreement testability, let ( fS )S be a collection of valid assignments to sets in S (so fS ∈ C|S
for any S), and suppose that fS agrees with fS0 on S ∩ S0 for most pairs S, S0 . Our goal will be to find a
global codeword g ∈ C that agrees with most fS . We find the function g in the following three stages.
Initial stage. In the first stage we define for any K ∈ K a ‘most popular function’ PlurK by choosing the
most common value among fS |K going over all S ∈ S containing K. We then show, using the assumption
that the fS typically agree on their pairwise intersections, that this most popular function is obtained with
overwhelming probability for a typical K.
Local structure stage. In the second stage we define for each K ∈ K a function gK : U → Σ by letting
gK (x) be the most common ‘vote’ among all fS where S ⊇ K and x ∈ S and fS agrees with PlurK on K
(this function is well defined because of the initial stage). We then show that for a typical K, gK is close
to some function hK ∈ C, and moreover hK |S = fS for most S containing K.
6 In this paper, we use the informal notation s t for positive numbers s,t to indicate s is much greater than t.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 7
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
To see why the above holds, first note that by the assumptions that C|T has large distance for any
T ∈ T, and the sets K sample well inside each T if a pair of partial functions fS and fS0 agree on K then
they must typically also agree on their whole intersection. Therefore gK (x) is also typically defined
with overwhelming probability. Consequently, for a typical K, and most K 0 , gK |K 0 agrees with some fS .
Recalling that the fS are valid assignments, local testability then implies the existence of hK ∈ C that is
close to gK . The fact that hK |S = fS for most S containing K follows by the assumption that S samples
well inside U, and the distance property on S.
Global structure stage. In the final stage we show that there exists K̂ ∈ K such that hK̂ agrees with fS
for most S (not necessarily containing K̂). We can then set our ‘global function’ g to be equal to hK̂ . To
this end, we first observe that it suffices to show that most functions hK are in fact identical. This now
follows since for typical S ⊇ K ∪ K 0 it holds that hK |S = fS = hK 0 |S , and consequently since S samples
well inside U, it must typically hold that hK = hK 0 .
2.4 The proof method of Guo, Haramaty and Sudan
Guo, Haramaty and Sudan’s method [23] to show robust soundness of lifted codes is very different from
ours. In particular, it relies heavily on the algebraic structure of lifted codes. More specifically, the proof
is based on viewing the lifted codes as the intersection of ‘modified tensor codes.’ The tensor power
C⊗m of a code C ⊆ {Fq → Fq } can be thought of as the ‘axis-parallel lifting’ of C. That is, it is the code
that consists of all functions f : Fm q → Fq whose restrictions to any axis-parallel line belong to C. The
‘modified tensor code’ is a code of the form Cb⊗m where b is a direction in Fm ⊗m
q , and Cb consists of all
⊗m
functions f ∈ C whose restrictions to lines in direction b also belong to C.
The authors first use Viderman’s method [32], showing robust testing of tensor codes, to show that
the modified tensor codes are also robustly testable. They then use the fact that the lifted code is the
intersection of all codes of the form Cb⊗m for all directions b (this is true when the dimension of the base
code for lifting is ` = 1; when ` > 1 the proof becomes more complicated) to deduce robust testability
for the lifted code. However, since the intersection of robustly testable codes is not necessarily robustly
testable, non-trivial work is required to show robust testability, which in particular exploits the degree
structure of affine-invariant lifted codes.
The above program can be carried out only when the dimension m of the lifted code is a small constant
multiple of `, and the authors use the bootstrapping technique of [31, 2, 4, 1] to extend the result to
arbitrarily large m.
In contrast, we work directly with lifted codes of large dimension which allows us to exploit the
sampling properties of large affine subspaces in Fm q . To the best of our knowledge, even for the special
case of low-degree polynomials, this gives the first analysis of robust soundness that is not based on the
two-step approach of first analyzing the constant-dimensional case and only then moving to the general
case.
In contrast to the proof of Guo, Haramaty and Sudan [23] who reprove local testability along the way,
our proof uses local testability in a black-box manner. Thus, it exhibits a separation between the algebraic
properties that are used for showing local testability, and the combinatorial properties that are needed in
order to turn local testability into robust testability.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 8
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
Organization of the paper. The rest of the paper is organized as follows. In Section 3 we set some
notation, provide some definitions, and present the sampling properties of subspaces that we use. The
transformation from agreement testing to robust testing is given in Section 4, while the transformation
from local testing to agreement testing appears in Section 5. We conclude in Section 6 with the
full transformation from local testing to robust testing that proves our Main Theorem 1.1 and Main
Corollary 1.2.
3 Preliminaries
For a prime power q, let Fq denote the finite field of q elements. Let {Fm q → Fq } denote the set of functions
mapping Fm q to F q . In what follows we focus on codes which are sets of functions, C ⊆ {Fmq → Fq }. For
a pair of functions f , g : Fq → Fq , we use dist( f , g) to denote the fraction of inputs x ∈ Fm
m
q for which
f (x) 6= g(x). The minimum distance mindist(C) of the code C is min f 6=g∈C {dist( f , g)}. For a function
f : Fmq → Fq , we use dist( f ,C) to denote ming∈C {dist( f , g)}.
The code C is said to be linear if it is an Fq -linear subspace, i. e., C 6= 0/ and for every α ∈ Fq and
f , g ∈ C, we have α f + g ∈ C. A function A : Fm m
q → Fq is said to be an affine transformation if there exist
a matrix M ∈ Fqm×m and a vector b ∈ Fm q such that A(x) = Mx + b. The code C is said to be affine invariant
if for every affine transformation A and every f ∈ C we have f ◦ A ∈ C (where ( f ◦ A)(x) = f (A(x))).
3.1 Lifted codes
A subset L ⊆ Fm q is said to be an `-dimensional affine subspace if there exist u0 ∈ Fq and linearly
m
`
independent u1 , . . . , u` ∈ Fm
q such that L = {u0 + ∑i=1 ui xi | x1 , . . . , x` ∈ Fq }. We fix an arbitrary invertible
affine map γL : F`q → L (which we can view as a parameterization of L). For a function f : Fm q → Fq , the
restriction f |L is viewed as a function in {F`q → Fq } through f ◦ γL : F`q → Fq . In particular, when we ask
?
if f |L ∈ C ⊆ {F`q → Fq } what we are really asking is whether f ◦ γL ∈ C. Note that if C is affine-invariant,
whether f |L ∈ C does not depend on the choice of the parametrization γL .
Definition 3.1 (Lifted codes). Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and m ≥ `. The
m-dimensional lift C`%m of C is given by
C`%m := f : Fm m
q → Fq | f |L ∈ C for every `-dimensional affine subspace L ⊆ Fq .
Proposition 3.2 (Distance of lifted codes, [24, Theorem 5.1, Part (2)]). Let C ⊆ {F`q → Fq } be an
affine-invariant linear code, and m ≥ `. Then mindist(C`%m ) ≥ mindist(C) − q−` .
3.2 Local testing, robust testing, and agreement testing
We now formally define the notions of local testing, robust testing, and agreement testing, specialized to
the class of lifted codes and subspace testers. In the case of local testing and robust testing this simply
means that the tester samples a uniform random k-dimensional affine subspace and its accepting views
are codewords in C`%k .
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 9
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
Definition 3.3 (Local testing of lifted codes). Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and
m ≥ k ≥ `. The m-dimensional lift C`%m is (k, α)-testable if for every f : Fm q → Fq it holds that
/ C`%k ≥ α · dist( f ,C`%m ) ,
Pr f |K ∈
K
where the probability is over a uniform random k-dimensional affine subspace K ⊆ Fm
q.
Recall the definition of the `-dimensional test in the paragraph before Main Theorem 1.1.
Theorem 3.4 ([28, Theorem 2.9]). Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and m ≥ `. Then
1
−2`
the `-dimensional test rejects a function f : Fm
q → Fq with probability at least 2 ·min q , dist( f ,C`%m ) .
−2`
In particular, C`%m is `, q 2 -testable.
Definition 3.5 (Robust testing of lifted codes). Let C ⊆ {F`q → Fq } be an affine-invariant linear code,
and m ≥ k ≥ `. The m-dimensional lift C`%m is (k, α)-robust if for every f : Fm
q → Fq it holds that
EK dist( f |K ,C`%k ) ≥ α · dist( f ,C`%m ) ,
where the expectation is over a uniform random k-dimensional affine subspace K ⊆ Fm
q.
We note the following easy implications.
Proposition 3.6. Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and m ≥ k ≥ `. Then the
following hold.
1. If C`%m is (k, α)-robust then it is (k, α)-testable.
2. If C`%m is (k, α)-testable then it is (k, α · q−k )-robust.
3. If C`%m is (k, α)-testable then it is (r, α)-testable for any k ≤ r ≤ m.
4. If C`%m is (k, α)-robust then it is (r, α)-robust for any k ≤ r ≤ m.
/ C`%k whenever dist( f |K ,C`%k ) > 0, while Part (2) follows since
Proof. Part (1) follows since f |K ∈
`%k −k
dist( f |K ,C ) ≥ q whenever f |K ∈ / C`%k .
Part (3) follows by observing that for a uniform random r-dimensional affine subspace R,
h i
/ C`%r = ER 1 f |R ∈C
Pr f |R ∈ / `%r
R
`%k
≥ ER Pr f |K ∈ /C
K⊆R
/ C`%k ,
= Pr f |K ∈
K
where the inequality follows since f |R ∈ C`%r implies that f |K ∈ C`%k for any K.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 10
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
Finally, Part (4) follows by letting fR be the codeword in C`%r that is closest to f |R , and noting that
ER dist( f |R ,C`%r ) = ER dist( f |R , fR )
= ER EK⊆R dist( f |K , fR |K )
h i
≥ ER EK⊆R dist( f |K ,C`%k )
= EK dist( f |K ,C`%k ) ,
where the inequality follows since fR |K ∈ C`%k for any K.
We now turn to the definition of agreement testing. The agreement testers we consider are testers
that for t < s, sample a uniform random t-dimensional affine subspace T , and a pair of uniform random
s-dimensional affine subspaces S, S0 containing T , and accept if and only if fS , fS0 agree on T .
For a code C ⊆ {Fm q → Fq }, we let C(s) be the code containing all collections ( f S )S of partial
assignments to s-dimensional affine subspaces that are consistent with some global codeword g ∈ C,
formally,
C(s) := ( fS )S | ∃ g ∈ C such that g|S = fS for any s-dimensional affine subspace S .
For a pair of collections ( fS )S , (gS )S of partial assignments to s-dimensional affine subspaces, we denote
by dist(( fS )S , (gS )S ) the fraction of s-dimensional affine subspaces S for which fS 6= gS , and we define
dist(( fS )S ,C(s)) accordingly.
Definition 3.7 (Agreement testing of lifted codes). Let C ⊆ {F`q → Fq } be an affine-invariant linear code,
and m ≥ s > t ≥ `. The m-dimensional lift C`%m is (s,t, α)-agreement testable if for every collection
( fS )S where fS ∈ C`%s for every s-dimensional affine subspace S it holds that
[ fS |T 6= fS0 |T ] ≥ α · dist ( fS )S ,C`%m (s) ,
Pr 0
T, S⊇T, S ⊇T
where the probability is over a uniform random t-dimensional affine subspace T ⊆ Fm
q , and uniform
0
random s-dimensional affine subspaces S, S containing T .
3.3 Sampling properties of affine subspaces
Let T be a collection of affine subspaces T ⊆ Fm q of dimension t, and let S be a collection of affine
subspaces S ⊆ Fm q of dimension s, where t < s. Let I(T, S) denote the bipartite inclusion graph whose
left side is T and right side is S and T ∈ T and S ∈ S are adjacent if and only if T ⊆ S. For α, β ∈ (0, 1),
we say that I(T, S) is an (α, β )-hitting sampler if for every subset A ⊆ T with |A| ≥ α|T|, it holds that
|N(A)| ≥ (1 − β )|S|, where N(A) denotes the set of neighbors of A in S.
First we note that in the case where T is the collection of all points in Fm
q (i. e., 0-dimensional affine
subspaces), and S is the collection of all s-dimensional affine subspaces, the hitting sampler property is
an immediate consequence of the fact that points in a random affine subspace are uniformly distributed
and pairwise independent, and Chebyshev’s inequality.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 11
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
Lemma 3.8. Let 0 < s < m, let T be the collection of all points in Fm q , and let S be the collection
of all s-dimensional affine subspaces of Fm
q . Then for any α > 0, the inclusion graph I(T, S) is an
−s
(α, qα )-hitting sampler.
The following lemma from [26] is an extension for the case where for a fixed affine subspace R ⊆ Fm q
of dimension r < s, T is the collection of all points in Fm
q \ R, and S is the collection of all s-dimensional
affine subspaces containing R.
Lemma 3.9 ([26, Lemma 2.12]). Let 0 < r < s < m, and let R ⊆ Fm q be an affine subspace of dimension
r. Let T be the collection of all points in Fq \ R, and let S be the collection of all s-dimensional affine
m
4q −(s−r−2)
q containing R. Then for any α > 0, the inclusion graph I(T, S) is an (α,
subspaces in Fm α )-hitting
sampler.
Remark 3.10. [26, Lemma 2.11] is only stated for the case where s = m2 , while [26, Lemma 2.12] is only
stated for the case where r = 2s . However, it can easily be seen that the proof implies the bounds we state
for general values of 0 < r < s < m.
Finally, we cite the following lemma, due to Impagliazzo, Kabanets and Wigderson [27], which deals
with the case where T is the collection of all t-dimensional linear subspaces, and S is the collection of all
s-dimensional linear subspaces.
Lemma 3.11 ([27, Lemma 2.3]). Let 0 < t < s < m, let T be the collection of all t-dimensional linear
q , and let S be the collection of all s-dimensional linear subspaces in Fq . Then for any
subspaces in Fm m
−(s−t)
α > 0, the inclusion graph I(T, S) is an (α, 18q α )-hitting sampler.
Remark 3.12. [27, Lemma 2.3] gives a worse bound for the case that I(T, S) is an averaging sampler.7
However, the proof first gives the bound we state, and only then shows how to deduce the worse bound
for the case of an averaging sampler.
We further observe that Lemma 3.11 gives a similar bound for affine subspaces.
Corollary 3.13. Let 0 < t < s, let T be the collection of all t-dimensional affine subspaces in Fm
q , and let
S be the collection of all s-dimensional affine subspaces in Fq . Then for any α > 0, the inclusion graph
m
−(s−t−1)
I(T, S) is an (α, 18q α )-hitting sampler.
Proof. Let A ⊆ T be a collection of t-dimensional affine subspaces in Fm q so that |A| ≥ α|T|. Let S ∈ S
be a uniformly random s-dimensional affine subspace. Then S can be sampled by first picking a random
affine shift v ∈ Fm m
q , then picking a random s-dimensional linear subspace V ⊆ Fq so that v ∈ / V \ {0},
m
and finally letting S = v +V . As for a fixed vector v ∈ Fq , and a random s-dimensional linear subspace
V ⊆ Fm −(m−s) , which is negligible in our setting, we
q , we have that v ∈ V with probability at most q
may assume that V is a completely random s-dimensional linear subspace. Next observe that v + V
contains a t-dimensional affine subspace T = w + W ∈ A if V contains Span{w − v,W }. The proof is
completed by noting that, conditioned on choosing v, by Lemma 3.11, V contains Span{w − v,W } for
some T = w +W ∈ A with probability at least 1 − 18 · q−(s−t−1) /α.
7 For α, β ∈ (0, 1), we say that I(T, S) is an (α, β )-averaging sampler if for every subset A ⊆ T with |A| ≥ α|T|, for at least
|A∩N(S)|
a (1 − β )-fraction of the vertices S ∈ S it holds that deg(S)
−α ≤ α2 . Note that an (α, β )-averaging sampler is in particular
an (α, β )-hitting sampler.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 12
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
4 From agreement testing to robust testing
In this section we prove the following lemma, showing the agreement testing to robust testing implication.
Lemma 4.1 (Agreement testing implies robust testing). Let C ⊆ {F`q → Fq } be an affine-invariant linear
code, and m ≥ s > t ≥ `. Suppose that C`%m is (s,t, α)-agreement testable, and let δ := mindist(C`%t ).
Then C`%m is s, Ω(αδ ) -robust.
Proof. For simplicity of notation, in what follows we let T, S denote the random variables obtained by
sampling a uniform random affine subspace of dimension t, s respectively. Suppose that f : Fm q → Fq has
`%s
ES [dist( f |S ,C )] ≤ ε. Our goal is to find a codeword g ∈ C `%m such that dist( f , g) ≤ O(ε/(αδ )).
The proof proceeds as follows. We would like to apply our assumption on agreement testability,
and towards this, we create an instance ( fS )S for the agreement tester by letting fS be the codeword
in C`%s that is closest to f |S . We then use the fact that fS is typically close to f |S , together with the
fact that t-dimensional affine subspaces sample well inside s-dimensional affine subspaces, and the
assumption that C has large distance on t-dimensional affine subspaces of the domain Fsq , to show
that PrT, S⊇T, S0 ⊇T [ fS |T 6= fS0 |T ] is small. Agreement testability then gives a codeword g ∈ C`%m that is
consistent with most fS , and using the fact that s-dimensional affine subspaces sample well inside Fm q this
implies in turn that dist( f , g) is small. Details follow.
We begin by showing that PrT, S⊇T, S0 ⊇T [ fS |T 6= fS0 |T ] is small. Recall first that ES [dist( f |S , fS )] =
ES [dist( f |S ,C`%s )] ≤ ε. Next observe that for a fixed s-dimensional affine subspace S, any point in a
uniform random t-dimensional affine subspace contained in S is uniform in S. Thus we also have that
ES, T ⊆S [dist( f |T , fS |T )] ≤ ε, and consequently
Pr 0 dist( fS |T , fS0 |T ) ≥ δ ≤ 2 · Pr dist( f |T , fS |T ) ≥ δ /2
T, S⊇T, S ⊇T T, S⊇T
= 2 · Pr dist( f |T , fS |T ) ≥ δ /2
S, T ⊆S
4ε
≤ .
δ
But since fS |T , fS0 |T are both codewords of C`%t , a code of minimum distance δ , the above implies in
turn that PrT, S⊇T, S0 ⊇T [ fS |T 6= fS0 |T ] ≤ 4ε
δ .
Our assumption on agreement testability now gives a codeword g ∈ C`%m that has PrS [g|S 6= fS ] ≤
4ε/(αδ ). But since any point in a uniform random s-dimensional affine subspace is uniform in Fm q this
gives in turn that
4ε 5ε
dist( f , g) = ES dist( f |S , g|S ) ≤ ES dist( f |S , fS ) + ES dist( fS , g|S ) ≤ ε + ≤ .
αδ αδ
5 From local testing to agreement testing
In this section we prove the following lemma that gives the local testing to agreement testing implication.
Lemma 5.1 (Local testing implies agreement testing). Let C ⊆ {F`q → Fq } be an affine-invariant linear
code, and m ≥ k ≥ `. Suppose that C`%m is (k, α)-testable, and let δ := mink≤r≤m mindist(C`%r ). Then
C`%m is (2k + 2 + logq (4/δ ), k + 1, Ω(α · δ 2 ))-agreement testable.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 13
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
Proof outline. For simplicity of notation, in what follows let s := 2k + 2 + logq (4/δ ) and t := k + 1. We
let both S, S0 (T , T 0 and K, K 0 , resp.) denote random variables obtained by sampling a uniform random
affine subspace of dimension s (t, k, resp.).
Let ( fS )S be a collection of partial assignments such that fS ∈ C`%s for every S, and
Pr [ fS |T 6= fS0 |T ] ≤ ε . (5.1)
T, S⊇T, S0 ⊇T
Our goal is to find a global codeword g ∈ C`%m that has
ε
Pr[g|S 6= fS ] ≤ O . (5.2)
S α ·δ2
We find the codeword g in three stages.
1. In the initial stage (Section 5.1) we define, for any k-dimensional affine subspace K, a ‘most popular
function’ PlurK : Fkq → Fq by choosing the most common value among fS |K going over all S ⊇ K.
We show that for a typical K, this function is obtained with an overwhelming plurality of 1 − O(ε).
2. In the “local structure” stage (Section 5.2) we define, for any k-dimensional affine subspace K,
a function gK : Fmq → Fq by letting gK (x) be the most common ‘vote’ among all f S that contain
both K and x and agree with PlurK on K. We then show that for a typical K, gK is close to some
codeword hK ∈ C`%m , and moreover hK |S = fS for most S containing K.
3. In the “global structure" stage (Section 5.3) we show that there exists K̂ for which hK̂ |S = fS for
most S (not necessarily containing K̂). We can then set our ‘global function’ g to be equal to hK̂ .
5.1 Initial stage
For any k-dimensional affine subspace K, we let PlurK : Fkq → Fq denote the most common value among
fS |K for S containing K. That is,
PlurK := pluralityS⊇K { fS |K } .
Next we use our assumption (5.1) to show that for a typical K, the function PlurK is obtained with
overwhelming plurality.
Lemma 5.2.
EK Pr fS |K 6= PlurK ≤ 2ε .
S⊇K
Proof. Since the collision probability lower bounds the probability of hitting the most common value, it
suffices to show that
Pr 0 fS |K 6= fS0 |K ≤ 2ε . (5.3)
K, S⊇K, S ⊇K
Clearly if t = k we would be done by (5.1), so the whole point is to show the same for t > k. We
describe a distribution on triples (S1 , S0 , S2 ) such that (S1 , S2 ) are distributed as in (5.3) but the pairs
(S1 , S0 ) and (S0 , S2 ) are distributed as in (5.1):
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 14
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
1. Choose a uniform random k-dimensional affine subspace K.
2. Choose a pair of uniform random t-dimensional affine subspaces T1 , T2 containing K.
3. For i = 1, 2, choose a uniform random s-dimensional affine subspace Si containing Ti .
4. Choose a uniform random s-dimensional affine subspace S0 containing T1 ∪ T2 (this can be done
since t = k + 1 and s ≥ k + 2).
One can check that indeed K, S1 , S2 are distributed as in (5.3) while Ti , Si , S0 are distributed as in (5.1).
Thus by our assumption (5.1),
Pr fS1 |K 6= fS2 |K ≤ Pr 0 fS1 |T1 6= fS0 |T1 + Pr fS0 |T2 6= fS2 |T2 ≤ 2ε .
K, S1 ⊇K, S2 ⊇K T1 , S1 ⊇T1 , S ⊇T1 T2 , S0 ⊇T2 , S2 ⊇T2
5.2 Local structure
Next we define for every k-dimensional affine subspace K the function gK : Fm
q → Fq . As described above,
m
for every x ∈ Fq , we let gK (x) be the most common value among fS (x) for S that contain both K and x
and agree with PlurK on K. That is,
gK (x) := pluralityS⊇K∪{x}, fS |K =PlurK { fS (x)} .
Next we would like to show that for a typical K, gK is close to some codeword hK ∈ C`%m , and
additionally hK |S = fS for most S containing K. We show these in three steps:
1. Boosting step (Lemma 5.3): In this step we show that for typical K, x, the plurality in the definition
of gK (x) is obtained with overwhelming probability.
2. LTC step (Lemma 5.4): In this step we use the previous step to show that for a typical gK , for most
K 0 , gK |K 0 agrees with some fS on K 0 , and therefore is a codeword of C`%k . By local testability
assumption this implies in turn that such gK is close to being in the code C`%m , and we denote by
hK ∈ C`%m the closest codeword to gK .
3. Agreement step (Lemma 5.5): In this step we show that a typical hK agrees with most fS for S ⊇ K.
We start with the boosting step, showing that for typical K, x, the plurality in the definition of gK (x) is
obtained with overwhelming probability. Intuitively, this follows by the assumption that the code has large
distance on t-dimensional affine subspaces of the domain Fsq , together with the fact that k-dimensional
affine subspaces sample well inside t-dimensional affine subspaces, which imply that if a pair of fS agree
on K then they must typically also agree on their whole intersection.
Lemma 5.3 (Boosting step).
ε
fS (x) 6= gK (x) fS |K = PlurK ≤ O q−k ·
EK, x∈K
/ Pr .
S⊇K∪{x} δ · (1 − 4ε)
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 15
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
Proof. Since the collision probability lower bounds the probability of hitting the most common value, it
suffices to show that
−k ε
Pr fS (x) 6= fS0 (x) | fS |K = fS0 |K = PlurK ≤ O q · .
/ S⊇K∪{x}, S0 ⊇K∪{x}
K, x∈K, δ · (1 − 4ε)
Now we have that
Pr fS (x) 6= fS0 (x) | fS |K = fS0 |K = PlurK
/ S⊇K∪{x}, S0 ⊇K∪{x}
K, x∈K,
≤ Pr 0 fS |T 6= fS0 |T | fS |K = fS0 |K = PlurK
K, T ⊇K, S⊇T, S ⊇T
PrT, S⊇T, S0 ⊇T, K⊆T fS |K = fS0 |K = PlurK | fS |T 6= fS0 |T · PrT, S⊇T, S0 ⊇T fS |T 6= fS0 |T
= ,
PrK, T ⊇K, S⊇T, S0 ⊇T fS |K = fS0 |K = PlurK
where the inequality follows recalling that t = k + 1, and so K and x span a random t-dimensional
subspace. Next we bound each of the terms above.
By our assumption (5.1), the right hand term in the numerator is not greater than ε. To bound the
denominator note that by Lemma 5.2,
Pr [ fS |K = fS0 |K = PlurK ] ≥ 1 − 2 · Pr [ fS |K 6= PlurK ] ≥ 1 − 4ε . (5.4)
K, T ⊇K, S⊇T, S0 ⊇T K, S⊇K
To bound the left hand term in the numerator note first that since fS , fS0 are both codewords of C`%s
then fS |T , fS0 |T are distinct codewords in C`%t , and so dist( fS |T , fS0 |T ) ≥ δ . We now apply Theorem 3.8
on the graph I(T, K), where the ambient space is T , T contains all points in T , and K contains all
−k
k-dimensional subspaces in T . By Theorem 3.8, the graph I(T, K) is a (δ , qδ )-hitting sampler, and so
−k
taking A0 = {x ∈ T | fS (x) 6= fS0 (x)} we deduce that at most a qδ -fraction of K can miss A altogether.
Thus,
q−k
Pr f S |K = f S 0 |K f S |T 6
= f S 0 |T ≤ . (5.5)
T, S⊇T, S0 ⊇T, K⊆T δ
The final bound is obtained by combining the bounds in (5.1), (5.4), and (5.5).
Next we use the assumption on local testability to show that for a typical K, gK is close to being a
codeword of C`%m .
Lemma 5.4 (LTC step). h ε
`%m
i
EK dist gK ,C ≤O .
α ·δ
Proof. To apply our assumption on local testability we first show that gK |K 0 is typically a codeword of
C`%k . For this, first observe that if gK |K 0 is not a codeword of C`%k then gK |K 0 6= fS |K 0 for all S (since
fS ∈ C`%s and so fS |K 0 ∈ C`%k ). Thus we have
h i
EK, K 0 1gK |K 0 ∈C
/ `%k ≤ EK, K 0 Pr [gK |K 0 6= fS |K 0 ]
S⊇K∪K 0
≤ EK, K 0 Pr 0 gK |K 0 6= fS |K 0 fS |K = PlurK + Pr [ fS |K 6= PlurK ] .
S⊇K∪K K, S⊇K
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 16
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
We claim that the above expression is at most O(ε/δ ). To see this note first that by Lemma 5.2 the
right hand term is at most 2ε . To bound the left hand term, note that since each individual point in K 0 is
uniformly distributed in Fmq this term is not greater than
k
q · EK, x Pr gK (x) 6= fS (x) fS |K = PlurK ,
S⊇K∪{x}
which is in turn at most O(ε/δ ) by Lemma 5.3 (noting that the probability in the above expression is
zero whenever x ∈ K).
`%k . Then on the one
Finally, for any k-dimensional affine subspace K, let εK := PrK 0 gK |K 0 ∈
/ C
h i
hand EK [εK ] = EK, K 0 1gK |K 0 ∈C
/ `%k ≤ O(ε/δ ), and on the other hand dist(gK ,C
`%m ) ≤ ε /α for any K
K
by assumption that C`%m is (k, α)-testable. We conclude that
h i hε i ε
K
EK dist gK ,C`%m ≤ EK ≤O .
α α ·δ
For any k-dimensional affine subspace K, let hK ∈ C`%m be the codeword that is closest to gK . Then
by the above lemma, ε
EK dist(gK , hK ) ≤ O .
α ·δ
The following lemma says that for a typical K, we have that hK |S = fS for most S containing K, which
follows by the fact that s-dimensional affine subspaces sample well inside Fm
q and by assumption that the
code has large distance on s-dimensional affine subspaces of the domain Fq .m
Lemma 5.5 (Agreement step).
ε
EK Pr hK |S 6= fS ≤ O .
S⊇K α ·δ2
Proof. We show that for typical S ⊇ K, on the one hand, by Lemma 5.4 and the fact that s-dimensional
affine subspaces sample well inside Fm q , dist(hK |S , gK |S ) is small, and on the other hand, by Lemma 5.3,
dist(gK |S , fS ) is small. We then conclude by triangle inequality that dist(hK |S , fS ) is small, which implies
in turn that hK |S = fS by assumption that the code has large distance on s-dimensional subspaces of the
domain Fm q.
We start by showing that dist(hK |S , gK |S ) is typically small. For this note that for a fixed k-dimensional
affine subspace K, and uniform random S containing K, each individual point in S \ K is uniformly
distributed in Fm q \ K. Thus we have
EK dist(hK , gK ) ε
EK, S⊇K dist(hK |S\K , gK |S\K ) ≤ ≤ O ,
1 − q−(m−k) α ·δ
where the last inequality follows by Lemma 5.4. Markov’s inequality then implies that dist(hK |S\K , gK |S\K )
≤ δ4 with probability at least 1 − O α·δ ε
2 over the choice of K and S ⊇ K. We conclude that with
ε
probability at least 1 − O α·δ 2 over the choice of K and S ⊇ K, it holds that
δ δ
dist(hK |S , gK |S ) ≤ + q−(s−k) ≤ , (5.6)
4 2
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 17
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
where the last inequality follows by choice of s ≥ k + logq (4/δ ).
Next we show that dist(gK |S , fS ) is typically small. For this note that
EK, S⊇K dist(gK |S , fS )
≤ Pr [gK |K 6= fS |K ] + EK, S⊇K dist(gK |S , fS ) | gK |K = fS |K
K, S⊇K
≤ Pr [gK |K 6= fS |K ] + EK, S⊇K dist(gK |S\K , fS |S\K ) | gK |K = fS |K
K, S⊇K
= Pr [ fS |K 6= PlurK ] + EK, x∈K/ Pr gK (x) 6= fS (x) fS |K = PlurK
K, S⊇K S⊇K∪{x}
ε
≤O , (5.7)
δ
where the last inequality follows by Lemmas 5.2 and 5.3. Markov’s inequality then implies that
δ
dist(gK |S , fS ) ≤ (5.8)
4
with probability at least 1 − O δε2 over the choice of K and S ⊇ K.
Combining (5.6) and (5.7), by aunion bound and triangle inequality, we have that dist(hK |S , fS ) < δ
ε
with probability at least 1 − O α·δ 2 over the choice of K and S ⊇ K. Finally, since both hK |S and fS are
`%s `%s ε
codewords of C and mindist(C ) ≥ δ we conclude that hK |S 6= fS with probability at most O α·δ 2
over the choice of K and S ⊇ K.
5.3 Global structure
We now complete the proof of Lemma 5.1 by showing that there exists a codeword g ∈ C`%m that
agrees with most fS . We start by showing that most functions hK are in fact identical, which follows by
Lemma 5.5 and the fact that s-dimensional affine subspaces sample well inside Fm q.
Lemma 5.6. There exists a k-dimensional affine subspace K̂ such that
ε
Pr hK 6= hK̂ ≤ O .
K α ·δ2
Proof. By Lemma 5.5,
ε
Pr hK |S 6
= hK 0 |S ≤ 2 · Pr h K |S 6
= f S ≤ O ,
K, K , S⊇K∪K 0
0 K, S⊇K α ·δ2
and so by averaging there exists K̂ such that
ε
Pr hK |S 6= hK̂ |S ≤ O .
K, S⊇K∪K̂ α ·δ2
Markov’s inequality then implies that
1
Pr hK |S 6= hK̂ |S ≥
S⊇K∪K̂ 2
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 18
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
ε
with probability at most O α·δ 2 over the choice of K.
1
Next we claim
that when h K 6
= hK̂ then PrS⊇K∪K̂ hK |S 6
= h K̂ |S ≥ 2 , and so hK 6= hK̂ with probability
ε
at most O α·δ 2 over the choice of K. To this end, observe that if hK 6= hK̂ then since hK , hK̂ are both
codewords of C`%m and mindist(C`%m ) ≥ δ , it must hold that dist(hK , hK̂ ) ≥ δ . If hK and hK̂ differ on
some point of K ∪ K̂, then we clearly have that PrS⊇K∪K̂ hK |S 6= hK̂ |S = 1, and so we are done. Hence,
we may assume that hK agrees with hK̂ on K ∪ K̂, and so dist hK |Fmq \(K∪K̂) , hK̂ |Fmq \(K∪K̂) ≥ δ .
We now apply Lemma 3.9 on the graph I(Fm q \ (K ∪ K̂), S) that connects the points of Fq \ (K ∪ K̂)
m
on the left to the s-dimensional affine subspaces containing K ∪ K̂ on the right. By Lemma 3.9, the graph
4q−(s−2k−2)
I(Fmq \ (K ∪ K̂), S) is a (δ , δ )-hitting sampler, and so taking
A0 = x ∈ Fm
q \ (K ∪ K̂) hK (x) 6= hK̂ (x) ,
we deduce that
q−(s−2k−2) 1
Pr hK̂ |S 6= hK |S ≥ 1 − ≥ ,
S⊇K̂∪K δ 2
where the last inequality follows by assumption that s ≥ 2k + 2 + logq (2/δ ).
ε
It now follows that hK 6= hK̂ with probability at most O α·δ 2 over the choice of K.
We can now complete the proof of Lemma 5.1.
Proof of Lemma 5.1. Set g ∈ C`%m to be the function hK̂ guaranteed by Lemma 5.6. By Lemmas 5.5
and 5.6,
ε
Pr g|S 6= fS = Pr g|S 6= fS ≤ Pr g 6= hK + Pr hK |S 6= fS ≤ O .
S K, S⊇K K K, S⊇K α ·δ2
So g satisfies (5.2) as required.
6 From local testing to robust testing
6.1 Proof of Main Theorem 1.1
We can now combine Lemmas 4.1 and 5.1 to prove our Main Theorem 1.1, restated below, showing a
transformation from local testing to robust testing.
Main Theorem 1.1. Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and m ≥ k ≥ `. Suppose
that C`%m is locally testable using the k-dimensional test with query complexity qk and soundness α,
and let δ := mink≤r≤m mindist(C`%r ). Then C`%m is robustly testable using the (2k + 2 + logq (4/δ ))-
dimensional test with query complexity O(q2k+2 /δ ) and robust soundness Ω(α · δ 3 ).
Proof of Main Theorem 1.1. By Lemma 5.1 we have that C`%m is (2k + 2 + logq (4/δ ), k + 1, Ω(α · δ 2 ))-
agreement testable, and by Lemma 4.1 this implies in turn that C`%m is (2k + 2 + logq (4/δ ), Ω(α · δ 3 ))-
robust.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 19
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
6.2 Proof of Main Corollary 1.2
We now instantiate our Main Theorem 1.1 with Theorem 3.4 to show that lifted codes are robustly testable.
For this, we first observe that one can amplify the soundness of the tester given by Theorem 3.4 to a
constant (independent of q and `) at the cost of increasing the testing dimension to ≈ 3`.
Proposition 6.1. Let C ⊆ {F`q → Fq } be an affine-invariant linear code, and m ≥ 3` + 1 + logq 72. Then
C`%m is 3` + 1 + logq 72, Ω(1) -testable.
Proof. If the `-dimensional test rejects with probability at least 12 · dist( f ,C`%m ) then by Part (3) of
Proposition 3.6, the (3` + logq 4)-dimensional test also rejects with the same probability and we are done.
Otherwise, by Theorem 3.4, the `-dimensional test rejects with probability at least 21 · q−2` .
Consider the graph I(S, T) with left hand side being all `-dimensional affine subspaces of Fmq and right
hand side being all (3` + 1 + logq 72)-dimensional affine subspaces of Fm q . Next we apply Corollary 3.13
on the graph I(S, T) with A being the collection of all `-dimensional affine subspaces on which the
0
`-dimensional test rejects. Noting that the (3` + 1 + logq 72)-dimensional test will reject on any neighbor
of A we conclude that the (3` + 1 + logq 72)-dimensional test rejects with probability at least
18q−(2`+logq 72) q−(2`+logq 4) 1
1− = 1 − = .
q−2` /2 q−2` /2 2
We now turn to the proof of Main Corollary 1.2, restated below.
Main Corollary 1.2. There exists an absolute constant c > 1 so that the following holds. Let C ⊆ {F`q →
Fq } be an affine-invariant linear code of minimum distance δ , and m ≥ `. Then C`%m is robustly testable
using the (6` + 4 + logq (c/δ ))-dimensional test with robust soundness Ω(δ 3 ).
Proof. Suppose first that δ < 2q−` . In this case by Theorem 3.4, C`%m is (`, Ω(q−2` ))-testable, and so
by Part (2) of Proposition 3.6, C`%m is also robustly testable using the `-dimensional test with robust
−3` ≥ Ω(δ 3 ). By Part (4) of Proposition 3.6 it follows that the (6` + 4 + logq (c/δ ))-
soundness Ω q
dimensional test also has robust soundness Ω(δ 3 ).
Next assume that δ ≥ 2q−` . In this case Proposition 3.2 gives that mindist(C`%r ) ≥ δ /2 for any
` ≤ r ≤ m, and so we may apply Proposition 6.1 and Main Theorem 1.1 and conclude that C`%m is
(6` + 4 + logq (c/δ ), Ω(δ 3 ))-robust for an absolute constant c > 1.
References
[1] S ANJEEV A RORA: Probabilistic Checking of Proofs and the Hardness of Approximation Problems.
Ph. D. thesis, UC Berkeley, 1994. ECCC. 8
[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, ECCC:TR98-008] 5, 8
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 20
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
[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]
5
[4] S ANJEEV A RORA AND M ADHU S UDAN: Improved low-degree testing and its applications. Combi-
natorica, 23(3):365–426, 2003. Preliminary version in STOC’97. [doi:10.1007/s00493-003-0025-0,
ECCC:TR97-003] 6, 8
[5] 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] 5
[6] 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] 5
[7] E LI B EN -S ASSON , O DED G OLDREICH , P RAHLADH H ARSHA , M ADHU S UDAN , AND S ALIL
VADHAN: Robust PCPs of proximity, shorter PCPs and applications to coding. SIAM J. Com-
put., 36(4):889–974, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539705446810,
ECCC:TR04-021] 3
[8] E LI B EN -S ASSON , P RAHLADH H ARSHA , AND S OFYA R ASKHODNIKOVA: Some 3CNF prop-
erties are hard to test. SIAM J. Comput., 35(1):1–21, 2005. Preliminary version in STOC’03.
[doi:10.1137/S0097539704445445] 2
[9] E LI B EN -S ASSON , G HID M AATOUK , A MIR S HPILKA , AND M ADHU S UDAN: Symmetric LDPC
codes are not necessarily locally testable. In Proc. 26th IEEE Conf. on Comput. Complexity
(CCC’11), pp. 55–65. IEEE Comp. Soc., 2011. [doi:10.1109/CCC.2011.14, ECCC:TR10-199] 3
[10] E LI B EN -S ASSON AND M ADHU S UDAN: Robust locally testable codes and products of
codes. Random Struct. Algor., 28(4):387–402, 2006. Preliminary version in RANDOM’04.
[doi:10.1002/rsa.20120, arXiv:cs/0408066, ECCC:TR04-046] 3
[11] E LI B EN -S ASSON AND M ICHAEL V IDERMAN: Composition of semi-LTCs by two-wise tensor
products. Comput. Complexity, 24(3):601–643, 2015. Preliminary version in RANDOM’09.
[doi:10.1007/s00037-013-0074-8, ECCC:TR11-070] 3
[12] M ANUEL B LUM , M ICHAEL L UBY, AND RONITT RUBINFELD: Self-testing/correcting with appli-
cations to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version
in STOC’90. [doi:10.1016/0022-0000(93)90044-W] 6
[13] YOTAM D IKSTEIN AND I RIT D INUR: Agreement testing theorems on layered set systems. In
Proc. 60th FOCS, pp. 1495–1524. IEEE Comp. Soc., 2019. [doi:10.1109/FOCS.2019.00088,
arXiv:1909.00638, ECCC:TR19-112] 6
[14] I RIT D INUR AND E LAZAR G OLDENBERG: Locally testing direct product in the low error range. In
Proc. 49th FOCS, pp. 613–622. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.26] 6
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 21
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
[15] I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI: From lo-
cal to robust testing via agreement testing. In Proc. 10th Innovations in Theoret. Comp.
Sci. Conf. (ITCS’19), pp. 29:1–18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.
[doi:10.4230/LIPIcs.ITCS.2019.29] 1, 6
[16] I RIT D INUR AND TALI K AUFMAN: High dimensional expanders imply agreement expanders. In
Proc. 58th FOCS, pp. 974–985. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.94, ECCC:TR17-
089] 6
[17] I RIT D INUR AND I NBAL L IVNI NAVON: Exponentially small soundness for the direct product
Z-test. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 29:1–29:50. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.29, ECCC:TR17-096]
6
[18] I RIT D INUR AND O MER R EINGOLD: Assignment testers: Towards a combinatorial proof of
the PCP Theorem. SIAM J. Comput., 36(4):975–1024, 2006. Preliminary version in FOCS’04.
[doi:10.1137/S0097539705446962] 3, 6
[19] I RIT D INUR AND DAVID S TEURER: Direct product testing. In Proc. 29th IEEE Conf. on Com-
put. Complexity (CCC’14), pp. 188–196. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.27,
ECCC:TR13-179] 6
[20] U RIEL F EIGE , S HAFI G OLDWASSER , L ÁSZLÓ L OVÁSZ , S HMUEL S AFRA , AND M ARIO S ZEGEDY:
Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, March 1996.
Preliminary version in FOCS’91. [doi:10.1145/226643.226652] 5
[21] P ETER G EMMELL , R ICHARD J. L IPTON , RONITT RUBINFELD , M ADHU S UDAN , AND AVI
W IGDERSON: Self-testing/correcting for polynomials and for approximate functions. In Proc. 23rd
STOC, pp. 32–42. ACM Press, 1991. [doi:10.1145/103418.103429] 6
[22] O DED G OLDREICH AND S HMUEL S AFRA: A combinatorial consistency lemma with application
to proving the PCP theorem. SIAM J. Comput., 29(4):1132–1154, 2000. Preliminary version in
RANDOM’97. [doi:10.1137/S0097539797315744, ECCC:TR96-047] 6
[23] A LAN G UO , E LAD H ARAMATY, AND M ADHU S UDAN: Robust testing of lifted codes with
applications to low-degree testing. In Proc. 56th FOCS, pp. 825–844. IEEE Comp. Soc., 2015.
[doi:10.1109/FOCS.2015.56, ECCC:TR15-043] 3, 4, 5, 8
[24] A LAN G UO , S WASTIK KOPPARTY, AND M ADHU S UDAN: New affine-invariant codes from lifting.
In Proc. 4th Innovations in Theoret. Comp. Sci. Conf. (ITCS’13), pp. 529–540. ACM Press, 2013.
[doi:10.1145/2422436.2422494, arXiv:1208.5413, ECCC:TR12-149] 3, 4, 9
[25] E LAD H ARAMATY, N OGA RON -Z EWI , AND M ADHU S UDAN: Absolutely sound testing of lifted
codes. Theory of Computing, 11(12):299–338, 2015. Preliminary version in RANDOM’13.
[doi:10.4086/toc.2015.v011a012, ECCC:TR13-030] 3, 4
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 22
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
[26] RUSSELL I MPAGLIAZZO , R AGESH JAISWAL , VALENTINE K ABANETS , AND AVI W IGDERSON:
Uniform direct product theorems: Simplified, optimized, and derandomized. SIAM J. Comput.,
39(4):1637–1665, 2010. Preliminary version in STOC’08. [doi:10.1137/080734030, ECCC:TR08-
079] 12
[27] RUSSELL I MPAGLIAZZO , VALENTINE K ABANETS , AND AVI W IGDERSON: New direct-product
testers and 2-query PCPs. SIAM J. Comput., 41(6):1722–1768, 2012. Preliminary version in
STOC’09. [doi:10.1137/09077299X, ECCC:TR09-090] 6, 12
[28] TALI K AUFMAN AND M ADHU S UDAN: Algebraic property testing: the role of invariance. In Proc.
40th STOC, pp. 403–412. ACM Press, 2008. [doi:10.1145/1374376.1374434, ECCC:TR07-111] 4,
5, 10
[29] 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,
ECCC:TR15-068] 3
[30] R AN R AZ AND S HMUEL S AFRA: A sub-constant error-probability low-degree test, and a sub-
constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM
Press, 1997. [doi:10.1145/258533.258641] 6
[31] RONITT RUBINFELD AND M ADHU S UDAN: Robust characterizations of polynomials with applica-
tions to program testing. SIAM J. Comput., 25(2):252–271, 1996. Preliminary versions in STOC’91
and SODA’92. [doi:10.1137/S0097539793255151] 6, 8
[32] M ICHAEL V IDERMAN: A combination of testability and decodability by tensor products. Random
Struct. Algor., 46(3):572–598, 2015. Preliminary version in RANDOM’12. [doi:10.1002/rsa.20498,
arXiv:1105.5806, ECCC:TR11-087] 3, 4, 8
AUTHORS
Irit Dinur
Department of Mathematics and Computer Science
Weizmann Institute
Rehovot, Israel
irit.dinur weizmann ac il
http://www.wisdom.weizmann.ac.il/~dinuri/
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 23
I RIT D INUR , P RAHLADH H ARSHA , TALI K AUFMAN , AND N OGA RON -Z EWI
Prahladh Harsha
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
prahladh tifr res in
http://www.tcs.tifr.res.in/~prahladh/
Tali Kaufman
Department of Computer Science
Bar-Ilan University
Ramat Gan, Israel
kaufmant mit edu
Noga Ron-Zewi
Department of Computer Science
University of Haifa
Haifa, Israel
noga cs haifa ac il
https://cs.haifa.ac.il/~noga
ABOUT THE AUTHORS
I RIT D INUR is a professor at the Weizmann Institute of Science. She received her Ph. D. in
2001 from Tel Aviv University under the supervision of Shmuel Safra. She is interested
broadly in theoretical computer science and mathematics, and more specifically in
complexity theory, probabilistically checkable proofs, hardness of approximation, and
most recently in the growing area of high-dimensional expansion. She has a wife and
three kids.
P RAHLADH H ARSHA is a theoretical computer scientist at the Tata Institute of Fundamental
Research (TIFR). He received his B. Tech. degree in Computer Science and Engineering
from the IIT Madras in 1998 and his S. M. and Ph. D. degrees in Computer Science
from MIT in 2000 and 2004, respectively; his Ph. D. advisor was Madhu Sudan. Prior
to joining TIFR in 2010, he was at Microsoft Research, Silicon Valley and at the
Toyota Technological Institute at Chicago. His areas of interest include computational
complexity, hardness of approximation, coding theory and information theory. Prahladh
credits his mother for his interest in mathematics and dance. He is also deeply indebted
to U Koteswara Rao, his high school mentor, for exposing him to the beauty and rigour
in mathematics.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 24
F ROM L OCAL TO ROBUST T ESTING VIA AGREEMENT T ESTING
TALI K AUFMAN is a professor at Bar Ilan University in Israel. She received her Ph. D.
degree from Tel-Aviv University in 2007 under the supervision of Noga Alon. Tali is
interested in the theory of computation with a specific interest in locally testable codes,
high-dimensional expanders, and their potential implications to CS.
N OGA RON -Z EWI is a professor at the Department of Computer Science at the University
of Haifa in Israel. She graduated from the Technion (Israel Institute of Technology) in
2014. Her Ph. D. advisor was Eli Ben-Sasson. Her research interests are in the theory
of computation, with a focus on research topics at the interface of communication and
computation.
T HEORY OF C OMPUTING, Volume 18 (12), 2022, pp. 1–25 25