# Approaching the Soundness Barrier:
A Near Optimal Analysis of the Cube versus Cube Test

Dor Minzer Department of Mathematics, Massachusetts Institute of Technology,
Cambridge, USA. Supported by a Sloan Research Fellowship. Kai Zheng Department
of Mathematics, Massachusetts Institute of Technology, Cambridge, USA.
Supported by the NSF Graduate Research Fellowship DGE-1745302.

###### Abstract

The Cube versus Cube test is a variant of the well-known Plane versus Plane
test of Raz and Safra [10], in which to each $3$-dimensional affine subspace
$C$ of $\mathbb{F}_{q}^{n}$, a polynomial of degree at most $d$, $T(C)$, is
assigned in a somewhat locally consistent manner: taking two cubes
$C_{1},C_{2}$ that intersect in a plane uniformly at random, the probability
that $T(C_{1})$ and $T(C_{2})$ agree on $C_{1}\cap C_{2}$ is at least some
$\varepsilon$. An element of interest is the soundness threshold of this test,
i.e. the smallest value of $\varepsilon$, such that this amount of local
consistency implies a global structure; namely, that there is a global degree
$d$ function $g$ such that $g|_{C}\equiv T(C)$ for at least
$\Omega(\varepsilon)$ fraction of the cubes.

We show that the cube versus cube low degree test has soundness
$\operatorname{poly}(d)/q$. This result achieves the optimal dependence on $q$
for soundness in low degree testing and improves upon previous soundness
results of $\operatorname{poly}(d)/q^{1/2}$ due to Bhangale, Dinur and Navon
[4].

##  1 Introduction

###  1.1 Low degree testing

The Reed-Muller code is a basic building block of many results in Theoretical
Computer Science. One of the features that makes it so useful, particularly in
the area of Probabilistically Checkable Proofs [6, 2, 1], is that it admits
very efficient local tests. Most relevant to the current paper are the line
versus line [11], plane versus plane [10], and their $3$-dimensional analog,
the cube versus cube test [4]. In these settings, we have a finite field
$\mathbb{F}_{q}$ where $q$ is thought of as large, a degree parameter
$d\in\mathbb{N}$ much smaller than $q$, and we wish to encode a degree $d$
polynomial111Here and throughout, the notion of degree we refer to is the
total degree of a polynomial. $f\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$
using an encoding scheme that allows for local testing with $2$ queries.

The most basic example of these encoding schemes and tests is given by the
line versus line test. To define this, let $\mathcal{L}$ be the set of all
lines in $\mathbb{F}_{q}^{n}$. A polynomial
$f\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ is thus encoded by the
restrictions-to-lines table $T$ that assigns to each line $\ell\in\mathcal{L}$
the restriction of $f$ to $\ell$, i.e. $f_{|{\ell}}$. The test that
accompanies this encoding scheme is the line versus line test, described as
follows:

  1. 1.

Choose a point $x\in\mathbb{F}_{q}^{n}$ uniformly at random.

  2. 2.

Choose two lines $\ell_{1},\ell_{2}$ uniformly and independently conditioned
on $\ell_{1},\ell_{2}\ni x$.

  3. 3.

Read $T(\ell_{1})$ and $T(\ell_{2})$ and check that
$T(\ell_{1})|_{x}=T(\ell_{2})|_{x}$, i.e. that these two functions agree on
$x$.

It is clear that if $T$ is indeed a table of restrictions of a given
polynomial $f$ of degree at most $d$, then the above test passes with
probability $1$. The interesting question in this context is the converse:
suppose we have a table of functions $T$ that assigns to each line a function
of degree at most $d$, and suppose that the above test passes with probability
at least $s>0$; is it necessarily the case that this table of functions is
associated with some global degree $d$ polynomial?

Early works [6, 2, 1] were only able to analyze this test in the case that the
soundness parameter $s$ is close to $1$, namely the case in which we are
guaranteed that the table of functions $T$ passes the test with probability
close to $1$, say $s=1-\varepsilon$. In this case, it is typically shown that
any such table is close (in Hamming distance) to a table $T^{\prime}$ which is
an actual table of restrictions of some polynomial
$f^{\prime}\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ of degree at most $d$.

To strengthen the PCP theorem however (and more precisely, to improve on the
soundness guarantee), it became clear that one has to be able to analyze these
tests for as small of a soundness parameter $s$ as possible. Towards this end,
better analysis of the line versus line test was given [3] and other variants
of the line versus line test were considered. Most relevant to us are the
higher dimensional analogs of the tests, which are the plane versus plane test
[10] and the cube versus cube test [4]. In these tests, instead of encoding a
polynomial $f\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ using its table of
restrictions to lines, one encodes $f$ using its table of restrictions to
planes (in the case of the plane versus plane test) and to $3$-dimensional
affine subspaces (in the case of the cube versus cube test).

In the cube versus cube test, a polynomial
$f\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ is encoded using its cubes table
$T$, which assigns to each affine cube $C\subseteq\mathbb{F}_{q}^{n}$ a degree
at most $d$ polynomial $T(C)$ which is equal to the restriction $f_{|C}$. The
associated test with this encoding scheme is the cube versus cube test,
defined as:

  1. 1.

Choose an affine plane $P\subseteq\mathbb{F}_{q}^{n}$ uniformly at random.

  2. 2.

Choose two affine cubes $C_{1},C_{2}$ uniformly at random such that
$C_{1},C_{2}\supseteq P$.

  3. 3.

Read $T(C_{1})$ and $T(C_{2})$ from the cubes table and accept if and only if
the restrictions to $P$ satisfy $T(C_{1})|_{P}=T(C_{2})|_{P}$.

It is clear that a valid table of restrictions $T$ passes the test with
probability $1$, and again the interesting question is the converse. Namely,
suppose that a table of functions $T$ passes the above test with probability
$s>0$; is it necessarily the case that $T$ may be associated with some degree
$d$ polynomial?

More generally, one can consider tests where affine cubes and planes are
replaced with affine subspaces of dimensions $k$ and $\ell$ with $k>\ell$. For
such tests, the table $T$ contains supposed restrictions of $f$ to each
dimension $k$ affine subspace and performs the following dimension $\ell$
agreement test:

  1. 1.

Choose an affine dimension $\ell$ subspace $U\subseteq\mathbb{F}_{q}^{n}$
uniformly at random.

  2. 2.

Choose two affine dimension $k$ subspaces $V_{1},V_{2}$ uniformly at random
such that $V_{1},V_{2}\supseteq U$.

  3. 3.

Read $T(V_{1})$ and $T(V_{2})$ from the table and accept if and only if the
restrictions to $U$ satisfy $T(V_{1})|_{U}=T(V_{2})|_{U}$.

Indeed the cube versus cube test is the $k=3,\ell=2$ case, and the originally
studied Raz-Safra plane versus plane test is the $k=2,\ell=1$ case [10]. As
discussed earlier, the primary reason these tests were considered is that they
admit a very low soundness error. The soundness error of a test is defined to
be the smallest $s$ such that if the test passes with probability at least
$s$, then there exists a degree $d$ function $g$ such that $g_{V}=T(V)$ for an
$\Omega(s)$-fraction of the dimension $k$ affine subspaces $V$.

For the plane vs plane test, Raz and Safra [10] showed that
$s\geqslant\frac{n^{C}d^{C}}{q^{c}}$ for some absolute constants $c,C>0$, a
result that was sufficient in order to prove an improved PCP characterization
of NP (see for example [5]). An improved analysis of this test was given by
Moshkovitz and Raz [9], who showed that
$s\geqslant\operatorname{poly}(d)/q^{1/8}$. We note that the natural lower
bound on $s$ is $\Theta(1/q)$, since there are tables of assignments $T$ on
which the test passes with probability $\Theta(1/q)$ yet all degree $d$
functions agree with at most $o(1/q)$ of the entries of $T$. Indeed, take
$h=cq^{3}$ for some small absolute constant $c>0$, and pick affine subspaces
$W_{1},\ldots,W_{h}\subseteq\mathbb{F}_{q}^{n}$ of dimension $n-1$ uniformly
at random; for each $i=1,\ldots,h$, also pick a degree $d$ polynomial
$f_{i}\colon W_{i}\to\mathbb{F}_{q}$. To define the table $T$, for each plane
$P$ pick the first $i$ such that $P\subseteq W_{i}$ if such $i$ exists and
define $T(P)=f_{i}|_{P}$; otherwise, pick $T(P)$ randomly. It is not hard to
see that if we pick planes, $P_{1},P_{2}$, randomly that intersect in a line,
and $P_{1}\subseteq W_{i}$, then $P_{2}\subseteq W_{i}$ with probability
$\Omega(1/q)$. In this case, one can show that with constant probability both
$P_{1},P_{2}$ are assigned by $f_{i}$, and hence in expectation, the test
passes with probability $\Omega(1/q)$. It can be shown though, that as each
$f_{i}$ is chosen randomly and each $W_{i}$ contains $O(1/q^{3})$ of the
planes, that no degree $d$ polynomial agrees with $T$ on more than $o(1/q)$ of
the planes.

In light of this, an intriguing open question is what the soundness threshold
for the plane versus plane and other low degree tests is. For the Raz-Safra
plane versus plane test, the best known soundness analysis is still due to
Moshkovitz and Raz in [9]. Motivated by this question and more recently,
Bhangale, Dinur, and Livni Navon [4] suggested to study the cube versus cube
test, and managed to show that its soundness threshold is higher than that
known in the Raz-Safra test. Specifically, they showed that the soundness
threshold of the cube versus cube test is
$s\geqslant\operatorname{poly}(d)/q^{1/2}$, and ask whether it is the case
that the true soundness threshold of the cube versus cube test is linear in
$1/q$. Our main result confirms that this is indeed the case.

More precisely, the cube versus cube test studied in [4] is slightly different
than the one presented above. The test they consider is the generalized test
above with $k=3$ and $\ell=0$, meaning the tester picks a point
$x\in\mathbb{F}_{q}^{n}$, and then independently two cubes $C_{1},C_{2}$ that
contain $x$, and tests that $T(C_{1})$ and $T(C_{2})$ assign to $x$ the same
value. As shown in [4] though, the acceptance probability of the various cube
versus cube tests are all virtually the same for any cubes table $T$, so one
can essentially ignore this difference:

######  Theorem 1.1.

For a table $T$ giving restrictions to dimension $k\leqslant\frac{n}{2}$
subspaces, let $\alpha_{k\ell k}(T)$ denote the probability that $T$ passes
the dimension $\ell$ agreement test. Then for $0\leqslant r<r^{\prime}<k$,

$(1-o(1))\alpha_{krk}(T)\leqslant\alpha_{kr^{\prime}k}(T)\leqslant\alpha_{krk}(T)+(1+o(1))q^{-(k-2r^{\prime}+r+1)}.$

In this paper, we improve the analysis in [4] and show that the cube versus
cube test has soundness $\frac{10^{7}d^{6}}{q}$. As mentioned, we think of $q$
as large, and $d$ as much smaller than $q$, but still larger than some
absolute constant. It suffices to assume that $d<\frac{q^{1/9}}{11}$. Our main
theorem is as follows:

######  Theorem 1.2.

Suppose $T$ is a cubes table such that for each affine cube
$C\subseteq\mathbb{F}_{q}^{n}$, $T(C)$ is a degree $d$ polynomial over $C$. If
$T$ passes the cube versus cube test with probability
$\varepsilon\geqslant\frac{10^{7}d^{6}}{q}$, then there exists a degree $d$
polynomial, $g$, such that $g|_{C}=T(C)$ for an $\Omega(\varepsilon)$-fraction
of all affine cubes $C$.

We note that while Theorem 1.1 implies our soundness bound also holds for the
the cube versus cube test with point intersection considered in [4], the same
is not true the other way around. Indeed, from Theorem 1.1 one cannot obtain
any lower bound on $\alpha_{303}$ from $\alpha_{323}$. Thus, prior to this
work even an $O(1/q^{2})$ soundness result was not known for the cube versus
cube test with dimension $2$ intersection.

We also remark that we made no attempt to optimize the dependence on $d$, and
that as noted earlier the main point of this result is that the dependency on
the field size $q$ is optimal.

###  1.2 Proof Overview

Our proof strategy relies heavily on ideas from [4], but to get the optimal
soundness threshold our argument uses more refined expansion as well as
sampling arguments.

#### High level description.

Suppose that the cube versus cube test passes with probability
$\varepsilon\geqslant\frac{10^{7}d^{6}}{q}$. For a point
$x\in\mathbb{F}_{q}^{n}$ and a value $\sigma\in\mathbb{F}_{q}$, define

$\mathcal{C}_{x}=\\{C\subseteq\mathbb{F}_{q}^{n}~{}|~{}C\text{ is a
$3$-dimensional cube, $x\in
C$}\\},\qquad\mathcal{C}_{x,\sigma}=\\{C\subseteq\mathbb{F}_{q}^{n}~{}|~{}C\in\mathcal{C}_{x}\text{
and $T(C)_{|x}=\sigma$}\\}.$

In words, $\mathcal{C}_{x,\sigma}$ is the set of cubes containing $x$ on which
$T$ gives the point $x$ the value $\sigma$. We may view
$\mathcal{C}_{x,\sigma}$ as a partition of $\mathcal{C}_{x}$ according to the
value given to $x$. In [4], the authors show that this partition cannot
consist of only parts that are small, otherwise the contribution to the
acceptance probability of the test of these cube would be small. Our argument
observes further properties of these partitions. At a high level, we show that
if we take $x$ and $y$ randomly and consider the partition
$\mathcal{C}_{x,\sigma}\cap\mathcal{C}_{y,\tau}$ of the cubes containing both
$x$ and $y$, then this partition cannot consist only of small parts. This
suggests that the partitions $\mathcal{C}_{x,\sigma}$ and
$\mathcal{C}_{y,\tau}$ are correlated. In fact, in a sense we are able to show
that (in the part that contributes to the acceptance probability of the test),
they are in $1$ to $1$ correspondence in the sense that for each $\sigma$ we
can identify a single $\tau$ so that
$\mathcal{C}_{x,\sigma}\cap\mathcal{C}_{y}$ and
$\mathcal{C}_{x}\cap\mathcal{C}_{y,\tau}$ are roughly the same set. We then
show that for a sufficiently large fraction of $x$’s and $\sigma$, there is a
global function agreeing with $T$ on almost all of $\mathcal{C}_{x,\sigma}$.
The above correlation between partitions then allows us to argue that the
global functions of $x$ and $y$ agree provided the parts
$\mathcal{C}_{x,\sigma}$ and $\mathcal{C}_{y,\tau}$ are matching according to
the above described $1$-to-$1$ correspondence. Using this, we are able to show
that for some $x$, the global function on $\mathcal{C}_{x,\sigma}$ agrees with
sufficiently many global functions on $\mathcal{C}_{y,\tau}$ for other $y$’s,
and enough so that this already gives agreement $\Omega(\varepsilon)$ with the
table $T$. A more detailed overview follows.

#### A more detailed description.

Consider the following way of generating a pair of cubes intersecting in a
plane: sample $x,y\in\mathbb{F}_{q}^{n}$, sample a plane $P$ containing both
$x$ and $y$, and sample $C_{1},C_{2}$ cubes containing $P$. We note that the
points $x$ and $y$ partition the set of cubes $C$ containing them into $q^{2}$
sets:

$\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}:=\mathcal{C}_{x,\sigma}\cap\mathcal{C}_{y,\tau},\qquad\text{for
all }\sigma,\tau\in\mathbb{F}_{q}.$

We further note that for the test on $C_{1},C_{2}$ to pass, they both must
belong to the same part in the partition, i.e. they must both be in
$C_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$ for some
$\sigma,\tau$. Thus, fixing $x$ and $y$, this shows that the probability of
the test passing (conditioned on that) is related to the expansion properties
of the partition $\left(\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)_{\sigma,\tau\in\mathbb{F}_{q}}$ in the affine
Grassmann graph. We formally define this graph in the next section, but
informally in our context this graph contains all of the cubes $C$ containing
both $x$ and $y$, and two cubes are adjacent if they intersect in a plane.
Thus, we get that the probability that the test passes is at most

$\sum\limits_{\sigma,\tau}\Pr_{C_{1}\cap C_{2}\supseteq P\ni
x,y}[C_{1},C_{2}\in\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}]=\sum\limits_{\sigma,\tau}\mu_{x,y}\left(\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\left(1-\Phi\left(\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\right).$

Here, $\mu_{x,y}\left(\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)$ is the relative measure of
$\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$ among all
cubes containing $x,y$ and
$\Phi_{xy}\left(\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)$ is the edge expansion of
$\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$ in the
above defined Grassmann graph. Using the spectral properties of the Grassmann
graph, we show that this sum is at most
$O\left(\frac{1}{q}\right)+\sum\limits_{\sigma,\tau}\mu_{x,y}\left(\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}$, and thereby conclude (using the fact that
the probability the cube versus cube test passes with probability at least
$\varepsilon$) that

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{\sigma,\tau\in\mathbb{F}_{q}}\mu_{x,y}\left({\mathcal{C}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\right]\geqslant\varepsilon.$ (1)

Intuitively, this says that the partitions given by
$(C_{x,\sigma})_{\sigma\in\mathbb{F}_{q}}$ and
$(C_{y,\tau})_{\tau\in\mathbb{F}_{q}}$ are somewhat correlated with each
other. To make use of this correlation, we must pass first to subsets of
$C_{x,\sigma}$ on which we already know that we have some global structure.

For that, we use ideas from [4]. Specifically, we identify and consider the
pairs $(x,\sigma)$ that contribute almost all of the acceptance probability of
the test, and show that for each such $(x,\sigma)$ one may find a global
degree $d$ function $g_{x,\sigma}$ that agrees with $T$ on almost all of
$\mathcal{C}_{x,\sigma}$. Thus, letting $\mathcal{F}_{x,\sigma}$ be the set of
cubes containing $x$ on which $T$ and $g_{x,\sigma}$ agree, we get that
$\mathcal{F}_{x,\sigma}\subseteq\mathcal{C}_{x,\sigma}$ are very close to each
other. This motivates us to define
$\mathcal{F}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}=\mathcal{F}_{x,\sigma}\cap\mathcal{F}_{y,\tau}$. Since
$\mathcal{F}_{x,\sigma}$ and $\mathcal{C}_{x,\sigma}$ are very close to each
other, one expects (1) to imply something similar about the partial partition
$\mathcal{F}_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$, and we
show that this in indeed the case (though not quite as obviously as one may
initially expect). Namely, we show that (1) implies that

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{\sigma,\tau\in\mathbb{F}_{q}}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\right]\geqslant\Omega(\varepsilon).$ (2)

We note now that while the sum is over $q^{2}$ terms, for each $\sigma$ there
exists at most a single $\tau$ for which the corresponding summand is non-
zero. Indeed, fixing $\sigma$ means that we look at $\mathcal{F}_{x,\sigma}$
on which we have some global degree $d$ function $g_{x,\sigma}$, and hence the
only viable option for $\tau$ is $\tau=g_{x,\sigma}(y)$. Moreover, by
averaging considerations it turns out that we can have at most
$O(1/\varepsilon)$ many $\sigma$’s for which the pair $(x,\sigma)$ contributes
to the above sum. Hence we may find $x$ and $\sigma$ such that

$\mathop{\mathbb{E}}_{y}\left[\mu_{x,y}\left(\mathcal{F}_{\left\\{\begin{subarray}{c}x,\sigma\\\
y,g_{x,\sigma}(y)\end{subarray}\right\\}}\right)^{2}\right]\geqslant\Omega(\varepsilon^{2}).$

Let $\eta=\mu_{x}(\mathcal{F}_{x,\sigma})$. Sampling $y\in\mathbb{F}_{q}^{n}$
uniformly, it is clear that the expected value of
$\mu_{x,y}(\mathcal{F}_{x,\sigma}\cap\mathcal{C}_{y})$ is $\eta$, and in fact
one can show that a relatively strong concentration holds. This concentration
is strong enough to show that the fraction of $y$’s for which
$\mu_{x,y}(\mathcal{F}_{x,\sigma}\cap\mathcal{C}_{y})\geqslant 2\eta$ is very
small – small enough so that discarding them from the above inequality only
incurs a small loss. Furthermore, we can also neglect $y$’s such that
$\mu_{x,y}\left(\mathcal{F}_{\left\\{\begin{subarray}{c}x,\sigma\\\
y,g_{x,\sigma}(y)\end{subarray}\right\\}}\right)\leqslant c\varepsilon$ for
some sufficiently small absolute constant $c$, so altogether we get that

$\mathop{\mathbb{E}}_{y}\left[\mu_{x,y}\left(\mathcal{F}_{\left\\{\begin{subarray}{c}x,\sigma\\\
y,g_{x,\sigma}(y)\end{subarray}\right\\}}\right)^{2}\mathbbm{1}_{\left\\{c\varepsilon\leqslant\mu_{x,y}\left(\mathcal{F}_{\left\\{\begin{subarray}{c}x,\sigma\\\
y,g_{x,\sigma}(y)\end{subarray}\right\\}}\right)\leqslant
2\eta\right\\}}\right]\geqslant\Omega(\varepsilon^{2}).$

Doing a dyadic partitioning, we get that there is a $t\geqslant c\varepsilon$
such that

$t^{2}p_{t}\geqslant\Omega\left(\frac{\varepsilon^{2}}{\log(1/\varepsilon)}\right),\qquad\text{
where
}~{}~{}p_{t}=\Pr_{y}\left[\mu_{x,y}\left(\mathcal{F}_{\left\\{\begin{subarray}{c}x,\sigma\\\
y,g_{x,\sigma}(y)\end{subarray}\right\\}}\right)\in[t,2t)\right].$

Taking $Y$ to be the set of $y$’s such that
$\mu_{x,y}\left(\mathcal{F}_{\left\\{\begin{subarray}{c}x,\sigma\\\
y,g_{x,\sigma}(y)\end{subarray}\right\\}}\right)\in[t,2t)$, we show
$g_{x,\sigma}\equiv g_{y,\tau}$ for all $y\in Y$. Hence, $g_{x,\sigma}$ agrees
with the table $T$ on all of the cubes in $\mathcal{F}=\cup_{y\in
Y}\mathcal{F}_{y,\tau}$, and to complete the proof it suffices to show that
$\mu(\mathcal{F})\geqslant\Omega(\varepsilon)$. This is done by applying a
standard spectral argument and using the fact that
$\mu(Y)=p_{t}\geqslant\Omega\left(\frac{\varepsilon^{2}}{t^{2}\log(1/\varepsilon)}\right)$.

##  2 Preliminaries

###  2.1 Notations

Throughout the paper, we let $q$ denote the field size, $n$ denote the
dimension, and let $\mathcal{C}$ be the set of all _affine_ cubes in
$\mathbb{F}_{q}^{n}$. An affine cube is a linear $3$-dimensional subspace with
all points translated by some $x_{0}\in\mathbb{F}_{q}^{n}$. We henceforth
refer to affine cubes as simply cubes.

For points $x,y\in\mathbb{F}_{q}^{n}$, we denote

$\mathcal{C}_{x}=\\{C\in\mathcal{C}\;|\;x\in
C\\},\qquad\qquad\mathcal{C}_{x,y}=\mathcal{C}_{x}\cap\mathcal{C}_{y}.$

We also let $\mathcal{L}$ denote the set of all lines in $\mathbb{F}_{q}^{n}$
and likewise let $\mathcal{L}_{x}$ denote the set of all lines containing $x$.
We let $\mu$ be the uniform distribution over $\mathcal{C}$, $\mu_{x}$ be the
uniform measure over $\mathcal{C}_{x}$ and $\mu_{x,y}$ be the uniform measure
over $\mathcal{C}_{x,y}$. Abusing notation, we will sometimes use $\mu$ to
also denote the uniform measure over $\mathbb{F}_{q}^{n}$, and it will be
clear from context if we are referring to the uniform measure over
$\mathcal{C}$ or over $\mathbb{F}_{q}^{n}$.

For two functions $f$ and $g$, we say that $f$ is $\delta$-close to $g$ if
they differ on at most a $\delta$ fraction of their inputs. That is,
$\Pr_{x}[f(x)\neq g(x)]\leqslant\delta$, where the space of inputs $x$ is the
domain of $f$ and $g$. We will also write
$f\,{\stackrel{{\scriptstyle{\delta}}}{{\approx}}}\,g$ to denote that $f$ is
$\delta$-close to $g$.

Finally, we will have a cubes table $T$ which assigns to each cube
$C\in\mathcal{C}$ a degree $d$ polynomial $T(C)\colon C\to\mathbb{F}_{q}$.
Given such table, we define

$\mathcal{C}_{x,\sigma}=\\{C\in\mathcal{C}_{x}\;|\;T(C)(x)=\sigma\\},\qquad\qquad\mathcal{C}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}=\mathcal{C}_{x,\sigma}\cap\mathcal{C}_{y,\tau},$

and we denote for convenience $\varepsilon(T)=\alpha_{323}(T)$, i.e. the
probability that the cube versus cube test on $T$ passes.

Henceforth, we suppose that $T$ is a cubes table that passes the cube versus
cube test with probability
$\varepsilon(T)=\varepsilon\geqslant\frac{10^{7}d^{6}}{q}$.

###  2.2 Grassman and Affine Grassman Graphs

In this section we introduce the Grassman and Affine Grassman graphs. At times
it will be helpful to think about the cube versus cube test in terms of these
graphs and use known results about expansion in these graphs.

######  Definition 1.

The _Grassman graph_ $\operatorname{Gras}(k,\ell)$ is the graph with vertex
set consisting of all $k$-dimensional linear subspaces and edges between all
pairs of subspaces $(U_{1},U_{2})$ satisfying $\dim(U_{1}\cap U_{2})=\ell$.

######  Definition 2.

The _Affine Grassman graph_ $\operatorname{AffGras}(k,\ell)$, is the graph
with vertex set consisting of all $k$-dimensional affine subspaces and edges
between all pairs of subspaces $(V_{1},V_{2})$ satisfying $\dim(V_{1}\cap
V_{2})=\ell$.

If we let $G=\operatorname{AffGras}(3,2)$ we can think of the cube versus cube
test as choosing a random edge $(C_{1},C_{2})\in E$ in the graph and checking
if $T(C_{1})$ and $T(C_{2})$ agree on their intersection. Thus we may let $S$
be the set of edges $(C_{1},C_{2})\in E$ where $T(C_{1})|_{C_{1}\cap
C_{2}}=T(C_{2})|_{C_{1}\cap C_{2}}$. Since $\varepsilon$ is the exact pass
probability of the test, we have

$\Pr\left[(C_{1},C_{2})\in S\right]=\varepsilon.$

If we fix a point $x$ and condition on $C_{1},C_{2},$ and $C_{1}\cap C_{2}$
containing $x$, then notice that with the remaining degrees of freedom,
choosing $C_{1}$ and $C_{2}$ corresponds to choosing two linear cubes that
intersect in a plane. Equivalently, this is choosing a random edge from the
induced subgraph of $G$ on $\mathcal{C}_{x}$, which we denote by $G_{x}$.
Notice that $G_{x}$ is isomorphic to $\operatorname{Gras}(3,2)$. If we further
condition on $C_{1},C_{2},$ and $C_{1}\cap C_{2}$ containing two points $x$
and $y$, then the random choice of $C_{1}$ and $C_{2}$ is equivalent to
choosing two linear planes that intersect in a line, or a random edge in
$G_{xy}$ which is isomorphic to $\operatorname{Gras}(2,1)$.

If we fix a point $x$ and condition on $C_{1}\in\mathcal{C}_{x,\sigma}$, then
notice that the test can only pass if $C_{2}\in\mathcal{C}_{x,\sigma}$ as
well. This is where expansion in the Grassman graphs plays a role. Conditioned
on $C_{1}\in\mathcal{C}_{x,\sigma}$, and $C_{2}$ intersecting $C_{1}$ in a
plane containing $x$, the probability that $C_{2}\in\mathcal{C}_{x,\sigma}$ is
precisely $1-\Phi_{x}(\mathcal{C}_{x,\sigma})$, where $\Phi_{x}$ denotes
expansion in $G_{x}$. Likewise, if we fix two points $x,y$, and condition on
$C_{1}\in{\mathcal{C}}_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$,
then we can lower bound the pass probability by
$1-\Phi_{xy}\left({\mathcal{C}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)$, which is the probability that
$C_{2}\in{\mathcal{C}}_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$.
The following fact about expansion in $\operatorname{Gras}(k,k-1)$ allows us
to freely convert these quantities to measures.

######  Lemma 2.1.

Let $A$ be a set of $k$-dimensional subspaces over $\mathbb{F}_{q}^{n}$ and
let $\Phi(A)$ denote the expansion of $A$ in $\operatorname{Gras}(k,k-1)$.
Then

$\mu(A)-\frac{1}{q^{n-k+1}-2}\leqslant 1-\Phi(A)\leqslant\mu(A)+\frac{1}{q}.$

###### Proof.

Let $F$ denote the indicator function for $A$. Thus $F$ is a function that
takes $k$-dimensional subspaces as input and is $1$ on those in $A$ and $0$
otherwise. Let $T$ denote the adjacency operator of
$\operatorname{Gras}(k,k-1)$. By [7, Theorem 9.4.1], the eigenvalues of $T$
are

$\lambda_{r}=\frac{-(q^{k}-1)+q^{r}(q^{k-r}-1)(q^{n-k-r+1}-1)}{(q^{k}-1)(q^{n-k+1}-2)},$

for $r=0,1\ldots,k$. It is easily seen that for $r=0$ we get an eigenvalue of
$1$, and for any other $r$ the corresponding eigenvalue is at most $q^{-r}$.
Thus, we may write $F=F_{0}+F_{1}+\ldots+F_{k}$ where $F_{r}$ is an
eigenvector of $T$ of eigenvalue $\lambda_{r}$, where $F_{0}\equiv\mu(S)$, and
so

$1-\Phi(A)=\frac{\langle
F,TF\rangle}{\mu(S)}=\frac{1}{\mu(A)}\left(\mu(A)^{2}+\sum_{r\geqslant
1}\lambda_{r}\|F_{r}\|_{2}^{2}\right)\leqslant\mu(A)+\frac{1}{q}\frac{\sum_{r\geqslant
1}\|F_{r}\|_{2}^{2}}{\mu(A)}\leqslant\mu(A)+\frac{1}{q},$

where we use the fact that $\sum_{r\geqslant
1}\|F_{r}\|_{2}^{2}\leqslant\sum_{r\geqslant
0}\|F_{r}\|_{2}^{2}=\|F\|_{2}^{2}=\mu(A)$. For the lower bound, we note that
the eigenvalues $\lambda_{r}$ are nonnegative for $r<k$, while
$\lambda_{k}=\frac{-1}{q^{n-k+1}-2}$. ∎

###  2.3 Bipartite Inclusion Graphs

Next, we review some results regarding sampling edges in bipartite inclusion
graphs that we will use later. These results were used in the context of
direct product testing in [8] and to analyze the cube versus cube test in [4].

Let $G(A,B)$ denote the bipartite inclusion graph with vertices $A\cup B$ and
edges $E$, where $A$ consists of subspaces of some dimension $i$ (possibly
$i=0$ if $A$ is a set of points) in $\mathbb{F}_{q}^{m}$, $B$ consists of
subspaces of some dimension $j>i$ in $\mathbb{F}_{q}^{m}$, and $(a,b)\in E$ if
$a\subseteq b$. Also let $\lambda(G)$ denote the second largest singular value
of a graph $G$ and for any vertex $v$ in the graph, let $N(v)$ denote its
neighborhood. It is known that such graphs satisfy the following sampling
property:

######  Lemma 2.2.

Let $G=G(A,B)$ be a bi-regular bipartite graph. For every subset
$B^{\prime}\subset B$ of measure $\mu>0$ and every $E^{\prime}\subset E$

$\left|\Pr_{\begin{subarray}{c}b\in B^{\prime}\\\ a\in
N(b)\end{subarray}}[(a,b)\in E^{\prime}]-\Pr_{\begin{subarray}{c}a\in A\\\
b\in N(a)\cap B^{\prime}\end{subarray}}[(a,b)\in
E^{\prime}]\right|\leqslant\frac{\lambda(G)}{\sqrt{\mu}}.$

For completeness, we list the singular values of the bipartite inclusion
graphs that we will use.

######  Lemma 2.3.

For $m\geqslant 6$, the bipartite inclusion graphs for subspaces of
$\mathbb{F}_{q}^{m}$ have the following second singular values:

  1. 1.

For $G_{1}=G(\mathcal{L}\setminus\mathcal{L}_{x},\mathcal{C}_{x})$,
$\lambda(G_{1})\approx\frac{1}{\sqrt{q}}$.

  2. 2.

For $G_{2}=G(\mathcal{L}_{x},\mathcal{C}_{x})$,
$\lambda(G_{2})\approx\frac{1}{q}$.

  3. 3.

For $G_{3}=G(\mathbb{F}_{q}^{m}\setminus\\{x\\},\mathcal{C}_{x})$,
$\lambda(G_{3})\approx\frac{1}{q}$.

  4. 4.

For $G_{4}=G(\mathbb{F}_{q}^{m}\setminus\ell,\mathcal{C}_{\ell})$,
$\lambda(G_{4})\approx\frac{1}{\sqrt{q}}$.

  5. 5.

For $G_{5}=G(\mathbb{F}_{q}^{m},\mathcal{C})$,
$\lambda(G_{5})\approx\frac{1}{q^{3/2}}$.

  6. 6.

For $G_{6}=G(\mathbb{F}_{q}^{3},\mathcal{L})$,
$\lambda(G_{6})\approx\frac{1}{\sqrt{q}}$.

We use $\approx$ to denote equality up to a multiplicative factor of $1+o(1)$,
where $o(1)$ is a function of $q$ that approaches $0$ as
$q\xrightarrow[]{}\infty$.

We refer the reader to the appendix of [4] for the proofs of Lemmas 2.2 and
2.3.

##  3 The Main Argument

###  3.1 Local Agreement with Degree d polynomials

In this section we show how to construct local degree $d$ polynomials $g_{x}$,
that agree with an $\Omega(\varepsilon)$ fraction of the cubes in $C_{x}$. The
strategy is similar to that of [4]. The following notion of excellent
$(x,\sigma)$ pairs will be relevant to our analysis. This notion was
introduced in an analysis of direct product tests [8] and also used in [4].

Recall that $\varepsilon\geqslant\frac{10^{7}d^{6}}{q}$ is the exact pass
probability of the test. Let $\gamma$ be a small constant factor times
$d^{-3}$, say $\gamma=\frac{1}{1000d^{3}}$.

######  Definition 3.

Call a pair $(x,\sigma)$ excellent if the following are true:

  * •

$\mu_{x}(\mathcal{C}_{x,\sigma})\geqslant\varepsilon/5$

  * •

For $C_{1}\in C_{x,\sigma}$ chosen uniformly at random, a random line
$\ell\subset C_{1}$ containing $x$, and $C_{2}\in\mathcal{C}_{x,\sigma}$
chosen uniformly conditioned on containing $\ell$, we have that

$\Pr_{C_{1},\ell,C_{2}}[T(C_{1})|_{\ell}\neq
T(C_{2})|_{\ell}]\leqslant\gamma.$

Henceforth we let $X$ denote the set of all excellent pairs $(x,\sigma)$.
Notice that if we let

$p_{x,\sigma}=\Pr_{\begin{subarray}{c}C_{1}\in\mathcal{C}_{x,\sigma},\\\
C_{2}\cap C_{1}=\ell\ni
x\end{subarray}}[T(C_{1})(x)=T(C_{2})(x),\;T(C_{1})|_{\ell}\neq
T(C_{1})|_{\ell}],$

then the second condition holds if
$p_{x,\sigma}\leqslant\gamma\left(1-\Phi_{x}(\mathcal{C}_{x,\sigma})\right)$,
since

$\Pr_{C_{1},\ell,C_{2}}[T(C_{1})|_{\ell}\neq
T(C_{2})|_{\ell}]=\frac{p_{x,\sigma}}{1-\Phi_{x}(\mathcal{C}_{x,\sigma})}$

where the probability is with respect to the distribution in the second point
of Definition 3, and the inequality is due to Lemma 2.1.

This leads to the following observation:

######  Lemma 3.1.

If $(x,\sigma)\notin X$, then either
$\mu_{x}(\mathcal{C}_{x,\sigma})<\varepsilon/5$ or
$p_{x,\sigma}>\gamma\left(1-\Phi_{x}(\mathcal{C}_{x,\sigma})\right)$.

The main result of this section shows that for an excellent $(x,\sigma)$,
there exists a degree $d$ polynomial $g$ that agrees with almost all of the
cubes in $\mathcal{C}_{x,\sigma}$. The same result has been proved in [4]
under a stronger assumption on the largeness of $\varepsilon$. We begin by
defining the function $f_{x,\sigma}$ by plurality over all cubes in
$\mathcal{C}_{x,\sigma}$.

######  Definition 4.

For a pair $(x,\sigma)$, define
$f_{x,\sigma}:\mathbb{F}_{q}^{n}\xrightarrow[]{}\mathbb{F}_{q}$ so that
$f_{x,\sigma}(y)$ is the most common value of $T(C)(y)$ over cubes
$C\in\mathcal{C}_{x,\sigma}$ containing $y$. If there are no such cubes,
assign the value arbitrarily.

Since $(x,\sigma)$ is excellent, it follows immediately that $f_{x,\sigma}$
usually agrees with $T$ on points in cubes $C\in C_{x,\sigma}$.

######  Lemma 3.2.

For $f_{x,\sigma}$ as defined above,

$\Pr_{C\in\mathcal{C}_{x,\sigma},y\in C}[f_{x,\sigma}(y)=T(C)(y)]\geqslant
1-\gamma.$

###### Proof.

Let

$\gamma_{y}=\Pr_{C_{1},C_{2}\in\mathcal{C}_{y}\cap\mathcal{C}_{x,\sigma}}[T(C_{1})(y)\neq
T(C_{2})(y)].$

Since $f_{x,\sigma}(y)$ is the most common value of $T(C)(y)$ over cubes
$C\in\mathcal{C}_{y}\cap\mathcal{C}_{x,\sigma}$. We can write,

$1-\gamma_{y}=\sum_{\alpha\in\mathbb{F}_{q}}\Pr_{C\in\mathcal{C}_{y}\cap\mathcal{C}_{x,\sigma}}[T(C)(y)=\alpha]^{2}\leqslant\Pr_{C\in\mathcal{C}_{y}\cap\mathcal{C}_{x,\sigma}}[T(C)(y)=f_{x,\sigma}(y)].$

Since this inequality holds for any $y$, it also holds under expectation over
any distribution of $y$. Take the distribution as: choose
$C\in\mathcal{C}_{x,\sigma}$ uniformly, and then $y\in C$ uniformly different
from $x$ (or equivalently, a uniformly random line $\ell\subseteq C$
containing $x$ and then $y\in\ell$ uniformly different from $x$). Then,
denoting by $\ell_{x,y}$ the line that passes through $x$ and $y$, we get that

$\displaystyle\Pr_{C\in\mathcal{C}_{x,\sigma},y\in
C}[T(C)(y)=f_{x,\sigma}(y)]\geqslant\mathbb{E}_{C,y}[1-\gamma_{y}]$
$\displaystyle=\Pr_{\begin{subarray}{c}C_{1}\in\mathcal{C}_{x,\sigma},y\in
C_{1}\\\
C_{2}\in\mathcal{C}_{x,\sigma}\cap\mathcal{C}_{y}\end{subarray}}[T(C_{1})(y)=T(C_{2})(y)]$
$\displaystyle\geqslant\Pr_{\begin{subarray}{c}C_{1}\in\mathcal{C}_{x,\sigma},y\in
C_{1}\\\
C_{2}\in\mathcal{C}_{x,\sigma}\cap\mathcal{C}_{y}\end{subarray}}[T(C_{1})|_{\ell_{x,y}}=T(C_{2})|_{\ell_{x,y}}]$
$\displaystyle\geqslant 1-\gamma,$

where the last inequality is due to the assumption that $(x,\sigma)$ is
excellent. ∎

Finally, we show that $f_{x,\sigma}$ is close to a degree $d$ polynomial by
using the following robust characterization of low degree polynomials due to
Rubinfeld and Sudan.

######  Theorem 3.1.

_[11]_ Let $f:\mathbb{F}_{q}^{m}\xrightarrow[]{}\mathbb{F}_{q}$, and let
$N_{y,h}=\\{y+i(h-y)\;|\;i\in[d+1]\\}$. If,

$\Pr_{y,h\in\mathbb{F}_{q}^{n}}[\;\exists p\text{ such that
}p|_{N_{y,h}}=f|_{N_{y,h}}]\geqslant 1-\delta,$

for $\delta\leqslant\frac{1}{2(d+2)^{2}}$, then $f$ is $2\delta$-close to some
degree $d$ polynomial $g$.

######  Lemma 3.3.

If
$\Pr_{C\in\mathcal{C}_{x}}[T(C)\,{\stackrel{{\scriptstyle{2\gamma}}}{{\approx}}}\,f|_{C}]\geqslant\frac{\varepsilon}{10}$,
then $f$ is $4d\gamma$ close to some degree $d$ polynomial $g$.

###### Proof.

Let
$\mathcal{F}=\\{C\in\mathcal{C}_{x}\;|\;T(C)\,{\stackrel{{\scriptstyle{2\gamma}}}{{\approx}}}\,f|_{C}\\}$.
Fix $C\in\mathcal{F}$. We first show that for almost all lines in $C$, $f$
agrees with the degree $d$ function $T(C)$ on almost all points on the line.
We do this using Lemma 2.2 and the spectral properties of $G_{C}=G(A\cup B,E)$
– the bipartite inclusion graph where $A$ is the set of all points in $C$, $B$
is the set of all affine lines in $C$, and $E$ is the set of all point-line
pairs $(x,\ell)$ such that $x\in\ell$. This graph is the same as $G_{5}$ in
Lemma 2.3, with $\mathbb{F}_{q}^{3}\cong\mathcal{C}$, so
$\lambda(G_{C})\leqslant\frac{2}{\sqrt{q}}$.

Let $A^{\prime}=\\{y\in A\;|\;T(C)(y)\neq f(y)\\}$, and let
$B^{\prime}=\\{\ell\in B\;|\;|N(\ell)\cap A^{\prime}|\geqslant
3\gamma|N(\ell)|\\}$, where $N(\ell)$ consists of all of the points contained
in $\ell$. In other words, $A$ is the set of points in $C$ where $f$ disagrees
with $T(C)$, and $B^{\prime}$ is the set of lines where $f$ and $T(C)$
disagree on at least $3\gamma$ of the points. Then, by Lemma 2.2

$\left|\Pr_{\ell\in B^{\prime},y\in N(\ell)}[y\in A^{\prime}]-\Pr_{y\in A,y\in
C\cap B^{\prime}}[y\in
A^{\prime}]\right|\leqslant\frac{\lambda(G_{C})}{\sqrt{\frac{|B^{\prime}|}{|B|}}}.$

By construction, $\Pr_{\ell\in B^{\prime},y\in N(\ell)}[y\in
A^{\prime}]\geqslant 3\gamma$ and by assumption

$\Pr_{y\in A,C\in N(y)\cap B^{\prime}}[y\in A^{\prime}]\leqslant\Pr_{y\in
A}[y\in A^{\prime}]\leqslant 2\gamma,$

so
$|B^{\prime}|\leqslant\left(\frac{\lambda(G_{C})}{\gamma}\right)^{2}|B|\leqslant\gamma|B|$.
Thus, for any cube $C\in\mathcal{F}$, $f$ is $3\gamma$-close to a degree $d$
polynomial on at least a $1-\gamma$ fraction of the lines in $C$. We next show
that $\mathcal{F}$ contains enough cubes to cover nearly all lines.

Consider the bipartite inclusion graphs
$G_{1}=G(\mathcal{L}\setminus\mathcal{L}_{x},\mathcal{C}_{x})$ and
$G_{2}=G(\mathcal{L}_{x},\mathcal{C}_{x})$, which have second singular values
at most $\frac{1}{\sqrt{q}}$ and $\frac{1}{q}$ respectively by Lemma 2.3. Let
$E^{\prime}$ denote the set of line-cube pairs $(\ell,C)$ such that
$\ell\subseteq C$ and
$T(C)|_{\ell}\,{\stackrel{{\scriptstyle{3\gamma}}}{{\approx}}}\,f|_{\ell}$.
Recall that $|\mathcal{F}|/|\mathcal{C}_{x}|\geqslant\varepsilon/10$, so by
Lemma 2.2 on $G_{1}$,

$\left|\Pr_{\ell,C\in N(\ell)\cap F}[(\ell,C)\in
E^{\prime}\;|\;\ell\notin\mathcal{L}_{x}]-\Pr_{C\in F,\ell\in C}[(\ell,C)\in
E^{\prime}\;|\;\ell\notin\mathcal{L}_{x}]\right|\leqslant\frac{1/\sqrt{q}}{\sqrt{\varepsilon/10}}=\sqrt{\frac{10}{q\varepsilon}}\leqslant\gamma.$

By Lemma 2.2 on $G_{2}$,

$\left|\Pr_{\ell,C\in N(\ell)\cap F}[(\ell,C)\in
E^{\prime}\;|\;\ell\in\mathcal{L}_{x}]-\Pr_{C\in F,\ell\in C}[(\ell,C)\in
E^{\prime}\;|\;\ell\in\mathcal{L}_{x}]\right|\leqslant\frac{1/q}{\sqrt{\varepsilon/10}}=\sqrt{\frac{10}{q^{2}\varepsilon}}\leqslant\gamma.$

We showed previously that for every $C\in\mathcal{F}$, $\Pr_{\ell\in
C}[(\ell,C)\in E^{\prime}]\geqslant 1-\gamma$. Let
$p=|\mathcal{L}_{x}|/|\mathcal{L}|$ be the probability that a randomly chosen
line contains $x$. Then,

$\displaystyle\Pr_{\ell}[\exists C\text{ s.t. }(\ell,C)\in E^{\prime}]$
$\displaystyle\geqslant\Pr_{\ell,C\in N(\ell)\cap F}[(\ell,C)\in E^{\prime}]$
$\displaystyle=(1-p)\Pr_{\ell,C\in N(\ell)\cap F}[(\ell,C)\in
E^{\prime}\;|\;\ell\notin\mathcal{L}_{x}]+p\Pr_{\ell,C\in N(\ell)\cap
F}[(\ell,C)\in E^{\prime}\;|\;\ell\in\mathcal{L}_{x}]$
$\displaystyle\geqslant(1-p)\Pr_{C\in F,\ell\in C}[(\ell,C)\in
E^{\prime}\;|\;\ell\notin\mathcal{L}_{x}]+p\Pr_{C\in F,\ell\in C}[(\ell,C)\in
E^{\prime}\;|\;\ell\in\mathcal{L}_{x}]-\gamma$ $\displaystyle=\Pr_{\ell\in
C}[(\ell,C)\in E^{\prime}]-\gamma$ $\displaystyle\geqslant 1-2\gamma.$

Therefore, $f$ is $3\gamma$-close to a degree $d$ polynomial on at least
$1-2\gamma$ of the lines in $\mathcal{L}$. This allows us to bound the
probability that, for a randomly chosen neighborhood, $f$ is equal to a low
degree polynomial on that neighborhood. To do this, we view picking a random
neighborhood as randomly picking a line $\ell\in\mathcal{L}$, and then
$y,h\in\ell$ uniformly at random.

$\displaystyle\Pr_{y,h\in\mathbb{F}_{q}^{n}}[\exists C\text{ s.t.
}f|_{N_{y,h}}=T(C)|_{N_{y,h}}]$ $\displaystyle\geqslant\Pr_{\ell}[\exists
C\text{ s.t. }(\ell,C)\in E^{\prime}]$
$\displaystyle\cdot\Pr_{\ell,y,h\in\ell}[f|_{N_{y,h}}=T(C)|_{N_{y,h}}\;|\;\exists
C\text{ s.t. }(\ell,C)\in E^{\prime}]$
$\displaystyle\geqslant(1-2\gamma)(1-(d+2)3\gamma)$ $\displaystyle\geqslant
1-5d\gamma.$

Since $\gamma=\frac{1}{1000d^{3}}\leqslant\frac{1}{10(d+2)^{3}}$. Theorem 3.1
now implies that there is a degree $d$ polynomial $g$ such that $f$ is
$4d\gamma$ close to $g$. ∎

Combining Lemmas 3.2 and 3.3 we get that for each excellent $(x,\sigma)$, the
plurality vote function $f_{x,\sigma}$ is $4d\gamma$-close to a degree $d$
polynomial.

######  Lemma 3.4.

For each excellent $(x,\sigma)$, the function $f_{x,\sigma}$ is
$4d\gamma$-close to a degree $d$ polynomial.

###### Proof.

Using Markov’s inequality and Lemma 3.2, $\Pr_{C\in
C_{x}}[T(C)\,{\stackrel{{\scriptstyle{2\gamma}}}{{\approx}}}\,f_{x,\sigma}|_{C}]\geqslant\frac{1}{2}\mu_{x}(\mathcal{C}_{x,\sigma})\geqslant\varepsilon/10$.
Thus, $f_{x,\sigma}$ satisfies the conditions of Lemma 3.3, and as a result,
it is $4d\gamma$-close to some degree $d$ polynomial. ∎

######  Lemma 3.5.

If $(x,\sigma)$ is excellent, then there exists a degree $d$ polynomial
$g_{x,\sigma}$ such that $g_{x,\sigma}$ agrees with $T(C)$ for at least
$1-2\sqrt{\gamma}$ of the cubes $C\in C_{x,\sigma}$.

###### Proof.

Let $g_{x,\sigma}$ be the degree $d$ polynomial guaranteed by Lemma 3.4 and
define,

$\mathcal{F}=\\{C\in\mathcal{C}_{x}\;|\;f_{x,\sigma}|_{C}\,{\stackrel{{\scriptstyle{\sqrt{\gamma}}}}{{\approx}}}\,T(C)\\},\qquad
A^{\prime}=\\{z\in\mathbb{F}_{q}^{n}\;|\;f_{x,\sigma}(z)\neq
g_{x,\sigma}(z)\\}.$

Then $\mu(A^{\prime})\leqslant 4d\gamma$ and and by Markov’s inequality and
Lemma 3.2,
$\mu_{x}(\mathcal{F})\geqslant(1-\sqrt{\gamma})\mu_{x}(\mathcal{C}_{x,\sigma})\geqslant\frac{\varepsilon}{10}$.

The bipartite inclusion graph
$G_{3}=G(\mathbb{F}_{q}^{n}\setminus\\{x\\},\mathcal{C}_{x})$ has second
singular value at most $1/q$ by Lemma 2.3. By Lemma 2.2 we have,

$\left|\Pr_{C\in\mathcal{F},y\in N(C)}[y\in
A^{\prime}]-\Pr_{y\in\mathbb{F}_{q}^{n}\setminus x,C\in
N(y)\cap\mathcal{F}}[y\in
A^{\prime}]\right|\leqslant\frac{1/q}{\sqrt{\mu_{x}(\mathcal{F})}}\leqslant\frac{1/q}{\sqrt{\varepsilon/10}}\leqslant
4\gamma.$

Since $\Pr_{y\in\mathbb{F}_{q}^{n}\setminus\\{x\\},C\in
N(y)\cap\mathcal{F}}[y\in A^{\prime}]\leqslant 2\mu(A^{\prime})$, where the
factor of $2$ accounts for the fact that $y\neq x$, it follows that
$\Pr_{C\in\mathcal{F},y\in N(C)}[y\in A^{\prime}]\leqslant
8d\gamma+4\gamma\leqslant 9d\gamma$. By applying Markov’s inequality again,
for at least $1-\sqrt{\gamma}$ of the cubes $C\in\mathcal{F}$, $g_{x,\sigma}$
and $f_{x,\sigma}$ agree on at least $1-9d\sqrt{\gamma}$ of the points in $C$.
Finally, since these cubes are in $\mathcal{F}$, $g_{x,\sigma}$ and $T(C)$
must agree on at least $1-\sqrt{\gamma}-9d\sqrt{\gamma}>\frac{d}{q}$ of the
points in $C$. By the Schwartz-Zippel lemma, $g_{x,\sigma}|_{C}=T(C)$ for such
$C$, and these cubes make up at least $(1-\sqrt{\gamma})^{2}>1-2\sqrt{\gamma}$
of the cubes in $\mathcal{C}_{x,\sigma}$. ∎

#### Concluding this section.

For each $(x,\sigma)\in X$ and degree $d$ polynomial $g_{x,\sigma}$, let
$\mathcal{F}_{x,\sigma}$ be the set of all cubes $C\in\mathcal{C}_{x,\sigma}$
satisfying $T(C)=g_{x,\sigma|C}$, and
$\mathcal{D}_{x,\sigma}=\mathcal{C}_{x,\sigma}\setminus\mathcal{F}_{x,\sigma}$.
By Lemma 3.5,
$\mu_{x}(\mathcal{F}_{x,\sigma})\geqslant(1-2\sqrt{\gamma})\mu_{x}(C_{x,\sigma})$
and
$\mu_{x}(D_{x,\sigma})\leqslant\frac{2\sqrt{\gamma}}{1-2\sqrt{\gamma}}\mu_{x}(\mathcal{F}_{x,\sigma})\leqslant\sqrt{5\gamma}\mathcal{F}_{x,\sigma}$.

###  3.2 Pruning the Pass Probability

Throughout this section, we consider the distribution $\mathcal{D}$ over
tuples $(x,\sigma,C_{1},y,\tau,C_{2})$ defined by the following process:

  1. 1.

Choose $x\in\mathbb{F}_{q}^{n}$ uniformly at random.

  2. 2.

Choose $\sigma\in\mathbb{F}_{q}$ with weight proportional to
$\mu_{x}(\mathcal{C}_{x,\sigma})$.

  3. 3.

Choose $C_{1}\in\mathcal{C}_{x,\sigma}$ uniformly at random.

  4. 4.

Choose $y\in C_{1}$ uniformly at random and different from $x$

  5. 5.

Choose $\tau\in\mathbb{F}_{q}$ with weight proportional to the fraction of
cubes $C\in\mathcal{C}_{x,y}$ with $\dim(C\cap C_{1})=2$ satisfying
$T(C)(y)=\tau$.

  6. 6.

Choose $C_{2}$ uniformly at random over
$\\{C\in{\mathcal{C}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\;|\;\dim(C\cap C_{1})=2\\}$.

Notice that the marginal distribution over $x,y$ is uniform, and conditioned
on $x,y$ the marginal distribution over $(C_{1},C_{2})$ is uniform among all
pairs of cubes intersecting in a plane $P$ that contains both $x$ and $y$. In
particular, the marginal of $(C_{1},C_{2})$ is uniform among cubes that
intersect in a plane, and so letting $S=\\{(C_{1},C_{2})\;|\;\dim(C_{1}\cap
C_{2})=2,\;T(C_{1})|_{C_{1}\cap C_{2}}=T(C_{2})|_{C_{1}\cap C_{2}}\\}$ we have

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\right]\geqslant\varepsilon.$ (3)

The distribution $\mathcal{D}$ can also be generated by either first choosing
$y\in\mathbb{F}_{q}^{n}$ and proceeding symmetrically, or by first choosing
$(x,y)\in\mathbb{F}_{q}^{n}$ and then choosing $(C_{1},C_{2})$ as a random
edge in the induced subgraph of $\operatorname{AffGras}(3,2)$ on $C_{xy}$ and
assigning $(\sigma,\tau)$ accordingly.

The main goal of this section is to prove the following lemma, asserting that
we may focus on the cases in which $C_{1},C_{2}$ lie in
$\mathcal{F}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}=\mathcal{F}_{x,\sigma}\cap\mathcal{F}_{y,\tau}$. Namely,
we show that a constant fraction of the probability on the left hand side of
(3) comes from the event that $C_{1},C_{2}$ are both in
$\mathcal{F}_{x,\sigma}\cap\mathcal{F}_{y,\tau}$.

######  Lemma 3.6.

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\text{ and
}C_{1},C_{2}\in{\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right]\geqslant\frac{\varepsilon}{4}.$

The rest of this section is devoted to the proof of Lemma 3.6. Towards this
end, recall from Section 3.1 that for each $(x,\sigma)\in X$ we write
$\mathcal{C}_{x,\sigma}=\mathcal{F}_{x,\sigma}\sqcup\mathcal{D}_{x,\sigma}$.
Therefore, we can deduce Lemma 3.6 by showing that the probability of passing
the test, i.e. $(C_{1},C_{2})\in S$ in conjunction of either one of the
events: (a) $(x,\sigma)\notin X$ and (b) $(x,\sigma)\in X$ but $C_{1}\in
D_{x,\sigma}$, is small. We begin by bounding the first event.

######  Lemma 3.7.

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S,\;(x,\sigma)\notin
X\right]\leqslant\frac{\varepsilon}{4}.$

###### Proof.

Consider the following alternative way of sampling according to $\mathcal{D}$.
First, choose a point $x$ uniformly at random, then a random
$\sigma\in\mathbb{F}_{q}$ with weight proportional to
$\mathcal{C}_{x,\sigma}$, a uniformly at random
$C_{1}\in\mathcal{C}_{x,\sigma}$, and finally a uniformly at random $C_{2}$
that intersects $C_{1}$ in a plane $P\ni x$. The point $y$ can then be chosen
at random from $P$ and $\tau=T(C_{2})(y)$. Viewing $\mathcal{D}$ this way we
see that

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S,\;(x,\sigma)\notin
X\right]\leqslant\mathop{\mathbb{E}}_{x,\sigma}\left[\mathbbm{1}_{(x,\sigma)\notin
X}(1-\Phi_{x}(C_{x,\sigma}))\right],$

since after $x$ and $\sigma$ are fixed, $(C_{1},C_{2})\in S$ only if
$T(C_{1})$ and $T(C_{2})$ agree on $x$ and $C_{2}\in C_{x,\sigma}$. This
probability, with $C_{x,\sigma}$ fixed, is precisely
$1-\Phi_{x}(C_{x,\sigma})$.

If $(x,\sigma)\notin X$, then either $\mu(C_{x,\sigma})<\varepsilon/5$, or
$p_{x,\sigma}+\frac{\gamma}{q^{n-2}-2}\geqslant\gamma\mu(C_{x,\sigma})$ by
Lemma 3.1. Therefore,

$\displaystyle\mathop{\mathbb{E}}_{x,\sigma}\left[\mathbbm{1}_{(x,\sigma)\notin
X}(1-\Phi_{x}(C_{x,\sigma}))\right]\leqslant$
$\displaystyle\;\mathop{\mathbb{E}}_{x,\sigma}\left[\mathbbm{1}_{\mu_{x}(C_{x,\sigma})<\varepsilon/5}(1-\Phi_{x}(C_{x,\sigma}))\right]$
$\displaystyle+\mathop{\mathbb{E}}_{x,\sigma}\left[\mathbbm{1}_{p_{x,\sigma}>\gamma\left(1-\Phi_{x}(\mathcal{C}_{x,\sigma})\right)}(1-\Phi_{x}(C_{x,\sigma}))\right].$

We bound each term on the right hand side separately. For the first term,
applying Lemma 2.1 yields

$\mathop{\mathbb{E}}_{x,\sigma}\left[\mathbbm{1}_{\mu_{x}(C_{x,\sigma})<\varepsilon/5}(1-\Phi_{x}(C_{x,\sigma}))\right]\leqslant\frac{\varepsilon}{5}+\frac{1}{q}.$

For the second term, we have

$\displaystyle\mathop{\mathbb{E}}_{x,\sigma}\left[\mathbbm{1}_{p_{x,\sigma}>\gamma\left(1-\Phi_{x}(\mathcal{C}_{x,\sigma})\right)}(1-\Phi_{x}(C_{x,\sigma}))\right]$
$\displaystyle\leqslant\mathop{\mathbb{E}}_{x,\sigma}\left[\frac{p_{x,\sigma}}{\gamma}\right]$
$\displaystyle\leqslant\frac{1000d^{4}}{q}.$

The last inequality is due to the fact that
$\mathop{\mathbb{E}}_{x,\sigma}\left[p_{x,\sigma}\right]$ can be bounded by
the probability that two degree at most $d$ entries $T(C_{1})$ and $T(C_{2})$
disagree on a line $\ell\subseteq C_{1}\cap C_{2}$, but agree on a point
$x\in\ell$. By the Schwartz-Zippel lemma, this probability is at most $d/q$.

Putting everything together gives:

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S,\;(x,\sigma)\notin
X\right]\leqslant\frac{\varepsilon}{5}+\frac{1000d^{4}}{q}\leqslant\frac{\varepsilon}{4}.$

∎

As $(x,\sigma)$ and $(y,\tau)$ have the same marginal distribution, we get
$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S,(y,\tau)\notin
X\right]\leqslant\varepsilon/4$, and it follows by the union bound that

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land((x,\sigma)\notin
X\lor(y,\tau)\notin X)\right]\leqslant\frac{\varepsilon}{2}.$ (4)

Next, we bound the contribution from $C_{1}\in\mathcal{D}_{x,\sigma}$.

######  Lemma 3.8.

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S,\;(x,\sigma)\in
X,\;C_{1}\in\mathcal{D}_{x,\sigma}\right]\leqslant 7\gamma\varepsilon$

###### Proof.

First we rewrite the probability as,

$\displaystyle\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S,\;(x,\sigma)\in
X,\;x\in\mathcal{D}_{x,\sigma}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x}\left[\sum_{(x,\sigma)\in
X}\mu(\mathcal{D}_{x,\sigma})\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S\;|\;C_{1}\in\mathcal{D}_{x,\sigma}\right]\right].$

We fix $(x,\sigma)\in X$ and upper bound
$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S\;|\;C_{1}\in\mathcal{D}_{x,\sigma}\right]$.

Conditioned on $C_{1}\in\mathcal{D}_{x,\sigma}$, the distribution
$\mathcal{D}$ chooses $C_{1}\in\mathcal{D}_{x,\sigma}$ uniformly at random, a
plane $P\subseteq C_{1}$ containing $x$, and $C_{2}$ containing $P$. For any
$C_{1}\in\mathcal{D}_{x,\sigma}$, we have by definition that $T(C_{1})\neq
g_{x,\sigma}|_{C_{1}}$, so by the Schwartz-Zippel Lemma we have
$T(C_{1})|_{P}=g_{x,\sigma}|_{P}$ with probability at most $d/q$. In the case
that $T(C_{1})|_{P}\neq g_{x,\sigma}|_{P}$, we immediately get that
$T(C_{1})|_{P}\neq T(C_{2})|_{P}$ for any $C_{2}\in\mathcal{F}_{x,\sigma}$
that contains $P$ (as $T(C_{2})=g_{x,\sigma}|_{C_{2}}$). Furthermore,
$T(C_{1})|_{P}\neq T(C_{2})|_{P}$ for all $C_{2}\notin\mathcal{C}_{x,\sigma}$
as $p\ni x$. Thus, if the plane $P$ is chosen so that $T(C_{1})|_{P}\neq
g_{x,\sigma}|_{P}$, then the test can pass only if
$C_{2}\in\mathcal{D}_{x,\sigma}$. Averaged over all $C_{1}\in D_{x,\sigma}$
the probability of picking such a plane $p\subseteq C_{1}$ and then
$C_{2}\in\mathcal{D}_{x,\sigma}$ is at most $1-\Phi_{x}(D_{x,\sigma}$).
Therefore,

$\displaystyle\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S\;|\;C_{1}\in\mathcal{D}_{x,\sigma}\right]\leqslant\frac{d}{q}+1\cdot(1-\Phi_{x}(\mathcal{D}_{x,\sigma}))\leqslant\frac{d+1}{q}+\mu(\mathcal{D}_{x,\sigma}),$

where we use Lemma 2.1. Thus,

$\displaystyle\mathop{\mathbb{E}}_{x}\left[\sum_{(x,\sigma)\in
X}\mu(\mathcal{D}_{x,\sigma})\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S\;|\;C_{1}\in\mathcal{D}_{x,\sigma}\right]\right]$
$\displaystyle\leqslant\mathop{\mathbb{E}}_{x}\left[\sum_{(x,\sigma)\in
X}\mu(\mathcal{D}_{x,\sigma})^{2}\right]+\frac{d+1}{q}$
$\displaystyle\leqslant\mathop{\mathbb{E}}_{x}\left[\sum_{(x,\sigma)\in
X}5\gamma\mu(\mathcal{F}_{x,\sigma})^{2}\right]+\frac{d+1}{q}.$

Finally notice that

$\mathop{\mathbb{E}}_{x}\left[5\gamma\mu(\mathcal{F}_{x,\sigma})^{2}\right]\leqslant
5\gamma\left(\mathop{\mathbb{E}}_{x}\left[\mu(\mathcal{F}_{x,\sigma})(1-\Phi_{x}(\mathcal{F}_{x,\sigma})\right]+\frac{1}{q^{n-2}-2}\right)\leqslant
5\gamma\left(\varepsilon+\frac{1}{q^{n-2}-2}\right)\leqslant
6\gamma\varepsilon,$

where we use the lower bound of Lemma 2.1 with $k=3$ for the first inequality.
The second inequality holds since
$\mu(\mathcal{F}_{x,\sigma})(1-\Phi_{x}(\mathcal{F}_{x,\sigma}))$ is exactly
the probability that $C_{1}$ and $C_{2}$ are both in $\mathcal{F}_{x,\sigma}$,
in which case the test passes. Hence, when this quantity is summed over all
$\sigma$ such that $(x,\sigma)\in X$ and averaged over all $x$, the value
obtained can be at most the overall pass probability of the test. ∎

######  Lemma 3.9.

Let $(x,\sigma,C_{1},y,\tau,C_{2})$ be a tuple chosen from $\mathcal{D}$ with
$(C_{1},C_{2})\in S$. Then,

$\mathcal{D}(x,\sigma,C_{1},y,\tau,C_{2})=\mathcal{D}(y,\tau,C_{2},x,\sigma,C_{1})=\mathcal{D}(x,\sigma,C_{2},y,\tau,C_{1})=\mathcal{D}(y,\tau,C_{1},x,\sigma,C_{2}).$

###### Proof.

Since $(C_{1},C_{2})\in S$, the table entries $T(C_{1})$ and $T(C_{2})$ must
agree on $x$ and $y$. Thus, $C_{1},C_{2}\in\mathcal{C}_{x,\sigma}$ and
$C_{1},C_{2}\in\mathcal{C}_{y,\tau}$. Now suppose $\mathcal{D}$ is generated
by first choosing cubes $C_{1},C_{2}$ uniformly at random conditioned on
$\dim(C_{1}\cap C_{2})=2$. Clearly the probability of choosing $(C_{1},C_{2})$
or $(C_{2},C_{1})$ is equal. Once the plane $C_{1}\cap C_{2}$ is fixed, the
pair $(x,y)$ is chosen uniformly at random over distinct ordered pairs of
points in $C_{1}\cap C_{2}$, while $\sigma$ and $\tau$ are set to
$T(C_{1})(x)$ and $T(C_{2})(y)$ respectively. Again, it is clear that the
pairs $(x,y)$ and $(y,x)$ have the same probability of being chosen. The
result of the lemma then follows. ∎

By Lemma 3.9, the bound in Lemma 3.8 still holds when either (or both) of
$(x,\sigma)$ or $C_{1}$ are replaced by $(y,\tau)$ or $C_{2}$ respectively.
Thus, letting $E$ be the event

$E=(C_{1}\in\mathcal{D}_{x,\sigma})\lor(C_{2}\in\mathcal{D}_{x,\sigma})\lor(C_{1}\in\mathcal{D}_{y,\tau})\lor(C_{2}\in\mathcal{D}_{y,\tau}),$

it follows that

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land(x,\sigma)\in X\land(y,\tau)\in
X\land E\right]\leqslant 28\gamma\varepsilon\leqslant\frac{\varepsilon}{4}.$
(5)

We are now ready to prove Lemma 3.6.

###### Proof of Lemma 3.6.

Let $H$ denote the event that both $(x,\sigma)$ and $(y,\tau)$ are in $X$. By
(4) and (3) we get that

$\varepsilon\leqslant\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S\right]=\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land
H\right]+\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S\land\bar{H}\right]\leqslant\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land
H\right]+\frac{\varepsilon}{2},$

so $\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land
H\right]\geqslant\frac{\varepsilon}{2}$. If $H$ holds, then we can write
$\mathcal{C}_{x,\sigma}=\mathcal{F}_{x,\sigma}\sqcup\mathcal{D}_{x,\sigma}$
and $\mathcal{C}_{y,\tau}=\mathcal{F}_{y,\tau}\sqcup\mathcal{D}_{y,\tau}$. Let
$H^{\prime}$ be the event that
$C_{1},C_{2}\in\mathcal{F}_{x,\sigma}\cap\mathcal{F}_{y,\tau}$, then

$\frac{\varepsilon}{2}\leqslant\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land
H\right]=\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land H\land
H^{\prime}\right]+\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land H\land
E\right],$

and by (5) we have $\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land H\land
E\right]\leqslant\frac{\varepsilon}{4}$ and so
$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in S\land H\land
H^{\prime}\right]\geqslant\frac{\varepsilon}{4}$. ∎

###  3.3 Bumps in measure are negligible

Throughout this section, let $\mathcal{F}_{x}$ be an arbitrary set of cubes
containing the point $x$ and suppose $\mu_{x}(\mathcal{F}_{x})=\eta$ (in our
setting, $\mathcal{F}_{x}$ will be $\mathcal{F}_{x,\sigma}$ for some
$(x,\sigma)\in X$). For $c>1$, let
$Y_{c}=\\{y\in\mathbb{F}_{q}^{n}\;|\;\mu_{x,y}(\mathcal{F}_{x}\cap\mathcal{C}_{y})\geqslant
c\eta\\}$, i.e. the set of points $y$ such that $\mathcal{F}_{x}$ is
significantly denser in $\mathcal{C}_{x,y}$. The goal of this section is to
show that the mass of $Y_{c}$ is small, namely:

######  Lemma 3.10.

Let
$Y_{c}=\\{y\in\mathbb{F}_{q}^{n}\setminus{x}\;|\;\mu_{x,y}(\mathcal{F}_{x}\cap\mathcal{C}_{y})>c\eta\\}$,
for $c>1$. Then,
$\mu(Y_{c})\leqslant\frac{4}{(c-1)^{2}\mu_{x}(\mathcal{F}_{x})q^{2}}$.

Towards the proof of Lemma 3.10, consider the distribution $\nu_{x}$ over
$\mathcal{C}_{x}$ generated by choosing a random $y\in Y_{c}$ and then a
random cube $C$ containing $x$ and $y$. Note that
$\nu_{x}(C)=\frac{z(C)}{|Y_{c}||\mathcal{C}_{x,y}|}$, where $z(C)=|C\cap
Y_{c}|$.

######  Lemma 3.11.

We have:

  1. 1.

$\mathop{\mathbb{E}}_{x}[z(C)]=\mu(Y_{c})(q^{3}-1)$.

  2. 2.

$\operatorname{var}[z(C)]\leqslant 2\mu(Y_{c})q^{4}$.

###### Proof.

The first item is clear using linearity of expectation, as the probability
that any fixed point $y\neq x$ from $Y_{c}$ is contained in a random cube
containing $x$ is $\frac{q^{3}-1}{|\mathbb{F}_{q}^{n}|}$.

For the second item, we write

$\mathop{\mathbb{E}}_{C}[z(C)^{2}]=\sum_{y_{1},y_{2}\in
Y_{c}}\mathop{\mathbb{E}}_{C}[\mathbbm{1}_{y_{1}\in C}\mathbbm{1}_{y_{2}\in
C}].$

If $x,y_{1},y_{2}$ are contained in a line, then the expectation in the sum is
$|Y_{c}|\frac{q^{3}-1}{q^{n}}$. This can happen for at most $|Y_{c}|q$ pairs
$y_{1},y_{2}$. Otherwise the expectation in the sum is
$|Y_{c}|^{2}\frac{(q^{3}-1)(q^{3}-q)}{q^{n}(q^{n}-q)}$. Overall this yields

$\mathop{\mathbb{E}}_{C}[z(C)^{2}]\leqslant|Y_{c}|q\frac{q^{3}-1}{q^{n}}+|Y_{c}|^{2}\frac{(q^{3}-1)(q^{3}-q)}{q^{n}(q^{n}-q)}\leqslant\mu(Y_{c})q^{4}+\mu(Y_{c})^{2}(q^{3}-1)^{2}\frac{q^{n}}{q^{n}-q}.$

Since $\mathop{\mathbb{E}}_{x}[z(C)]=\mu(Y_{c})(q^{3}-1)$, the second term on
the right hand side essentially cancels out and we can crudely bound the
variance by

$\operatorname{var}[z(C)]=\mathop{\mathbb{E}}_{x}[z(C)^{2}]-(\mu(Y_{c})(q^{3}-1))^{2}\leqslant\mu(Y_{c})q^{4}+\mu(Y_{c})^{2}(q^{3}-1)^{2}\frac{q}{q^{n}-q}\leqslant
2\mu(Y_{c})q^{4}.\qed$

###### Proof of Lemma 3.10.

We have

$|\mu_{x}(\mathcal{F}_{x})-\nu_{x}(\mathcal{F}_{x})|^{2}\leqslant\left(\sum_{C\in\mathcal{F}_{x}}|\mu_{x}(C)-\nu_{x}(C)|\right)^{2}\leqslant|\mathcal{F}_{x}|\sum_{C\in\mathcal{F}_{x}}(\mu_{x}(C)-\nu_{x}(C))^{2},$

where the first inequality is due to the triangle inequality, and the second
inequality is Cauchy-Schwartz. Fix some $y\neq x$, and recall that
$\nu_{x}(C)=\frac{z(C)}{|Y_{c}||\mathcal{C}_{x,y}|}$ and
$\mu_{x}(C)=\frac{\mathop{\mathbb{E}}_{C}[z(C)]}{|Y_{c}||\mathcal{C}_{x,y}|}=\frac{1}{|C_{x}|}$,
so

$(\mu_{x}(C)-\nu_{x}(C))^{2}=\frac{(z(C)-\mathop{\mathbb{E}}[z(C)])^{2}}{|Y_{c}|^{2}|\mathcal{C}_{x,y}|^{2}}.$

Therefore we may bound
$\sum_{C\in\mathcal{F}_{x}}(\mu_{x}(C)-\nu_{x}(C))^{2}\leqslant\sum_{C\in\mathcal{C}_{x}}(\mu_{x}(C)-\nu_{x}(C))^{2}\leqslant\frac{\operatorname{var}[z(C)]|\mathcal{C}_{x}|}{|Y_{c}|^{2}|\mathcal{C}_{x,y}|^{2}}$,
which with the previous inequality and Lemma 3.11 implies that

$|\mu_{x}(\mathcal{F}_{x})-\nu_{x}(\mathcal{F}_{x})|^{2}\leqslant
2\frac{|Y_{c}||\mathcal{F}_{x}||\mathcal{C}_{x}|q^{4}}{|Y_{c}|^{2}|\mathcal{C}_{x,y}|^{2}q^{n}}\leqslant\frac{4\eta
q^{n}}{|Y_{c}|q^{2}}=\frac{4\eta}{\mu(Y_{c})q^{2}}.$

where we use the facts that
$|\mathcal{C}_{x}|/|\mathcal{C}_{x,y}|\leqslant\frac{q^{3n}q^{3}}{q^{2n}q^{3}(q^{3}-1)}\leqslant\frac{q^{n}}{q^{3}-1}$
and $|\mathcal{F}_{x}|=\eta|\mathcal{C}_{x}|$. By definition,
$\nu_{x}(\mathcal{F}_{x})\geqslant c\eta$, so the left hand side is least
$(c-1)^{2}\eta^{2}$, and combining this with the above inequality yields
$\mu(Y_{c})\leqslant\frac{4}{(c-1)^{2}\eta q^{2}}$. ∎

###  3.4 Proof of Theorem 1.2

In this section we use the results of Sections 3.2 and 3.3 to prove Theorem
1.2. Namely, we find a degree $d$ polynomial that agrees with an
$\Omega(\varepsilon)$-fraction of the entries in $T$.

We start by rewriting the probability in Lemma 3.6 as an expectation over
random points $x$ and $y$. This can be seen as generating $\mathcal{D}$ by
first choosing $x$ and $y$, and then choosing $(C_{1},C_{2})$ as two random
cubes in $\mathcal{C}_{x,y}$ that intersect in a plane, and setting
$\sigma=T(C_{1})(x)$ and $\tau=T(C_{2})(y)$. Lemma 3.6 then states

$\Pr_{\mathcal{D}}\left[(C_{1},C_{2})\in
S,\;C_{1},C_{2}\in\mathcal{F}_{x,\sigma}\cap\mathcal{F}_{y,\tau}\right]=\mathop{\mathbb{E}}_{x,y}\left[\sum_{(x,\sigma),(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\left(1-\Phi_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\right)\right]\geqslant\frac{\varepsilon}{4}.$

Applying Lemma 2.1 we get

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(x,\sigma),(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\right]+\frac{1}{q}\geqslant\frac{\varepsilon}{4}.$
(6)

At this point, we would like to restrict to
${\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\ y,\tau\end{subarray}}$ such
that $\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)$ is not significantly larger than
$\mu_{x}(\mathcal{F}_{x,\sigma})$ and $\mu_{y}(\mathcal{F}_{y,\tau})$. Let
$H_{x,\sigma}(y,\tau)$ denote the indicator for the event that
$\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)>2\mu_{x}(\mathcal{F}_{x,\sigma})$.

######  Lemma 3.12.

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(x,\sigma),(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}(H_{x,\sigma}(y,\tau)+H_{y,\tau}(x,\sigma))\right]\leqslant\frac{400\log(5/\varepsilon)}{q^{2}}.$

###### Proof.

We bound

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(x,\sigma),(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}H_{x,\sigma}(y,\tau)\right]=\mathop{\mathbb{E}}_{x}\left[\sum_{(x,\sigma)\in
X}\mathop{\mathbb{E}}_{y}\left[\sum_{(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}H_{x,\sigma}(y,\tau)\right]\right].$

Fix an $(x,\sigma)\in X$ and denote $\eta=\mu_{x}(F_{x,\sigma})$. Let
$A_{y}(j)$ denote the indicator of the event that
$2^{j}\eta\leqslant\mu_{x,y}\left({\mathcal{F}}_{x,\sigma,y}\right)<2^{j+1}\eta$.
Since all cubes in $F_{x,\sigma}$ agree with a function $g_{x,\sigma}$, for
each $y$ there can only be one $\tau$, namely $\tau=g_{x,\sigma}(y)$, such
that $\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)>0$. Thus, denoting
${\mathcal{F}}_{x,\sigma,y}={\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}$ for this $\tau$, for all $(x,\sigma)\in X$ we have:

$\mathop{\mathbb{E}}_{y}\left[\sum_{(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}H_{x,\sigma}(y,\tau)\right]\leqslant\mathop{\mathbb{E}}_{y}\left[\mu_{x,y}({\mathcal{F}}_{x,\sigma,y})^{2}H_{x,\sigma}(y,\tau)\right]$

We start by performing dyadic partitioning of the inner expectation with
$(x,\sigma)$ fixed.

$\displaystyle\mathop{\mathbb{E}}_{y}\left[\mu_{x,y}({\mathcal{F}}_{x,\sigma,y})^{2}H_{x,\sigma}(y,\tau)\right]\leqslant\sum_{j=1}^{\log(1/\eta)}\mathop{\mathbb{E}}_{y}[A_{y}(j)\mu_{x,y}({\mathcal{F}}_{x,\sigma,y})^{2}]\leqslant\sum_{j=1}^{\log(1/\eta)}\mathop{\mathbb{E}}_{y}[A_{y}(j)(2^{j+1}\eta)^{2}].$

Using Lemma 3.10 gives

$\mathop{\mathbb{E}}_{y}[A_{y}(j)(2^{j+1}\eta)^{2}]\leqslant(2^{j+1}\eta)^{2}\mu(Y_{2^{j}})\leqslant\frac{100\eta}{q^{2}}.$

Combining everything, we get that

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(x,\sigma),(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}H_{x,\sigma}(y,\tau)\right]\leqslant\mathop{\mathbb{E}}_{x}\left[\sum_{(x,\sigma)\in
X}\log(1/\eta)\frac{100\mu(\mathcal{F}_{x,\sigma})}{q^{2}}\right]\leqslant\frac{200\log(5/\varepsilon)}{q^{2}}.$

Similarly, $\mathop{\mathbb{E}}_{x,y}\left[\sum_{(x,\sigma),(y,\tau)\in
X}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}H_{y,\tau}(x,\sigma)\right]\leqslant\frac{200\log(5/\varepsilon)}{q^{2}}$,
and the proof is concluded. ∎

Let $X^{\prime}(x,y)=\\{(\sigma,\tau)\;|\;(x,\sigma),(y,\tau)\in
X,\;H_{x,\sigma}(y,\tau)+H_{y,\tau}(x,\sigma)=0\\}$.

As an immediate consequence of Lemma 3.12,

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(\sigma,\tau)\in
X^{\prime}(x,y)}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\right]\geqslant\frac{\varepsilon}{4}-\frac{1}{q}-\frac{400\log(5/\varepsilon)}{q^{2}}\geqslant\frac{\varepsilon}{5}.$

Also,

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(\sigma,\tau)\in
X^{\prime}(x,y)}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\mathbbm{1}_{\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\leqslant\frac{\varepsilon}{10}}\right]\leqslant\frac{\varepsilon}{10}\mathop{\mathbb{E}}_{x,y}\left[\sum_{(\sigma,\tau)\in
X^{\prime}(x,y)}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\right]\leqslant\frac{\varepsilon}{10},$

and so

$\mathop{\mathbb{E}}_{x,y}\left[\sum_{(\sigma,\tau)\in
X^{\prime}(x,y)}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\mathbbm{1}_{\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)>\frac{\varepsilon}{10}}\right]\geqslant\frac{\varepsilon}{10}.$

Therefore, there is some $x$ such that

$\mathop{\mathbb{E}}_{y}\left[\sum_{(\sigma,\tau)\in
X^{\prime}(x,y)}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\mathbbm{1}_{\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)>\frac{\varepsilon}{10}}\right]\geqslant\frac{\varepsilon}{10},$

and we fix such $x$ henceforth. For this point $x$, there are at most
$5/\varepsilon$ values $\sigma$ such that $(\sigma,\tau)\in X^{\prime}(x,y)$
for some pair $(y,\tau)$. Consequently for this $x$, there is a value $\sigma$
such that

$\mathop{\mathbb{E}}_{y}\left[\sum_{\tau:(\sigma,\tau)\in
X^{\prime}(x,y)}\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\mathbbm{1}_{\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)>\frac{\varepsilon}{10}}\right]\geqslant\frac{\varepsilon^{2}}{50}.$

Let $\eta=\mu_{x}(F_{x,\sigma})$. For each $y$, note that only
$\tau=g_{x,\sigma}(y)$ such that $(\sigma,\tau)\in X^{\prime}(x,y)$ can
contribute to the above sum, and the corresponding summand
$\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)$ is between $\varepsilon/10$ and $2\eta$, and so
there is some $t\in[\varepsilon/10,2\eta)$ such that

$\mathop{\mathbb{E}}_{y}\left[\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)^{2}\mathbbm{1}_{\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\in[t,2t]}\mathbbm{1}_{(\sigma,\tau)\in
X^{\prime}(x,y)}\right]\geqslant\frac{\varepsilon^{2}}{50\log(10/\varepsilon)}.$

Let $Y$ be the set consisting of $x$ and all $y$’s such that
$\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\in[t,2t]$ and $(\sigma,\tau)\in X^{\prime}(x,y)$
for $\tau=g_{x,\sigma}(y)$; writing $p_{t}=\Pr_{y}\left[y\in Y\right]$, we get
that $t^{2}p_{t}\geqslant\frac{\varepsilon^{2}}{200\log(10/\varepsilon)}$.

For $y\in Y$, let $\tau=g_{x,\sigma}(y)$ and denote
$\mathcal{F}_{y}=\mathcal{F}_{y,\tau}$ and $\mathcal{F}=\cup_{y\in
Y}\mathcal{F}_{y}$.

######  Lemma 3.13.

For all $y\in Y$ we have that $g_{x,\sigma}\equiv g_{y,\tau}$.

###### Proof.

Assume towards contradiction that $g_{x,\sigma}\not\equiv g_{y,\tau}$. We
choose a cube in $C\in\mathcal{C}_{x,y}$ uniformly at random and bound the
probability that $g_{x,\sigma}|_{C}=g_{y,\tau}|_{C}$. Note that any cube in
$C\in\mathcal{C}_{x,y}$ is of the form
$x+\operatorname{span}(y-x,z_{1},z_{2})$, so we may choose a cube in
$\mathcal{C}_{x,y}$ uniformly at random by choosing $z_{1},z_{2}$, such that
$z_{1}\notin x+\operatorname{span}(y-x)$, $z_{2}\notin
x+\operatorname{span}(y-x,z_{1})$. By the Schwartz-Zippel Lemma, the
probability that $g_{x,\sigma}$ and $g_{y,\tau}$ are equal on both $z_{1}$ and
$z_{2}$ is at most $(\frac{2d}{q})^{2}=\frac{4d^{2}}{q^{2}}$. The factors of
$2$ account for the fact that $z_{1}$ and $z_{2}$ are not uniform over all
possible points. Thus,

$\frac{\varepsilon}{10}\leqslant\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)\leqslant\Pr_{C\in\mathcal{C}_{x,y}}\left[g_{x,\sigma}|_{C}=g_{y,\tau}|_{C}\right]\leqslant\frac{4d^{2}}{q^{2}},$

and contradiction. ∎

Thus, denoting $g=g_{x,\sigma}$ we get that $g|_{C}=T(C)$ for all
$C\subseteq\mathcal{F}$. We finish the proof by showing that
$\mu(\mathcal{F})\geqslant\Omega(\varepsilon)$. Towards this end, consider the
bipartite inclusion graph $G_{5}=G(\mathbb{F}_{q}^{m},\mathcal{C})$, which has
second singular value at most $q^{-3/2}$ by Lemma 2.3. By Lemma 2.2,

$\left|\Pr_{y\in Y,C\ni
y}\left[C\in\mathcal{F}\right]-\Pr_{C\in\mathcal{C},y\in
C}\left[C\in\mathcal{F}\right]\right|\leqslant\frac{q^{-3/2}}{\sqrt{\mu(Y)}}=\frac{1}{\sqrt{q^{3}p_{t}}}\leqslant
t\frac{\sqrt{200\log(10/\varepsilon)}}{\sqrt{q^{3}\varepsilon^{2}}},$

where we used
$p_{t}\geqslant\frac{\varepsilon^{2}}{200t^{2}\log(10/\varepsilon)}$. Since
for each $y\in Y$ we have $(\sigma,\tau)\in X^{\prime}(x,y)$ for
$\tau=g_{x,\sigma}(y)$, we have

$\mu_{y}(\mathcal{F}_{y})\geqslant\frac{\mu_{x,y}\left({\mathcal{F}}_{\begin{subarray}{c}x,\sigma\\\
y,\tau\end{subarray}}\right)}{2}\geqslant\frac{t}{2}.$

Therefore, $\Pr_{y\in Y,C\ni
y}\left[C\in\mathcal{F}\right]\geqslant\frac{t}{2}$, so we get

$\mu(\mathcal{F})=\Pr_{C\in\mathcal{C}}\left[C\in\mathcal{F}\right]\geqslant\frac{t}{2}-t\frac{\sqrt{200\log(10/\varepsilon)}}{\sqrt{q^{3}\varepsilon^{2}}}\geqslant\frac{t}{3},$

where we used the fact that $\varepsilon\geqslant\frac{10^{7}d^{6}}{q}$. Since
$t\geqslant\varepsilon/10$, the proof is concluded.

## References

  * [1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and hardness of approximation problems.  In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 14–23, 1992.
  * [2] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs; A new characterization of NP.  In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 2–13, 1992.
  * [3] Sanjeev Arora and Madhu Sudan.  Improved low-degree testing and its applications.  In Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, pages 485–495, 1997.
  * [4] Amey Bhangale, Irit Dinur, and Inbal Livni Navon.  Cube vs. cube low degree test.  In 8th Innovations in Theoretical Computer Science Conference, pages 1–31, 2017.
  * [5] Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, and Shmuel Safra.  PCP characterizations of NP: toward a polynomially-small error-probability.  Comput. Complex., 20(3):413–504, 2011.
  * [6] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy.  Approximating clique is almost np-complete (preliminary version).  In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 2–12, 1991.
  * [7] Christopher Godsil and Karen Meagher.  Erdos-Ko-Rado theorems: algebraic approaches.  Number 149. Cambridge University Press, 2016.
  * [8] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson.  New direct-product testers and 2-query pcps.  SIAM J. Computing, 38(1):140–180, 2012.
  * [9] Dana Moshkovitz and Ran Raz.  Sub-constant error low degree test of almost-linear size.  SIAM J. Computing, 38(1):140–180, 2008.
  * [10] Ran Raz and Shmuel Safra.  A sub-constant error-probability low-degree test, and a subconstant error-probability pcp characterization of np.  In Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, pages 475–484, 1997.
  * [11] Ronitt Rubinfeld and Madhu Sudan.  Robust characterizations of polynomials with applications to program testing.  SIAM J. Computing, 25(2):252–271, 1996.