# Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer Department of Mathematics, Massachusetts Institute of Technology,
Cambridge, USA. Supported by NSF CCF award 2227876 and NSF CAREER award
2239160. Kai Zhe Zheng Department of Mathematics, Massachusetts Institute of
Technology, Cambridge, USA. Supported by the NSF GRFP DGE-2141064.

###### Abstract

We show that for all $\varepsilon>0$, for sufficiently large prime power
$q\in\mathbb{N}$, for all $\delta>0$, it is NP-hard to distinguish whether a
$2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least
$1-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly
optimal alphabet-to-soundness tradeoff for $2$-query PCPs with alphabet size
$q$, improving upon a result of Chan [Cha16]. Our result has the following
implications:

  1. 1.

Near optimal hardness for Quadratic Programming: it is NP-hard to approximate
the value of a given Boolean Quadratic Program within factor $(\log
n)^{1-o(1)}$ under quasi-polynomial time reductions. This result improves a
result of Khot and Safra [KS13] and nearly matches the performance of the best
known approximation algorithm [Meg01, NRT99, CW04] that achieves a factor of
$O(\log n)$.

  2. 2.

Bounded degree $2$-CSP’s: under randomized reductions, for sufficiently large
$d>0$, it is NP-hard to approximate the value of $2$-CSPs in which each
variable appears in at most $d$ constraints within factor
$(1-o(1))\frac{d}{2}$, improving upon a recent result of Lee and Manurangsi
[LM23].

  3. 3.

Improved hardness results for connectivity problems: using results of
Laekhanukit [Lae14] and Manurangsi [Man19], we deduce improved hardness
results for the Rooted $k$-Connectivity Problem, the Vertex-Connectivity
Survivable Network Design Problem and the Vertex-Connectivity $k$-Route Cut
Problem.

##  1 Introduction

The PCP theorem is a fundamental result in theoretical computer science with
many equivalent formulations [FGL+91, AS03, ALM+92]. One of the formulations
asserts that there exists $\varepsilon>0$ such that given a satisfiable
$3$-SAT formula $\phi$, it is NP-hard to find an assignment that satisfies at
least $(1-\varepsilon)$ fraction of the constraints. The PCP theorem has a
myriad of applications within theoretical computer science, and of particular
interest to this paper are applications of PCP to hardness of approximation.

The vast majority of hardness of approximation result are proved via
reductions from the PCP theorem above. Oftentimes, to get a strong hardness of
approximation result, one must first amplify the basic PCP theorem above into
a result with stronger parameters [Hås01, Hås96, Fei98, KP06] (see [Tre14] for
a survey). To discuss these parameters, it is often convenient to view the PCP
through the problem of $2$-Prover-$1$-Round Games, which we define
next.111Strictly speaking, the notion below is referred to in the literature
as projection $2$-Prover-$1$-Round games. We omit the more general definition
as we do not discuss non-projection games in this paper.

######  Definition 1.1.

An instance $\Psi$ of $2$-Prover-$1$-Round Games consists of a bipartite graph
$G=(L\cup R,E)$, alphabets $\Sigma_{L}$ and $\Sigma_{R}$ and a collection of
constraints $\Phi=\\{\phi_{e}\\}_{e\in E}$, which for each edge $e\in E$
specifies a constraint map $\phi_{e}\colon\Sigma_{L}\to\Sigma_{R}$.

  1. 1.

The alphabet size of $\Psi$ is defined to be $|\Sigma_{L}|+|\Sigma_{R}|$.

  2. 2.

The value of $\Psi$ is defined to be the maximum fraction of edges $e\in E$
that can be satisfied by any assignment. That is,

${\sf val}(\Psi)=\max_{\begin{subarray}{c}A_{L}\colon L\to\Sigma_{L}\\\
A_{R}\colon R\to\Sigma_{R}\end{subarray}}\frac{|\\{e=(u,v)\in
E~{}|~{}\phi_{e}(A_{L}(u))=A_{R}(v)\\}|}{|E|}.$

The combinatorial view of $2$-Prover-$1$-Round Games has its origins in an
equivalent, active view in terms of a game between a verifier and two all
powerful provers, which is sometimes more intuitive. The verifier and the two
provers have access to an instance $\Psi$ of $2$-Prover-$1$-Round Games, and
the provers may agree beforehand on a strategy; after this period they are not
allowed to communicate. The verifier then picks a random edge, $e=(u,v)$, from
the $2$-Prover-$1$-Round game, sends $u$ to the first prover, sends $v$ to the
second prover, receives a label in response from each one of them, and finally
checks that the labels satisfy the constraint $\phi_{e}$. If so, then the
verifier accepts. It is easy to see that the value of the $2$-Prover-$1$-Round
game is equal to the acceptance probability of the verifier under the best
strategy of the provers. This view will be useful for us later.

In the language of $2$-Prover-$1$-Round Games, the majority of hardness of
approximation results are proved by combining the basic PCP theorem [FGL+91,
AS03, ALM+92] with Raz’s parallel repetition theorem [Raz98], which together
imply the following result:

######  Theorem 1.2.

There exists $\gamma>0$ such that for sufficiently large $R$, given a
$2$-Prover-$1$-Round game $\Psi$ with alphabet size $R$, it is NP-hard to
distinguish between the following two cases:

  1. 1.

YES case: ${\sf val}(\Psi)=1$.

  2. 2.

NO case: ${\sf val}(\Psi)\leqslant\frac{1}{R^{\gamma}}$.

For many applications, one only requires that the soundness error of the PCP
is small. Namely, that ${\sf val}(\Psi)$ is arbitrarily small in the “NO
case”. For certain applications however, more is required: not only must the
soundness error be small – but it must also be small in terms of the alphabet
size. The tradeoff between the soundness error of the PCP and the alphabet
size of the PCP is the main focus of this paper.

With respect to this tradeoff, it is clear that the best result one may hope
for in Theorem 1.2 is $\gamma=1-o(1)$ since a random assignment to $\Psi$
satisfies, in expectation, at least $\frac{1}{R}$ fraction of the constraints.
In terms of results, combining the PCP theorem with Raz’s parallel repetition
theorem gives $\gamma>0$ that is an absolute, but tiny constant. Towards a
stronger tradeoff, Khot and Safra [KS13] showed that Theorem 1.2 holds for
$\gamma=1/6$ with imperfect completeness (i.e., ${\sf val}(\Psi)\geqslant
1-o(1)$ instead of ${\sf val}(\Psi)=1$ in the YES case). The result of Khot
and Safra was improved by Chan [Cha16], who showed (using a completely
different set of techniques) that Theorem 1.2 holds for $\gamma=1/2-o(1)$,
again with imperfect completeness.

###  1.1 Main Results

In this section we explain the main results of this paper.

####  1.1.1 Near Optimal Alphabet vs Soundness Tradeoff

The main result of this work improves upon all prior results, and shows that
one may take $\gamma=1-o(1)$ in Theorem 1.2, again with imperfect
completeness. Formally, we show:

######  Theorem 1.3.

For all $\varepsilon,\delta>0$, for sufficiently large $R$, given a
$2$-Prover-$1$-Round game $\Psi$, it is NP-hard to distinguish between the
following two cases:

  1. 1.

YES case: ${\sf val}(\Psi)\geqslant 1-\delta$.

  2. 2.

NO case: ${\sf val}(\Psi)\leqslant\frac{1}{R^{1-\varepsilon}}$.

Theorem 1.3 shows a near optimal tradeoff between the alphabet of a PCP and
the alphabet of a PCP, improving upon the result of Chan [Cha16]. Moreover,
Theorem 1.3 has several applications to combinatorial optimization problems,
which we discuss below. We remark that most of these applications require
additional features from the instances produced in Theorem 1.3 which we omit
from its formulation for the sake of clarity. For instance, one application
requires a good tradeoff between the size of the instance and the size of the
alphabet, which our construction achieves (see the discussion following
Theorem 1.4). Other applications require the underlying constraint graph to be
bounded-degree bi-regular graph, which our construction also achieves (after
mild modifications; see Theorem 7.1).

####  1.1.2 Application: NP-Hardness of Approximating Quadratic Programs

Theorem 1.3 has an application to the hardness of approximating the value of
Boolean Quadratic Programming, as we explain next.

An instance of Quadratic programming consists of a quadratic form
$Q(x)=\sum\limits_{i,j=1}^{n}a_{i,j}x_{i}x_{j}$ where $a_{i,i}=0$ for all $i$,
and one wishes to maximize $Q(x)$ over $x\in\\{-1,1\\}^{n}$. This problem is
known to have an $O(\log n)$ approximation algorithm [Meg01, NRT99, CW04], and
is known to be quasi-NP-hard to approximate within factor $(\log
n)^{1/6-o(1)}$ [ABH+05, KS13]. That is, unless NP has a quasi-polynomial time
algorithm, no polynomial time algorithm can approximate Quadratic Programming
to within factor $(\log n)^{1/6-o(1)}$. As a first application of Theorem 1.3,
we improve the hardness result of Khot and Safra:

######  Theorem 1.4.

It is quasi-NP-hard to approximate Quadratic Programming to within a factor of
$(\log n)^{1-o(1)}$.

Theorem 1.4 is proved via a connection between $2$-Prover-$1$-Round Games and
Quadratic Programming due to Arora, Berger, Hazan, Kindler, and Safra
[ABH+05]. This connections requires a good tradeoff between the alphabet size,
the soundness error of the PCP, and the size of the PCP. Fortunately, the
construction in Theorem 1.4 has a sufficiently good tradeoff between all of
these parameters: letting $N$ be the size of the instance, the alphabet size
can be taken to be $(\log N)^{1-o(1)}$ and the soundness error can be taken to
be $(\log N)^{-1+o(1)}$. 222We remark that the result of Chan [Cha16] does not
achieve a good enough trade-off between the alphabet size and the instance
size due to the use of the long-code, and therefore it does not yield a strong
inapproximability result for Quadratic Programming.

##### Relevance to the sliding scale conjecture:

It is worth noting that using our techniques, we do not know how to achieve
soundness error that is smaller than inversely poly-logarithmic in the
instance size. In particular, our techniques have no bearing on the sliding
scale conjecture, which is concerned with getting soundness error that is
inversely polynomial in the instance size. This seems to be a bottleneck of
any PCP construction that is based on the covering property. In fact, assuming
ETH, any quasi-polynomial PCP construction achieving soundness error, say,
$1/(\log N)^{2}$ would necessarily need to have almost polynomial alphabet
size (since the reduction to Quadratic Solvability would give an algorithm
that runs roughly in time exponential in the alphabet size), which is the
opposite of what our techniques give. With this in mind, we would like to
mention a closely related, recent conjecture made in [CDGT22], which is a sort
of a mixture between $d$-to-$1$ games and the sliding scale conjecture. This
conjecture is motivated by improved hardness results for densest $k$-subgraph
style problems, and focuses on the relation between the instance size and the
soundness error (allowing the alphabet to be quite large). It may be possible
that the ideas from the current paper can help make progress towards this
conjecture.

####  1.1.3 Application: NP-hardness of Approximating Bounded Degree $2$-CSPs

Theorem 1.3 has an application to the hardness of approximating the value of
$2$-CSPs with bounded degree, as we explain next.

An instance $\Psi$ of $2$-CSP, say $\Psi=(X,C,\Sigma)$, consists of a set of
variables $X$, a set of constraints $C$ and an alphabet $\Sigma$. Each
constraint in $C$ has the form $P(x_{i},x_{j})=1$ where
$P\colon\Sigma\times\Sigma\to\\{0,1\\}$ is a predicate (which may be different
in distinct constraints). The degree of the instance $\Psi$ is defined to be
the maximum, over variables $x\in X$, of the number of constraints that $x$
appears in. The goal is to find an assignment $A\colon X\to\Sigma$ that
satisfies as many of the constraints as possible.

There is a simple $\frac{d+1}{2}$ approximation algorithm for the $2$-CSP
problem for instances with degree at most $d$. Lee and Manurangsi proved a
nearly matching $\left(\frac{1}{2}-o(1)\right)d$ hardness of approximation
result assuming the Unique-Games Conjecture [LM23]. Unconditionally, they show
the problem to be NP-hard to approximate within factor
$\left(\frac{1}{3}-o(1)\right)d$ under randomized reductions.

Using the ideas of Lee and Manurangsi, our main result implies a nearly
matching NP-hardness result for bounded degree $2$-CSPs:

######  Theorem 1.5.

For all $\eta>0$, for sufficiently large $d$, approximating the value of
$2$-CSPs with degree at most $d$ within factor
$\left(\frac{1}{2}-\eta\right)d$ is NP-hard under randomized reductions.

As in [LM23], Theorem 1.5 has a further application to finding independent
sets in claw free graphs. A $k$-claw $K_{1,k}$ is the $(k+1)$ vertex graph
with a center vertex which is connected to all other $k$-vertices and has no
other edges; a graph $G$ is said to be $k$-claw free if $G$ does not contain
an induced $k$-claw graph. There is a polynomial time approximation algorithm
for approximating the size of the largest independent set in a given $k$-claw
free graph $G$ within factor $\frac{k}{2}$ [Ber00, TW23], and a quasi-
polynomial time approximation algorithm within factor
$\left(\frac{1}{3}+o(1)\right)k$ [CGM13]. As in [LM23], using ideas from
[DFRR23] Theorem 1.5 implies that for all $\varepsilon>0$, for sufficiently
large $k$, it is NP-hard (under randomized reductions) to approximate the size
of the largest independent set in a given $k$-claw free graph within factor
$\left(\frac{1}{4}+\eta\right)k$. This improves upon the result of [LM23] who
showed that the same result holds assuming the Unique-Games Conjecture.

####  1.1.4 Application: NP-hardness of Approximating Connectivity Problems

Using ideas of Laekhanukit [Lae14] and the improvements by Manurangsi [Man19],
Theorem 1.3 implies improved hardness of approximation results for several
graph connectivitiy problems. More specifically, Theorem 1.3 combined with the
results of [Man19] implies improvements to each one of the results outlined in
table $1$ in [Lae14] by a factor of $2$ in the exponent - with the exception
of Rooted-$k$-Connectivity on directed graphs where a factor of $2$
improvement is already implied by [Man19]. We briefly discuss the Rooted
$k$-Connectivity Problem, but defer the reader to [Lae14] for a detailed
discussion of the remaining graph connectivity problems.

In the Rooted $k$-Connectivity problem there is a graph $G=(V,E)$, edge costs
$c\colon E\to\mathbb{R}$, a root vertex $r\in V$ and a set of terminals
$T\subseteq V\setminus\\{r\\}$. The goal is to find a sub-graph $G^{\prime}$
of smallest cost that for each $t\in T$, has at least $k$ vertex disjoint
paths from $r$ to $t$. The problem admits $|T|$ trivial approximation
algorithm (by applying minimum cost $k$-flow algorithm for each vertex in
$T$), as well as an $O(k\log k)$ approximation algorithm [Nut12].

Using the ideas of [Lae14], Theorem 1.3 implies the following improved
hardness of approximation results:

######  Theorem 1.6.

For all $\varepsilon>0$, for sufficiently large $k$ it is NP-hard to
approximate the Rooted-$k$-Connectivity problem on undirected graphs to within
a factor of $k^{1/5-\varepsilon}$, the Vertex-Connectivity Survivable Network
Design Problem with connectivity parameters at most $k$ to within a factor of
$k^{1/3-\varepsilon}$, and the Vertex-Connectivity $k$-Route Cut Problem to
within a factor of $k^{1/3-\varepsilon}$.

We remark that in [CCK08], a weaker form of hardness for the Vertex-
Connectivity Survivable Network problem is proved. More precisely, they show
an $\Omega(k^{1/3}/\log k)$ integrality gap for the set-pair relaxation of the
problem. Our hardness result of $k^{1/3-\varepsilon}$ improves upon it,
showing that (unless P$=$NP) no relaxation can yield a better than
$k^{1/3-\varepsilon}$ factor approximation algorithm.

###  1.2 Our Techniques

Theorem 1.3 is proved via a composition of an Inner PCP and an Outer PCP. Both
of these components incorporate ideas from the proof of the $2$-to-$1$ Games
Theorem. The outer PCP is constructed using smooth parallel repetition [KS13,
KMS17] while the inner PCP is based on the Grassmann graph [KMS17, DKK+18,
DKK+21, KMS23].

The novelty in this current paper, in terms of techniques, is twofold. First,
we must consider a Grassmann test in a different regime of parameters (as
otherwise we would not be able to get a good alphabet to soundness tradeoff)
and in a regime of much lower soundness error. These differences complicate
matters considerably. Second, our soundness analysis is more involved than
that of the $2$-to-$1$-Games Theorem. As is the case in [KMS17, DKK+18,
DKK+21, KMS23], we too use global hyperconractivity, but we do so more
extensively. We also require quantitatively stronger versions of global
hypercontractivity over the Grasssmann graph which are due to [EKL24]. In
addition, our analysis incorporates ideas from the plane versus plane test and
direct product testing [RS97, IKW12, MZ23], from classical PCP theory [KS13],
as well as from error correcting codes [GRS00]. All of these tools are
necessary to prove our main technical statement – Lemma 1.7 below – which is a
combinatorial statement that may be of independent interest.

We now elaborate on each one of the components separately.

####  1.2.1 The Inner PCP

Our Inner PCP is based on the subspace vs subspace low degree test. Below, we
first give a general overview of the objective in low-degree testing. We then
discuss the traditional notion of soundness as well as a non-traditional
notion of soundness for low-degree tests. Finally, we explain the low-degree
test used in this paper, the notion of soundness that we need from it, and the
way that this notion of soundness is used.

##### Low degree tests in PCPs.

Low degree tests have been have a vital component in PCPs since their
inception, and much attention has been devoted to improving their various
parameters. The goal in low-degree testing is to encode a low-degree function
$f\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ via a table (or a few tables) of
values, in a way that allows for local testing. Traditionally, one picks a
parameter $\ell\in\mathbb{N}$ (which is thought of as a constant and is most
often just $2$) and encodes the function $f$ by the table $T$ of restrictions
of $f$ to $\ell$-dimensional affine subspaces of $\mathbb{F}_{q}^{n}$. For the
case $\ell=2$, the test associated with this encoding is known as the Plane vs
Plane test [RS97]. The Plane vs Plane test proceeds by picking two planes
$P_{1}$, $P_{2}$ intersecting on a line, and then checking that $T[P_{1}]$ and
$T[P_{2}]$ agree on $P_{1}\cap P_{2}$. It is easy to see that the test has
perfect completeness, namely that a valid table of restrictions $T$ passes the
test with probability $1$. In the other direction, the soundness error of the
test – which is a converse type statement – is much less clear (and is crucial
towards applications in PCP). In the context of the Plane vs Plane test, it is
know that if a table $T$, that assigns to each plane a degree $d$ function,
passes the Plane vs Plane test with probability $\varepsilon\geqslant q^{-c}$
(where $c>0$ is a small absolute constant), then there is a degree $d$
function $f$ such that $T[P]\equiv f|_{P}$ on at least $\Omega(\varepsilon)$
fraction of the planes.

Nailing down the value of the constant $c$ for which soundness holds is an
interesting open problem which is related to soundness vs alphabet size vs
instance size tradeoff in PCPs [MR10, BDN17, MZ23]. Currently, the best known
analysis for the Plane vs Plane test [MR10] shows that one may take $c=1/8$.
Better analysis is known for higher dimensional encoding [BDN17, MZ23], and
for the $3$-dimensional version of it a near optimal soundness result is known
[MZ23].

##### Low degree tests in this paper.

In the context of the current paper, we wish to encode linear functions
$f\colon\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$, and we do so by the subspaces
encoding. Specifically, we set integer parameters $\ell_{1}\geqslant\ell_{2}$,
and encode the function $f$ using the table $T_{1}$ of the restrictions of $f$
to all $\ell_{1}$-dimensional linear subspaces of $\mathbb{F}_{q}^{n}$, and
the table $T_{2}$ of the restrictions of $f$ to all $\ell_{2}$-dimensional
linear subspaces of $\mathbb{F}_{q}^{n}$. The test we consider is the natural
inclusion test:

  1. 1.

Sample a random $\ell_{1}$-dimensional subspace
$L_{1}\subseteq\mathbb{F}_{q}^{n}$ and a random $\ell_{2}$-dimensional
subspace $L_{2}\subseteq L_{1}$.

  2. 2.

Read $T_{1}[L_{1}]$, $T_{2}[L_{2}]$ and accept if they agree on $L_{2}$.

As is often the case, the completeness of the test – namely the fact that
valid tables $T_{1},T_{2}$ pass the test with probability $1$ – is clear. The
question of most interest then is with regards to the soundness of the test.
Namely, what is the smallest $\varepsilon$ such that any two tables $T_{1}$
and $T_{2}$ that assign linear functions to subspaces and pass the test with
probability $\varepsilon$, must necessarily “come from” a legitimate linear
function $f$?

##### Traditional notion of soundness.

As the alphabet vs soundness tradeoff is key to the discussion herein, we
begin by remarking that the alphabet size of the above encoding is
$q^{\ell_{1}}+q^{\ell_{2}}=\Theta(q^{\ell_{1}})$ (since there are $q^{\ell}$
distinct linear functions on a linear space of dimension $\ell$ over
$\mathbb{F}_{q}$). Thus, ideally we would like to show that the soundness
error of the above test is $q^{-(1-o(1))\ell_{1}}$. Alas, this is false.
Indeed, it turns out that one may construct assignments that pass the test
with probability at least $\Omega(\max(q^{-\ell_{2}},q^{\ell_{2}-\ell_{1}}))$
that do not have significant correlation with any linear function $f$:

  1. 1.

Taking $T_{1},T_{2}$ randomly by assigning to each subspace a random linear
function, one can easily see that the test passes with probability
$\Theta(q^{-\ell_{2}})$.

  2. 2.

Taking linear subspaces
$W_{1},\ldots,W_{100q^{\ell_{1}}}\subseteq\mathbb{F}_{q}^{n}$ of co-dimension
$1$ randomly, and a random linear function $f_{i}\colon
W_{i}\to\mathbb{F}_{q}$ for each $i$, one may choose $T_{1}$ and $T_{2}$ as
follows. For each $L_{1}$, pick a random $i$ such that $L_{1}\subseteq W_{i}$
(if such $i$ exists) and assign $T_{1}[L_{1}]=f_{i}|_{L_{1}}$. For each
$L_{2}$, pick a random $i$ such that $L_{2}\subseteq W_{i}$ (if such $i$
exists) and assign $T_{2}[L_{2}]=f_{i}|_{L_{2}}$. Taking $L_{2}\subseteq
L_{1}$ randomly, one sees that with constant probability $L_{2}$ has
$\Theta(q^{\ell_{1}-\ell_{2}})$ many possible $i$’s, $L_{1}$ has $\Theta(1)$
many possible $i$’s and furthermore there is at least one $i$ that is valid
for both of them. With probability $\Omega(q^{\ell_{2}-\ell_{1}})$ this common
$i$ is chosen for both $L_{1}$ and $L_{2}$, and in this case, the test on
$(L_{1},L_{2})$ passes. It follows that, in expectation, $T_{1},T_{2}$ pass
the test with probability $\Omega(q^{\ell_{2}-\ell_{1}})$.

In light of the above, it makes sense that the best possible alphabet vs
soundness tradeoff we may achieve with the subspace encoding is by taking
$\ell_{2}=\ell_{1}/2$. Such a setting of the parameters would give alphabet
size $R=q^{\ell_{1}}$ and (possibly) soundness error $\Theta(1/\sqrt{R})$.
There are several issues with this setting however. First, this tradeoff is
not good enough for our purposes (which already rules out this setting of
parameters). Second, we do not know how to prove that the soundness error of
the test is $\Theta(1/\sqrt{R})$ (the best we can do is quadratically off and
is $\Theta(1/R^{1/4})$). To address both of these issues, we must venture
beyond the traditional notion of soundness.

##### Non-traditional notion of soundness.

The above test was first considered in the context of the $2$-to-$1$ Games
Theorem, wherein one takes $q=2$ and $\ell_{2}=\ell_{1}-1$. In this setting,
the test is not sound in the traditional sense; instead, the test is shown to
satisfy a non-standard notion of soundness, which nevertheless is sufficient
for the purposes of constructing a PCP. More specifically, in [KMS23] it is
proved that for all $\varepsilon>0$ there is $r\in\mathbb{N}$ such that for
sufficiently large $\ell$ and for tables $T_{1},T_{2}$ as above, there are
subspaces $Q\subseteq W\subseteq\mathbb{F}_{q}^{n}$ with ${\sf dim}(Q)+{\sf
codim}(W)\leqslant r$ and a linear function $f\colon W\to\mathbb{F}_{q}$ such
that

$\Pr_{Q\subseteq L_{1}\subseteq W}[T_{1}[L_{1}]\equiv
f|_{L_{1}}]\geqslant\varepsilon^{\prime}(\varepsilon)>0.$

We refer to the set

$\\{L\subseteq\mathbb{F}_{q}^{n}~{}|~{}{\sf dim}(L)=\ell_{1},Q\subseteq
L\subseteq W\\}$

as the zoom in of $Q$ and zoom out of $W$. While this result is good for the
purposes of $2$-to-$1$ Games, the dependency between $\ell$ and $\varepsilon$
(and thus, between the soundness and the alphabet size) is still not good
enough for us.

##### Our low-degree test.

It turns out that the proper setting of parameters for us is
$\ell_{2}=(1-\delta)\ell_{1}$ where $\delta>0$ is a small constant. With these
parameters, we are able to show that for $\varepsilon\geqslant
q^{-(1-\delta^{\prime})\ell_{1}}$ (where
$\delta^{\prime}=\delta^{\prime}(\delta)>0$ is a vanishing function of
$\delta$), if $T_{1}$, $T_{2}$ pass the test with probability at least
$\varepsilon$, then there are subspaces $Q\subseteq W$ with ${\sf dim}(Q)+{\sf
codim}(W)\leqslant r=r(\delta)\in\mathbb{N}$, and a linear function $f\colon
W\to\mathbb{F}_{q}$ such that

$\Pr_{Q\subseteq L_{1}\subseteq W}[T_{1}[L_{1}]\equiv
f|_{L_{1}}]\geqslant\varepsilon^{\prime}(\varepsilon)=\Omega(\varepsilon).$

Working in the very small soundness regime of $\varepsilon\geqslant
q^{-(1-\delta^{\prime})\ell_{1}}$ entails with it many challenges, however.
First, dealing with such small soundness requires us to use a strengthening of
the global hypercontractivity result of [KMS23] in the form of an optimal
level $d$ inequality due to Evra, Kindler and Lifshitz [EKL24]. Second, in the
context of [KMS23], $\varepsilon^{\prime}$ could be any function of
$\varepsilon$ (and indeed it ends up being a polynomial function of
$\varepsilon$). In the context of the current paper, it is crucial that
$\varepsilon^{\prime}=\varepsilon^{1+o(1)}$, as opposed to, say,
$\varepsilon^{\prime}=\varepsilon^{1.1}$. The reason is that, as we are
dealing with very small $\varepsilon$, the result would be trivial for
$\varepsilon^{\prime}=\varepsilon^{1.1}$ and not useful towards the analysis
of the PCP (as then $\varepsilon^{\prime}$ would be below the threshold
$q^{-\ell_{1}}$ which represents the agreement a random linear function $f$
has with $T_{1}$).

####  1.2.2 Getting List Decoding Bounds

As is usually the case in PCP reductions, we require a list decoding version
for our low-degree test. Indeed, using a standard argument we are able to show
that in the setting that $\ell_{2}=(1-\delta)\ell_{1}$ and
$\varepsilon\geqslant q^{(1-\delta^{\prime})\ell_{1}}$, there is
$r=r(\delta,\delta^{\prime})\in\mathbb{N}$ such that for at least
$q^{-\Theta(\ell_{1})}$ fraction of subspaces $Q\subseteq\mathbb{F}_{q}^{n}$
of dimension $r$, there exists a subspace $W$ with co-dimension at most $r$
and $Q\subseteq W\subseteq\mathbb{F}_{q}^{n}$, as well as a linear function
$f\colon W\to\mathbb{F}_{q}$, such that

$\Pr_{Q\subseteq L_{1}\subseteq W}[T_{1}[L_{1}]\equiv
f|_{L_{1}}]\geqslant\varepsilon^{\prime}(\varepsilon)=\Omega(\varepsilon).$
(1)

This list decoding version theorem alone is not enough. In our PCP
construction, we compose the inner PCP with an outer PCP (that we describe
below), and analyzing the composition requires decoding global linear
functions (from a list decoding version theorem as above) in a coordinated
manner between two non communicating parties. Often times, the number of
possible global functions that may be decoded is constant, in which case
randomly sampling one among them often works. This is not the case for us,
though: if $(Q,W)$ and $(Q^{\prime},W^{\prime})$ are distinct zoom-in and
zoom-out pairs for which there are linear functions $f_{Q,W}$ and
$f_{Q^{\prime},W^{\prime}}$ satisfying (1), then the functions $f_{Q,W}$ and
$f_{Q^{\prime},W^{\prime}}$ could be completely different. Thus, to achieve a
coordinated decoding procedure, we must:

  1. 1.

Facilitate a way for the two parties to agree on a zoom-in and zoom-out pair
$(Q,W)$ with noticeable probability.

  2. 2.

Show that for each $(Q,W)$ there are at most ${\sf poly}(1/\varepsilon)$
functions $f_{Q,W}$ for which

$\Pr_{Q\subseteq L_{1}\subseteq W}[T_{1}[L_{1}]\equiv
f_{Q,W}|_{L_{1}}]\geqslant\varepsilon^{\prime}.$

The second item is precisely the reason we need $\varepsilon^{\prime}$ to be
$\varepsilon^{1+o(1)}$; any worse dependency, such as
$\varepsilon^{\prime}=\varepsilon^{1.1}$ would lead to the second item being
false. We also remark that the number of functions being ${\sf
poly}(1/\varepsilon)$ is important to us as well. There is some slack in this
bound, but a weak quantitative bound such as ${\sf exp}({\sf
exp}(1/\varepsilon))$ would have been insufficient for some of our
applications. Luckily, such bounds can be deduced from [GRS00] for the case of
linear functions.333In the case of higher degree functions (even quadratic
functions) some bounds are known [Gop13, BL15] but they would not have been
good enough for us.

We now move onto the first item, in which we must facilitate a way for two
non-communicating parties to agree on a zoom-in and zoom-out pair $(Q,W)$. It
turns out that agreeing on the zoom-in $Q$ can be delegated to the outer PCP,
and we can construct a sound outer PCP game in which the two parties are
provided with a coordinated zoom-in $Q$. This works because in our list
decoding theorem, the fraction of zoom-ins $Q$ that work is significant.
Coordinating zoom-outs is more difficult, and this is where much of the
novelty in our analysis lies.

####  1.2.3 Coordinating Zoom-outs

For the sake of simplicity and to focus on the main ideas, we ignore zoom-ins
for now and assume that the list decoding statement holds with no $Q$. Thus,
the list decoding theorem asserts that there exists a zoom-out $W$ of constant
co-dimension on which there is a global linear function. However, there could
be many such zoom-outs $W$, say $W_{1},\ldots,W_{m}$ and say all of them were
of co-dimension $r=O_{\delta,\delta^{\prime}}(1)$. If the number $m$ were
sufficiently large – say at least $q^{-{\sf poly}(\ell_{1})}$ fraction of all
co-dimension $r$ subspaces – then we would have been able to coordinate them
in the same way as we coordinate zoom-ins. If the number $m$ were sufficiently
small – say $m=q^{{\sf poly}(\ell_{1})}$, then randomly guessing a zoom-out
would work well enough. The main issue is that the number $m$ is intermediate,
say $m=q^{\sqrt{n}}$.

This issue had already appeared in [KMS17, DKK+18]. Therein, this issue is
resolved by showing that if there are at least $m\geqslant
q^{100\ell_{1}^{2}}$ zoom-outs $W_{1},\ldots,W_{m}$ of co-dimension $r$, and
linear functions $f_{1},\ldots,f_{m}$ on $W_{1},\ldots,W_{m}$ respectively
such that

$\Pr_{L\subseteq W_{i}}[T[L]\equiv f_{i}|_{L}]\geqslant\varepsilon^{\prime}$

for all $i$, then there exists a zoom out $W$ of co-dimension _strictly less
than $r$_ and a linear function $f\colon W\to\mathbb{F}_{q}$ such that

$\Pr_{L\subseteq W}[T[L]\equiv f|_{L}]\geqslant\Omega(\varepsilon^{\prime
12}).$

Thus, if there are too many zoom-outs of a certain co-dimension, then there is
necessarily a zoom-out of smaller co-dimension that also works. In that case,
the parties could go up to that co-dimension.

This result is not good enough for us, due to the polynomial gap between the
agreement between and $f_{i}$’s and $F$ and the agreement between $f$ an $T$.
Indeed, in our range of parameters, $\varepsilon^{\prime 12}$ will be below
the trivial threshold $q^{-\ell_{1}}$ which is the agreement a random linear
function $f$ has with $T$, and therefore the promise on the function $f$ above
is meaningless.

We resolve this issue by showing a stronger, essentially optimal version of
the above assertion still holds. Formally, we prove:

######  Lemma 1.7.

For all $\delta>0$, $r\in\mathbb{N}$ there is $C>1$ such that the following
holds for $\varepsilon^{\prime}\geqslant q^{(1-\delta)\ell_{1}}$. Suppose that
$F$ is a table that assigns to each subspace $L$ of dimension $\ell_{1}$ a
linear function, and suppose that there are at least $m\geqslant
q^{C\ell_{1}}$ subspaces $W_{1},\ldots,W_{m}$ of co-dimension $r$ and linear
functions $f_{i}\colon W_{i}\to\mathbb{F}_{q}$ such that

$\Pr_{L\subseteq W_{i}}[T[L]\equiv f_{i}|_{L}]\geqslant\varepsilon^{\prime}$

for all $i=1,\ldots,m$. Then, there exists a zoom-out $W$ of co-dimension
strictly smaller than $r$ and a linear function $f\colon W\to\mathbb{F}_{q}$
such that

$\Pr_{L\subseteq W}[T[L]\equiv f|_{L}]\geqslant\Omega(\varepsilon^{\prime}).$

We defer a detailed discussion about Lemma 1.7 and its proof to Section 8, but
remark that our proof of Lemma 1.7 is very different from the arguments in
[DKK+18] and is significantly more involved. Our proof uses tools from [KMS17,
DKK+18], tools from the analysis of the classical Plane vs Plane and direct
product testing [RS97, IKW12, MZ23], global hypercontractivity [EKL24] as well
as Fourier analysis over the Grassmann graph.

####  1.2.4 The Outer PCP

Our outer PCP game is the outer PCP of [KMS17, DKK+18], which is a smooth
parallel repetition of the equation versus variables game of Hastad [Hås01]
(or of [KP06] for the application to Quadratic Programming). As in there, we
equip this game with the “advice” feature to facilitate zoom-in coordination
(as discussed above). For the sake of completeness we elaborate on the
construction of the outer PCP below.

We start with an instance of $3$-Lin that has a large gap between the
soundness and completeness. Namely, we start with an instance $(X,E)$ of
linear equations over $\mathbb{F}_{q}$ in which each equation has the form
$ax_{i_{1}}+bx_{i_{2}}+cx_{i_{3}}=d$. It is known [Hås01] that for all
$\eta>0$, it is NP-hard to distinguish between the following two cases:

  1. 1.

YES case: ${\sf val}(X,E)\geqslant 1-\eta$.

  2. 2.

NO case: ${\sf val}(X,E)\leqslant\frac{1.1}{q}$.

Given the instance $(X,E)$, we construct a $2$-Prover-$1$-Round game, known as
the smooth equation versus variable game with $r$-advice as follows. The
verifier has a smoothness parameter $\beta>0$ and picks a random equation $e$,
say $ax_{i_{1}}+bx_{i_{2}}+cx_{i_{3}}=d$, from $(X,E)$. Then:

  1. 1.

With probability $1-\beta$ the verifier takes
$U=V=\\{x_{i_{1}},x_{i_{2}},x_{i_{3}}\\}$ and vectors
$u_{1}=v_{1},\ldots,u_{r}=v_{r}\in\mathbb{F}_{q}^{U}$ sampled uniformly and
independently.

  2. 2.

With probability $\beta$, the verifier sets
$U=\\{x_{i_{1}},x_{i_{2}},x_{i_{3}}\\}$, chooses a set consisting of a single
variable $V\subseteq U$ uniformly at random. The verifier picks
$v_{1},\ldots,v_{r}\in\mathbb{F}_{q}^{V}$ uniformly and independently and
appends to each $v_{i}$ the value $0$ in the coordinates of $U\setminus V$ to
get $u_{1},\ldots,u_{r}$.

After that, the verifier sends $U$ and $u_{1},\ldots,u_{r}$ to the first
prover and $V$ and $v_{1},\ldots,v_{r}$ to the second prover. The verifier
expects to get from them $\mathbb{F}_{q}$ assignments to the variables in $U$
and in $V$, and accepts if and only if these assignments are consistent, and
furthermore the assignment to $U$ satisfies the equation $e$.

Denoting the equation versus variable game by ${\sf\Psi}$, it is easy to see
that if ${\sf val}(X,E)\geqslant 1-\eta$, then ${\sf val}(\Psi)\geqslant
1-\eta$, and if ${\sf val}(X,E)\leqslant 1.1/q$, then ${\sf
val}(\Psi)\leqslant 1-\Omega(q^{-r}\beta)$. The gap between $1-\eta$ and
$1-\Omega(q^{-r}\beta)$ is too weak for us, and thus we apply parallel
repetition.

In the parallel repetition of the smooth equation versus variable game with
advice, denoted by $\Psi^{\otimes k}$, the verifier picks $k$ equations
uniformly and independently $e_{1},\ldots,e_{k}$, and picks $U_{i}$,
$u_{1,i},\ldots,u_{r,i}$ and $V_{i}$, $v_{1,i},\ldots,v_{r,i}$ for each
$i=1,\ldots,k$ from $e_{i}$ independently. Thus, the questions of the provers
may be seen as $U=U_{1}\cup\ldots\cup U_{k}$ and $V=V_{1}\cup\ldots\cup V_{k}$
and their advice is
$\vec{u}_{j}=(u_{j,1},\ldots,u_{j,k})\in\mathbb{F}_{q}^{U}$ for $j=1,\ldots,r$
and $\vec{v}_{j}=(v_{j,1},\ldots,v_{j,k})\in\mathbb{F}_{q}^{V}$ for
$j=1,\ldots,r$ respectively. The verifier expects to get from the first prover
a vector in $\mathbb{F}_{q}^{U}$ which specifies an $\mathbb{F}_{q}$
assignment to $U$, and from the second prover a vector in $\mathbb{F}_{q}^{V}$
specifying an $\mathbb{F}_{q}$ assignment to $V$. The verifier accepts if and
only if these assignments are consistent and the assignment of the first
prover satisfies all of $e_{1},\ldots,e_{k}$. It is clear that if ${\sf
val}(X,E)\geqslant 1-\eta$, then ${\sf val}(\Psi^{\otimes m})\geqslant
1-k\eta$. Using the parallel repetition theorem of Rao [Rao11] (albeit not in
a completely trivial way) we argue that if ${\sf
val}(X,E)\leqslant\frac{1.1}{q}$, then ${\sf val}(\Psi^{\otimes k})\leqslant
2^{-\Omega(\beta q^{-r}k)}$. The game $\Psi^{\otimes k}$ is our outer PCP
game.

######  Remark 1.8.

We remark that in the case of the Quadratic Programming application, we
require a hardness result in which the completeness is very close to $1$ in
the form of Theorem 2.1. The differences between the reduction in that case
and the reduction presented above are mostly minor, and amount to picking the
parameters a bit differently. There is one significant difference in the
analysis; we require a much sharper form of the “covering property” used in
[KMS17, DKK+18], as elaborated on in Section 1.2.6

####  1.2.5 Composing the Outer PCP and the Inner PCP Game

To compose the outer and inner PCPs, we take the outer PCP game, only keep the
questions $U$ to the first prover and consider an induced $2$-Prover-$1$-Round
game on it. The alphabet is $\mathbb{F}_{q}^{3k}$, that given a question $U$
specifies an $\mathbb{F}_{q}$ assignment to the variables of $U$. There is a
constraint between $U$ and $U^{\prime}$ if there is a question $V$ to the
second prover such that $V\subseteq U\cap U^{\prime}$. Denoting the
assignments to $U$ and $U^{\prime}$ by $s_{U}$ and $s_{U^{\prime}}$, the
constraint between $U$ and $U^{\prime}$ is that $s_{U}$ satisfies all of the
equations that form $U$, $s_{U^{\prime}}$ satisfies all of the equations that
form $U^{\prime}$, and $s_{U}$, $s_{U^{\prime}}$ agree on $U\cap U^{\prime}$.

The composition amounts to replacing each question $U$ with a copy of our
inner PCP. Namely, we identify between the question $U$ and the space
$\mathbb{F}_{q}^{U}$, and then replace $U$ by a copy of the
$\ell_{2},\ell_{1}$ sub-spaces graph of $\mathbb{F}_{q}^{U}$. The answer
$s_{U}$ is naturally identified with the linear function $f_{U}(x)=\langle
s_{U},x\rangle$, which is then encoded by the sub-spaces encoding via tables
of assignments $T_{1,U}$ and $T_{2,U}$.

The constraints of the composed PCP must check that: (1) side conditions: the
encoded vector $s_{U}$ satisfies the equations of $U$, and (2) consistency:
$s_{U}$ and $s_{U^{\prime}}$ agree on $U\cap U^{\prime}$.

The first set of constraints is addressed by the folding technique, which we
omit from this discussion. The second set of constraints is addressed by the
$\ell_{1}$ vs $\ell_{2}$ subspace test, except that we have to modify it so
that it works across blocks $U$ and $U^{\prime}$. This completes the
description of the composition step of the other PCP and the inner PCP, and
thereby the description of our reduction.

####  1.2.6 The Covering Property

We end this introductory section by discussing the covering property. The
covering property is an important feature of our outer PCP construction which
enables the composition step to go through. The covering property first
appeared in [KS13] and later more extensively in the context of the $2$-to-$1$
Games [KMS17, DKK+18]. To discuss the covering property, let $k\in\mathbb{N}$
be thought of as large, let $\beta\in(0,1)$ be thought of as $k^{-0.99}$ and
consider sets $U_{1},\ldots,U_{k}$ consisting of distinct element, each
$U_{i}$ has size $3$ (in our context, $U_{i}$ will be the set of variables in
the $i$th equation the verifier chose). Let $U=U_{1}\cup\ldots\cup U_{k}$, and
consider the following two distributions over tuples in $\mathbb{F}_{q}^{U}$:

  1. 1.

Sample $x_{1},\ldots,x_{\ell}\in\mathbb{F}_{q}^{U}$ uniformly.

  2. 2.

For each $i$ independently, take $V_{i}=U_{i}$ with probability $1-\beta$ and
otherwise take $V_{i}\subseteq U_{i}$ randomly of size $1$, then set
$V=V_{1}\cup\ldots\cup V_{k}$. Sample
$x_{1},\ldots,x_{\ell}\in\mathbb{F}_{q}^{V}$ uniformly and lift them to points
in $\mathbb{F}_{q}^{U}$ by appending $0$’s in $U\setminus V$. Output the
lifted points.

In [KMS17] it is shown that the two distributions above are
$q^{3\ell}\beta\sqrt{k}$ close in statistical distance, which is good enough
for the purposes of Theorem 1.3. However, this is not good enough for Theorem
1.4. 444 The reason is that letting $N$ be the size of the instance we
produce, it holds that $k$ is roughly logarithmic $\log N$ and $q^{\ell}$ is
the alphabet size. To have small statistical distance, we must have
$k\leqslant q^{6\ell}$, hence the soundness error could not go lower than
$(\log N)^{-1/6}$. Carrying out a different analysis, we are able to show that
the two distributions are close with better parameters and in a stronger
sense: there exists a set $E$ of $\ell$ tuples which has negligible measure in
both distributions, such that each tuple not in $E$ is assigned the same
probability under the two distribution up to factor $(1+o(1))$. We are able to
prove this statement provided that $k$ is only slightly larger than
$q^{2\ell}$.

The issue with the above two distributions is that they are actually far from
each other if, say, $k=q^{1.9\ell}$. To see that, one can notice that the
expected number of $i$’s such that each one of $x_{1},\ldots,x_{\ell}$ has the
form $(a,0,0)\in\mathbb{F}_{q}^{3}$ on coordinates corresponding to $U_{i}$ is
very different. In the first distribution, this expectation is
$\Theta(q^{-2\ell}k)$ which is less than 1, whereas in the second distribution
it is at least $\beta k\geqslant k^{0.01}$.

To resolve this issue and to go all the way through in the Quadratic
Programming application, we have to modify the distributions in the covering
property so that (a) they will be close even if $k=q^{1.01\ell}$, and (b) we
can still use these distributions in the composition step in our analysis of
the PCP construction. Indeed, this is the route we take, and the two
distributions we use are defined as follows:

  1. 1.

Sample $x_{1},\ldots,x_{\ell}\in\mathbb{F}_{q}^{U}$ uniformly.

  2. 2.

For each $i$ independently, take $V_{i}=U_{i}$ with probability $1-\beta$ and
otherwise take $V_{i}\subseteq U_{i}$ randomly of size $1$, then set
$V=V_{1}\cup\ldots\cup V_{k}$. Sample
$x_{1},\ldots,x_{\ell}\in\mathbb{F}_{q}^{V}$ uniformly, and let
$w_{i}=1_{U_{i}}\in\mathbb{F}_{q}^{U}$ be the vector that has $1$ on
coordinates of $U_{i}$ and $0$ everywhere else. Lift the points
$x_{1},\ldots,x_{\ell}$ to
$x_{1}^{\prime},\ldots,x_{\ell}^{\prime}\in\mathbb{F}_{q}^{U}$ by appending
$0$’s in $U\setminus V$ and take
$y_{j}=x_{j}+\sum\limits_{i=1}^{k}\alpha_{i,j}w_{i}$ where $\alpha_{i,j}$ are
independent random elements from $\mathbb{F}_{q}$. Output
$y_{1},\ldots,y_{\ell}$.

We show that for a suitable choice of $k$ and $\beta$, these distributions are
close even in the case that $k=q^{1.01\ell}$. 555More speifically, one takes a
small $c>0$ and chooses $\beta=k^{2c/3-1}$, $k=q^{(1+c)\ell}$. Indeed, as a
sanity check one could count the expected number of appearances of blocks of
the form $(0,a,0)\in\mathbb{F}^{3}$ and see they are very close ($q^{-2\ell}k$
versus $(1-\beta)q^{-2\ell}k+\beta kq^{-\ell}$). In this setting of
parameters, $k$ is roughly equal to the alphabet size – which can be made to
be equal $(\log N)^{1-o(1)}$ under quasi-polynomial time reductions – it is
sufficient to get the result of Theorem 1.4.

######  Remark 1.9.

We remark that a tight covering property is crucial for obtaining the tight
hardness of approximation factor in Theorem 1.4. In the reduction from
$2$-Prover-$1$-Round games to Quadratic Programs, which is due to [ABH+05],
the size of the resulting instance is exponential in the alphabet size and the
soundness error remains roughly the same. In our case the alphabet size is
roughly $k$ hence the instance size is dominated by
$N=2^{\Theta(k^{1+o(1)})}$. If our analysis required $k=q^{C\ell}$, then even
showing an optimal soundness of $q^{-(1-o(1))\ell}$ for the
$2$-Prover-$1$-Round game would only yield a factor of $(\log N)^{1/C-o(1)}$
hardness for quadratic programming.

##  2 Preliminaries

###  2.1 The Grassmann Graph

In this section we present the Grassmann graph and some Fourier analytic tools
on it that are required for our analysis of the inner PCP. Throughout this
section, we fix parameters $n,\ell$ with $1\ll\ell\ll n$, and a prime power
$q$.

####  2.1.1 Basic Definitions

The Grassmann graph ${\sf Grass}_{q}(n,\ell)$ is defined as follows.

  * •

The vertex set corresponds to the set of $\ell$-dimensional subspaces
$L\subseteq\mathbb{F}_{q}^{n}$.

  * •

The edge set corresponds to all pairs $(L,L^{\prime})$ of $\ell$-dimensional
subspaces $L,L^{\prime}\subseteq\mathbb{F}_{q}^{n}$ such that $\dim(L\cap
L^{\prime})=\ell-1$.

At times we will have a vector space $V$ over $\mathbb{F}_{q}$, and thus we
may identify $V$ with $\mathbb{F}_{q}^{n}$ and work with the Grassmann graph
on the $\ell$-dimensional subspaces $L\subseteq V$. We may also use ${\sf
Grass}_{q}(V,\ell)$ to denote this graph, which is isomporphic to ${\sf
Grass}_{q}(n,\ell)$ if $\dim(V)=n$. Abusing notation, we also use ${\sf
Grass}_{q}(n,\ell)$ to denote the set of all $\ell$-dimensional subspaces in
$\mathbb{F}_{q}^{n}$. Throughout, we denote by $L_{2}({\sf
Grass}_{q}(n,\ell))$ the set of complex valued functions
$F\colon\begin{bmatrix}{\mathbb{F}_{q}^{n}}\\\
{\ell}\end{bmatrix}_{q}\to\mathbb{C}$.

The number of $\ell$-dimensional subspaces of $\mathbb{F}_{q}^{n}$ is counted
by the Gaussian binomial coefficient, $\begin{bmatrix}{n}\\\
{\ell}\end{bmatrix}_{q}$. The following standard fact gives a formula for the
Gaussian binomial coefficients, and we omit the proof.

######  Fact 2.1.

Suppose $1\leqslant\ell\leqslant\frac{n}{2}$, then the number of vertices in
${\sf Grass}_{q}(n,\ell)$ is given by

$\begin{bmatrix}{n}\\\
{\ell}\end{bmatrix}_{q}=\prod_{i=0}^{\ell-1}\frac{q^{n}-q^{i}}{q^{\ell}-q^{i}}.$

Abusing notations, we denote by $\begin{bmatrix}{V}\\\
{\ell}\end{bmatrix}_{q}$ the set of $\ell$ dimensional subspaces of $V$.

##### Zoom ins and Zoom outs.

A feature of the Grassmann graph is that it contains many copies of lower
dimensional Grassmann graphs as induced subgraphs. These subgraphs are
precisely the zoom-ins and and zoom-outs referred to in the introduction, and
they play a large part in the analysis of our inner PCP and final PCP. For
subspaces $Q\subseteq W\subseteq\mathbb{F}_{q}^{n}$, let

${\sf Zoom}[Q,W]=\\{L\in{\sf Grass}_{q}(n,\ell)\;|\;Q\subseteq L\subseteq
W\\}.$

We refer to $Q$ as a zoom-in and $W$ as a zoom-out. When
$W=\mathbb{F}_{q}^{n}$, ${\sf Zoom}[Q,W]$ is the zoom-in on $Q$, and when
$Q=\\{0\\}$, ${\sf Zoom}[Q,W]$ is the zoom-out on $W$.

####  2.1.2 Pseudo-randomness over the Grassmann graph

One notion that will be important to us is $(r,\varepsilon)$-pseudo-
randomness, which measures how much $F$ can deviate from its expectation on a
zoom-in/zoom-out restrictions of “size $r$”. For all of our applications, $F$
and $G$ will both be indicator functions of some sets of vertices, so it will
be helpful to think of this case for the remainder of the section. 666We
remark that the results we state have more general versions that apply to
wider classes of functions. We refrain from stating them in this generality
for sake of simplicity. Let $\mu(F)=\mathop{\mathbb{E}}_{L\in{\sf
Grass}_{q}(n,\ell)}[F(L)]$ (for indicator functions, this is simply the
measure of the indicated set). For subspaces $Q\subseteq
W\subseteq\mathbb{F}_{q}^{n}$, define

$\mu_{Q,W}(F)=\mathop{\mathbb{E}}_{L\in{\sf
Grass}_{q}(n,\ell)}[F(L)\;|\;Q\subseteq L\subseteq W].$

######  Definition 2.2.

We say that a Boolean function $F\colon G(n,\ell)\to\\{0,1\\}$ is
$(r,\varepsilon)$-pseudo-random if for all $Q\subseteq
W\subseteq\mathbb{F}_{q}^{n}$ satisfying $\dim(Q)+\operatorname{codim}(W)=r$,
we have

$\mu_{Q,W}(F)\leqslant\varepsilon.$

We will often say that a set $S\subseteq{\sf Grass}_{q}(n,\ell)$ is
$(r,\varepsilon)$-pseudo-random if its indicator function is. Because the
Grassmann graph is not a small-set expanders, there are small sets in it that
do not look “random” with respect to some combinatorial counting measures
(such as edges between sets, expansion and so on). Intuitively, a small set
$S$ which is highly pseudo-random will exhibit random-like structure with
respect to several combinatorial measures of interest, and the two lemmas
below are instantiations of it required in our proof. The proof proceed by
reducing them to similar statements about the Bi-linear scheme, which can then
be proved directed by appealing to global hypercontractivity results of
[EKL23, EKL24].

For the analysis of the inner PCP, we require the following lemma, which
bounds the number of edges between $\mathcal{L}\subseteq{\sf
Grass}_{q}(n,2\ell)$ and ${\sf Grass}_{q}(n,2(1-\delta)\ell)$ when
$\mathcal{L}$ is $(r,\varepsilon)$-pseudo-random.

######  Lemma 2.3.

Let $F\colon\operatorname{{\sf Grass}}_{q}(n,2\ell)\to\\{0,1\\}$ and
$G\colon\operatorname{{\sf Grass}}_{q}(n,2(1-\delta)\ell)\to\\{0,1\\}$ be
Boolean functions such that $\mathop{\mathbb{E}}_{L}[F(L)]=\alpha$,
$\mathop{\mathbb{E}}_{R}[G(R)]=\beta$, and suppose that $F$ is
$(r,\varepsilon)$ pseudo-random. Then for all $t\geqslant 4$ that are powers
of $2$,

$\langle\mathcal{T}F,G\rangle\leqslant
q^{O_{t,r}(1)}\beta^{(t-1)/t}\varepsilon^{2t/(2t-1)}+q^{-r\delta\ell}\sqrt{\alpha\beta}.$

###### Proof.

Deferred to Section A ∎

We also need the following lemma, asserting that if a not-too-small set $S$ is
highly pseudo-random, then its density remains nearly the same on all zoom-
ins.

######  Lemma 2.4.

For all $\xi>0$, the following holds for sufficiently large $\ell$. Suppose
that $\ell^{\prime}\geqslant\frac{\xi}{3}\ell$, $\delta_{2}=\frac{\xi}{100}$,
and let $V^{\star}$ be a subspace such that
$\dim(V^{\star})\geqslant\ell^{\prime 2}$. Let
$\mathcal{L}^{\star}\subseteq{\sf Grass}_{q}(V^{\star},\ell^{\prime})$ have
measure $\mu(\mathcal{L}^{\star})=\eta\geqslant q^{-2\ell}$ and set $Z=\\{z\in
V^{\star}\;|\;|\mu_{z}(\mathcal{L}^{\star})-\eta|\leqslant\frac{\eta}{10}\\}$.
If $\mathcal{L}^{\star}$ is $(1,q^{\delta_{2}\ell/100})$-pseudo-random, then

$|Z|\geqslant\left(1-q^{\frac{\ell^{\prime}}{2}}\right)|V^{\star}|.$

###### Proof.

The proof is deferred to Appendix A.4 ∎

At times we will also use the term global to refer to sets whose indicator
functions are pseudo-random. That is, we say that a set is
$(r,\varepsilon)$-global if its indicator is $(r,\varepsilon)$-pseudo-random.

###  2.2 Hardness of 3LIN

In this section we cite several hardness of approximation results for the
problem of solving linear equations over finite fields, which are the starting
point of our reduction. We begin by defining the ${\sf 3Lin}$ and the ${\sf
Gap3Lin}$ problem.

######  Definition 2.5.

For a prime power $q$, an instance of ${\sf 3Lin}$ is $(X,{\sf Eq})$ which
consists of a set of variables $X$ and a set of linear equations ${\sf Eq}$
over $\mathbb{F}_{q}$. Each equation in ${\sf Eq}$ depends on exactly three
variables in $X$, each variable appears in at most $10$ equations, and any two
distinct equations in ${\sf Eq}$ share at most a single variable.

The goal in the ${\sf 3Lin}$ problem is to find an assignment $A\colon
X\to\mathbb{F}_{q}$ satisfying as many of the equations in $E$ as possible.
The maximum fraction of equations that can be satisfied is called the value of
the instance. We remark that usually in the literature, the condition that two
equations in $E$ share at most a single variable is not included in the
definition of ${\sf 3Lin}$, as well the the bound on the number of occurences
of each variable.

For $0<s<c\leqslant 1$, the problem ${\sf Gap3Lin}[c,s]$ is the promise
problem wherein the input is an instance $(X,E)$ of ${\sf 3Lin}$ promised to
either have value at least $c$ or at most $s$, and the goal is to distinguish
between these two cases. The problem ${\sf Gap3Lin}[c,s]$ with various
settings of $c$ and $s$ will be the starting point for our reductions.

To prove Theorem 1.3, we shall use the classical result of Håstad [Hås01].
This result says that for general ${\sf 3Lin}$ instances (i.e., without the
additional condition that two equations share at most a single variable), the
problem ${\sf Gap3Lin}[1-\varepsilon,1/q+\varepsilon]$ is NP-hard for all
constant $q\in\mathbb{N}$ and $\varepsilon>0$. This result implies the
following theorem by elementary reductions:

######  Theorem 2.1.

There exists $s<1$ such that for every constant $\eta>0$ and prime $q$, ${\sf
Gap3Lin}\left[1-\eta,s\right]$ is ${\sf NP}$-hard.

To prove Theorem 1.4 we will need a hardness result for ${\sf 3Lin}$ with
completeness close to $1$, and we will use a hardness result of Khot and
Ponnuswami [KP06]. Once again, their result does not immediately guarantee the
fact that any two equations share at most a single variable, however once
again this property may be achieved by an elementary reduction.

######  Theorem 2.2.

There is a reduction from ${\sf SAT}$ with size $n$ to a ${\sf
Gap3Lin}[1-\eta,1-\varepsilon]$ instance with size $N$ over a field
$\mathbb{F}_{q}$ of characteristic $2$, where,

  * •

Both $N$ and the running time of the reduction are bounded by
$2^{O(\log^{2}n)}$

  * •

$\eta\leqslant 2^{-\Omega(\sqrt{\log N})}$.

  * •

$\varepsilon\geqslant\Omega\left(\frac{1}{\log^{3}N}\right)$.

##  3 The Outer PCP

In this section, we describe our outer PCP game. In short, our outer PCP is a
smooth parallel repetition of the variable versus equation game with advice.
This outer PCP was first considered in [KS13] without the advice feature, and
then in [KMS17] with the advice feature.

###  3.1 The Outer PCP construction

Let $\varepsilon_{1}<\varepsilon_{2}$ be parameters that determine the
completeness and the soundness our ${\sf Gap3Lin}$. Our reduction starts with
the ${\sf Gap3Lin}[1-\varepsilon_{1},1-\varepsilon_{2}]$ problem, and we fix
an instance of it $(X,E)$ for the rest of this section. Our presentation is
gradual, and we begin by presenting the basic Variable versus Equation Game.
We then equip it with the additional features of smoothness and advice.

####  3.1.1 The Variable versus Equation Game

We first convert the instance $(X,E)$ into an instance of $2$-Prover-$1$-Round
Games, and it will be convenient for us to describe it in the active view with
a verifier and $2$ provers.

In the Variable versus Equation game, the verifier picks an equation $e\in E$
uniformly at random, and then chooses a random variable $x\in e$. The verifier
sends the question $e$, i.e. the three variables appearing in $e$, to the
first prover, and sends the variable $x$ to the second prover. The provers are
expected to answer with assignments to their received variables, and the
verifier accepts if and only if the two assignments agree on $x$ and the first
prover’s assignment satisfies the equation $e$. If the verifier accepts then
we also say that the provers pass. This game has the following completeness
and soundness, which are both easy to see (we omit the formal proof):

  1. 1.

Completeness: If $(X,E)$ has an assignment satisfying $1-\varepsilon$-fraction
of the equations, then the prover’s have a strategy that passes with
probability at least $1-\varepsilon$.

  2. 2.

Soundness: If $(X,{\sf Eq})$ has no assignment satisfying more than
$1-\varepsilon$-fraction of the equations, then the prover’s can pass with
probability at most $1-\frac{\varepsilon}{3}$.

####  3.1.2 The Smooth Equation versus Variable Game

We next describe a smooth version of the Variable versus Equation game. In
this game, the verifier has a parameter $\beta\in(0,1]$, and it proceeds as
follows:

  1. 1.

The verifier chooses an equation $e\in E$ uniformly, and lets $U$ be the set
of variables in $e$.

  2. 2.

With probability $1-\beta$, the prover chooses $V=U$. With probability
$\beta$, the prover chooses $V\subseteq U$ randomly of size $1$.

  3. 3.

The verifier sends $U$ to the first prover, and $V$ to the second prover.

  4. 4.

The provers respond with assignments to the variables they receive, and the
verifier accepts if and only if their assignments agree on $V$ and the
assignment to $U$ satisfies the equation $e$.

The smooth Variable versus Equation game has the following completeness and
soundness property, which are again easily seen to hold (we omit the formal
proof).

  1. 1.

Completeness: If $(X,E)$ has an assignment satisfying $1-\varepsilon$ fraction
of the equations, then the provers have a strategy that passes with
probability at least $1-\varepsilon$.

  2. 2.

Soundness: If $(X,{\sf Eq})$ has no assignment satisfying more than
$1-\varepsilon$ fraction of the equations, then the provers can pass with
probability at most $1-\frac{\beta\varepsilon}{3}$.

####  3.1.3 The Smooth Equation versus Variable Game with Advice

Next, we introduce the feature of advice into the smooth Variable versus
Equation Game. This “advice” acts as shared randomness which may help the
provers in their strategy; we show though that it does not considerably change
the soundness. The game is denoted by $G_{\beta,r}$ for $\beta\in(0,1]$ and
$r\in\mathbb{N}$, and proceeds as follows:

  1. 1.

The verifier chooses an equation $e\in E$ uniformly, and lets $U$ be the set
of variables in $e$.

  2. 2.

With probability $1-\beta$, the verifier chooses $V=U$. With probability
$\beta$, the verifier chooses $V\subseteq U$ randomly of size $1$.

  3. 3.

The verifier picks vectors $v_{1},\ldots,v_{r}\in\mathbb{F}_{q}^{V}$ uniformly
and independently. If $U=V$ the verifier takes $u_{i}=v_{i}$ for all $i$, and
otherwise the verifier takes the vectors
$u_{1},\ldots,u_{r}\in\mathbb{F}_{q}^{U}$ where for all $i=1,\ldots,r$, the
vector $u_{i}$ agrees with $v_{i}$ on the coordinate of $V$, and is $0$ in the
coordinates of $U\setminus V$.

  4. 4.

The verifier sends $U$ and $u_{1},\ldots,u_{r}$ to the first prover, and $V$
and $v_{1},\ldots,v_{r}$ to the second prover.

  5. 5.

The provers respond with assignments to the variables they receive, and the
verifier accepts if and only if their assignments agree on $V$ and the
assignment to $U$ satisfies the equation $e$.

Below we state the completeness and soundness of this game:

  1. 1.

Completeness: If $(X,E)$ has an assignment satisfying $1-\varepsilon$ fraction
of the equations, then the provers have a strategy that passes with
probability at least $1-\varepsilon$. This is easy to see.

  2. 2.

Soundness: If $(X,{\sf Eq})$ has no assignment satisfying more than
$1-\varepsilon$ fraction of the equations, then the provers can pass with
probability at most $1-\frac{q^{-r}\beta\varepsilon}{3}$. Indeed, suppose that
the provers can win the game with probability at least $1-\eta$. Note that
with probability at least $\beta q^{-r}$ it holds that $U\neq V$ and all the
vectors $u_{1},\ldots,u_{r}$ and $v_{1},\ldots,v_{r}$ are all $0$, in which
case the provers play the standard equation versus variable game. Thus, the
provers’ strategy wins in the latter game with probability at least
$1-\frac{\eta}{q^{-r}\beta}>1-\frac{\varepsilon}{3}$, and contradiction.

####  3.1.4 Parallel Repetition of the Smooth Equation versus Variable Game
with Advice

Finally, our Outer PCP is then the $k$-fold parallel repetition of
$G_{\beta,r}$, which we denote by $G^{\otimes k}_{\beta,r}$. Below is a full
description of it:

  1. 1.

The verifier chooses equations $e_{1},\ldots,e_{k}\in E$ uniformly and
independently, and lets $U_{i}$ be the set of variables in $e_{i}$.

  2. 2.

For each $i$ independently, with probability $1-\beta$, the verifier chooses
$V_{i}=U_{i}$. With probability $\beta$, the verifier chooses $V_{i}\subseteq
U_{i}$ randomly of size $1$.

  3. 3.

For each $i$ independently, the verifier picks a vectors
$v_{1}^{i},\ldots,v_{r}^{i}\in\mathbb{F}_{q}^{V}$ uniformly and independently.
If $U_{i}=V_{i}$ the verifier takes $u_{j}^{i}=v_{j}^{i}$ for $j=1,\ldots,r$,
and otherwise the verifier takes the vectors
$u_{1}^{i},\ldots,u_{r}^{i}\in\mathbb{F}_{q}^{U}$ where for all
$j=1,\ldots,r$, the vector $u_{j}^{i}$ agrees with $v_{j}^{i}$ on the
coordinate of $V_{i}$, and is $0$ in the coordinates of $U_{i}\setminus
V_{i}$.

  4. 4.

The verifier sets $U=\bigcup_{i=1}^{k}U_{i}$ and
$u_{j}=(u_{j}^{1},\ldots,u_{j}^{k})$ for each $j=1,\ldots r$, and
$V=\cup_{i=1}^{k}V_{i}$ and $v_{j}=(v_{j}^{1},\ldots,v_{j}^{k})$ for each
$j=1,\ldots,r$. The verifier sends $U$ and $u_{1},\ldots,u_{r}$ to the first
prover, and $V$ and $v_{1},\ldots,v_{r}$ to the second prover.

  5. 5.

The provers respond with assignments to the variables they receive, and the
verifier accepts if and only if their assignments agree on $V$ and the
assignment to $U$ satisfies the equations $e_{1},\ldots,e_{k}$.

Next, we state the completeness and the soundness of the game
$G_{\beta,r}^{\otimes k}$, and we begin with its completeness.

######  Claim 3.1.

If $(X,E)$ has an assignment satisfying at least $1-\varepsilon$ of the
equations, then the provers can win $G_{\beta,r}^{\otimes k}$ with probability
at least $1-k\varepsilon$.

###### Proof.

Let $A$ be an assignment that satisfies at least $1-\varepsilon$ fraction of
the equations in $E$, and consider the strategy of the provers that assigns
their variables according to $A$. Note that whenver each one of the equations
$e_{1},\ldots,e_{k}$ the verifier chose is satisfied by $A$, the verifier
accepts. By the union bound, the probability this happens is at least
$1-k\varepsilon$. ∎

Next, we establish the soundness of the game $G_{\beta,r}^{\otimes k}$.

######  Claim 3.2.

If there is no assignment to $(X,E)$ satisfying at least $1-\varepsilon$ of
the equations, then the provers can win $G_{\beta,r}^{\otimes k}$ with
probability at most $2^{-\Omega(\varepsilon^{2}q^{-r}\beta k)}$.

###### Proof.

We appeal to the parallel repetition theorem for projection games of Rao
[Rao11], but we have to do so carefully. That theorem states that if $\Psi$ is
a $2$-Prover-$1$-Round game with ${\sf val}(\Psi)\leqslant 1-\eta$, then ${\sf
val}(\Psi^{\otimes k})\leqslant 2^{-\Omega(\eta^{2}k)}$. We cannot apply the
theorem directly on $G_{\beta,r}$ (as the square is too costly for us).
Instead, we consider the game $\Psi=G_{\beta,r}^{\frac{q^{r}}{\beta}}$ and
note that it has value bounded away from $1$.

Write ${\sf val}(\Psi)=1-\eta$. Note that probability at least $0.1$ there
exists at least a single coordinate $i$ in which $U_{i}\neq V_{i}$ and all of
the advice vectors $v_{1}^{i},\ldots,v_{r}^{i}$ and
$u_{1}^{i},\ldots,u_{r}^{i}$ are all $0$. Thus, there exists a coordinate $i$
and a fixing for the questions of the provers outside $i$ so that the answers
of the players to the $i$th coordinate win the standard equation versus
variable game with probability at least $1-10\eta$. It follows that
$1-10\eta\leqslant 1-\frac{\varepsilon}{3}$, and so
$\eta\geqslant\frac{\varepsilon}{30}$.

We conclude from Rao’s parallel repetition theorem that

${\sf val}(G_{\beta,r}^{\otimes k})={\sf
val}(\Psi^{\otimes\frac{k}{q^{r}/\beta}})\leqslant
2^{-\Omega(\varepsilon^{2}q^{-r}\beta k)}.\qed$

##### Viewing the advice as subspaces.

Due to the fact that each variable appears in at most $O(1)$ equations, it can
easily be seen that with probability $1-O(k^{2}/n)$, all variables in
$e_{1},\ldots,e_{k}$ are distinct. In that case, note that the $r$ vectors of
advice to the second prover, $v_{1},\ldots,v_{r}\in\mathbb{F}_{q}^{V}$, are
uniform, and the second prover may consider their span $Q_{V}$. Note that the
distribution of $Q_{V}$ is that of a uniform $r$ dimensional subspace of
$\mathbb{F}_{q}^{V}$. As for the second prover, the vectors
$u_{1},\ldots,u_{r}\in\mathbb{F}_{q}^{U}$ are not uniformly distributed.
Nevertheless, as shown by the covering property from [KS13, KMS17] (and
presented below), the distribution of $u_{1},\ldots,u_{r}$ is close to uniform
over $r$-tuple of vectors from $\mathbb{F}_{q}^{U}$. Thus, the first prover
can also take their span, call it $Q_{U}$, and think of it as a random
$r$-dimensional subspace of $\mathbb{F}_{q}^{U}$ (which is highly correlated
to $Q_{V}$).

##  4 The Composed PCP Construction

In this section we describe the final PCP construction, which is a composition
of the outer PCP from Section 3 with the inner PCP based on the Grassmann
consistency test.

###  4.1 The Underlying Graph

Our instance of $2$-Prover-$1$-Round Games starts from an instance $(X,{\sf
Eq})$ of ${\sf Gap3Lin}$. Consider the game $G_{\beta,r}^{\otimes k}$ from
Section 3, and let $\mathcal{U}$ denote the set of questions asked to the
first prover. Thus $\mathcal{U}$ consists of all $k$-tuples of equations
$U=(e_{1},\ldots,e_{k})\in{\sf Eq}^{k}$ from the ${\sf Gap3Lin}$ instance
$(X,{\sf Eq})$. For $e\in{\sf Eq}$ let $v_{e}\in\mathbb{F}_{q}^{X}$ denote the
indicator vector on the three variables appearing in $e$.

It will be convenient to only keep the $U=(e_{1},\ldots,e_{k})$ that satisfy
the following properties:

  * •

The equations $e_{1},\ldots,e_{k}$ are distinct and do not share variables.

  * •

For any $i\neq j$ and pair of variables $x\in e_{i}$ and $y\in e_{j}$, the
variables $x$ and $y$ do not appear together in any equation in the instance
$(X,{\sf Eq})$.

The fraction of $U=(e_{1},\ldots,e_{k})$ that do not satisfy the above is
$O(k^{2}/n)$ which is negligible for us, and dropping them will only reduce
our completeness by $o(1)$. This will not affect our analysis, and henceforth
we will assume that all $U=(e_{1},\ldots,e_{k})$ satisfy the above properties.
We now describe the $2$-Prover-$1$-Round Games instance
$\Psi=(\mathcal{A},\mathcal{B},E,\Sigma_{1},\Sigma_{2},\Phi)$. All vertices in
the underlying graph will correspond to subspaces of $\mathbb{F}_{q}^{X}$.

####  4.1.1 The Vertices

For each question $U=(e_{1},\ldots,e_{k})$, let
$H_{U}=\operatorname{span}(v_{e_{1}},\ldots,v_{e_{k}})$, where $v_{e_{i}}$ is
the vector with ones at coordinates corresponding to variables appearing in
$e_{i}$. We can think of the $v_{e_{i}}$’s as vectors from an underlying space
$\mathbb{F}_{q}^{U}$. By the first property described above, $\dim(H_{U})=k$
and $\dim(\mathbb{F}_{q}^{U})=3k$. The vertices of $\Psi$ are:

$\displaystyle\mathcal{A}=\\{L\oplus
H_{U}\;|\;U\in\mathcal{U},L\subseteq\mathbb{F}_{q}^{U},\dim(L)=2\ell,L\cap
H_{U}=\\{0\\}\\},$ $\displaystyle\mathcal{B}=\\{R\;|\;\exists
U\in\mathcal{U},\text{ s.t.
}R\subseteq\mathbb{F}_{q}^{U},\dim(R)=2(1-\delta)\ell\\}.$

In words, the vertices on the side $\mathcal{A}$ are all $2\ell$-dimensional
subspaces of some $\mathbb{F}_{q}^{U}$ for some $U\in\mathcal{U}$. For
technical reasons, we require them to intersect $H_{U}$ trivially (which is
the case for a typical $2\ell$-dimensional space) and add to them the space
$H_{U}$.777This has the effect of collapsing $L$ and $L^{\prime}$ such that
$L\oplus H_{U}=L^{\prime}\oplus H_{U}$ to a single vertex. The vertices on the
side $\mathcal{B}$ are all $2(1-\delta)\ell$ dimensional subspaces of
$\mathbb{F}_{q}^{U}$.

####  4.1.2 The Alphabets

The alphabets $\Sigma_{1},\Sigma_{2}$ have sizes $|\Sigma_{1}|=q^{2\ell}$ and
$|\Sigma_{2}|=q^{2(1-\delta)\ell}$. For each vertex $L\oplus
H_{U}\in\mathcal{A}$, let $\psi:H_{U}\xrightarrow[]{}\mathbb{F}_{q}$ denote
the function that satisfies the side conditions given by the equations in $U$.
Namely, if $e_{i}\in U$ is the equation $\langle x,h_{i}\rangle=b_{i}$ for
$x\in\mathbb{F}_{q}^{U}$, then $\psi(h_{i})=b_{i}$. We say a linear function
$f\colon L\oplus H_{U}\to\mathbb{F}_{q}$ satisfies the side conditions of $U$
if $f|_{H_{U}}\equiv\psi$. In this language, for a vertex $L\oplus H_{U}$ we
identify $\Sigma_{1}$ with

$\\{f:L\oplus H_{U}\xrightarrow[]{}\mathbb{F}_{q}\;|\;f\text{ is linear
function satisfying the side conditions of $U$}\\}.$

As $L\cap H_{U}=\\{0\\}$ and $\dim(L)=2\ell$, it is easy to see that the above
set indeed has size $q^{2\ell}$. For each right vertex $R$, we identify
$\Sigma_{2}$ with

$\\{f:R\xrightarrow[]{}\mathbb{F}_{q}\;|\;f\text{ is linear}\\}.$

####  4.1.3 The Edges

To define the edges, we first need the following relation on the vertices in
$A$. Say that $(L\oplus H_{U})\sim(L^{\prime}\oplus H_{U^{\prime}})$ if

$L\oplus H_{U}\oplus H_{U^{\prime}}=L^{\prime}\oplus H_{U}\oplus
H_{U^{\prime}}.$

Recall that all subspaces above are in $\mathbb{F}_{q}^{X}$ hence the direct
sums and equality above are well defined. The relation described is in fact an
equivalence relation and thus partitions the vertices in $\mathcal{A}$ into
disjoint equivalence classes. It is clear that the relation is reflexive and
symmetric, so we need only show that it is also transitive.

######  Lemma 4.1.

If $L_{1}\oplus H_{U_{1}}\oplus H_{U_{2}}=L_{2}\oplus H_{U_{1}}\oplus
H_{U_{2}}$, and $L_{2}\oplus H_{U_{2}}\oplus H_{U_{3}}=L_{3}\oplus
H_{U_{2}}\oplus H_{U_{3}}$, then

$L_{1}\oplus H_{U_{1}}\oplus H_{U_{3}}=L_{3}\oplus H_{U_{1}}\oplus H_{U_{3}}.$

###### Proof.

We “add” $H_{U_{1}}$ to the second equation to obtain,

$L_{2}\oplus H_{U_{1}}\oplus H_{U_{2}}\oplus H_{U_{3}}=L_{3}\oplus
H_{U_{1}}\oplus H_{U_{2}}\oplus H_{U_{3}}.$

Next, write $H_{U_{2}}=A\oplus B$, where $A$ is the span of all vectors
$v_{e}$ for equations $e$ in $U_{2}$ that are also in $U_{1}$ or $U_{3}$,
while $B$ is the span of all vectors $v_{e}$ for equations $e\in U_{2}$ that
are in neither $U_{1}$ nor $U_{3}$. It follows that $A\cap B=\\{0\\}$. Now
note that any equation $e\in B$ has at most one variable that appears in an
equation in $U_{1}$, and at most one variable that appears in an equation in
$U_{2}$. Thus, each $e\in B$, has a “private variable”, and as the equations
in $B$ are over disjoint sets of variables, this private variable does not
appear in $U_{1}\cup U_{3}\cup(U_{2}\setminus e)$. It follows that

$B\cap L_{1}\oplus L_{3}\oplus H_{U_{1}}\oplus
H_{U_{3}}=\\{0\\}\subset\mathbb{F}_{q}^{X}.$

Indeed, by the above discussion any nonzero vector in
$B\subseteq\mathbb{F}_{q}^{X}$ is nonzero on at least one coordinate of $X$
(corresponding to a private variable), and no vector in
$\mathbb{F}_{q}^{U_{1}}$ or $\mathbb{F}_{q}^{U_{2}}$ is supported on this
coordinate.

Substituting $H_{U_{2}}=A\oplus B$ into the original equation yields,

$L_{1}\oplus(H_{U_{1}}\oplus H_{U_{3}}\oplus A)\oplus
B=L_{3}\oplus(H_{U_{1}}\oplus H_{U_{3}}\oplus A)\oplus B.$

Since $A\subset H_{U_{1}}\oplus H_{U_{3}}$, this equivalent to

$L_{1}\oplus H_{U_{1}}\oplus H_{U_{3}}\oplus B=L_{3}\oplus H_{U_{1}}\oplus
H_{U_{3}}\oplus B.$

As $B\cap L_{1}\oplus L_{3}\oplus H_{U_{1}}\oplus H_{U_{3}}=\\{0\\}$, it
follows that

$L_{1}\oplus H_{U_{1}}\oplus H_{U_{3}}=L_{3}\oplus H_{U_{1}}\oplus H_{U_{3}},$

as desired. ∎

By Lemma 4.1 the relation $\sim$ is indeed an equivalence relation and we may
partition $\mathcal{A}$ into equivalence classes, $[L\oplus H_{U}]$. We call
each class a clique and partition $\mathcal{A}$ into cliques:

$\mathcal{A}=\textsf{Clique}_{1}\sqcup\cdots\sqcup\textsf{Clique}_{m}.$

The actual number of cliques, $m$, will not be important, but it is clear that
such a number exists. The edges of our graph will be between vertices $L\oplus
H_{U}$ and $R$ if there exists $L^{\prime}\oplus H_{U^{\prime}}\in[L\oplus
H_{U}]$ such that $L^{\prime}\supseteq R$. The edges will be weighted
according to a sampling process that we describe in the next section, which
also explains the constraints on $\Psi$. For future reference, the following
lemma will be helpful in defining the constraints:

######  Lemma 4.2.

Suppose $L\oplus H_{U}\sim L^{\prime}\oplus H_{U^{\prime}}$ and that
$f:L\oplus H_{U}\xrightarrow[]{}\mathbb{F}_{q}$ is a linear function
satisfying the side conditions. Then there is a unique linear function
$f^{\prime}:L^{\prime}\oplus H_{U^{\prime}}\xrightarrow[]{}\mathbb{F}_{q}$
that satisfies the side conditions such that there exists a linear function
$g:L\oplus H_{U}\oplus H_{U^{\prime}}\xrightarrow[]{}\mathbb{F}_{q}$
satisfying the side conditions (of both $U$ and $U^{\prime}$) such that

$g|_{L\oplus H_{U}}=f\quad\text{ and }\quad g|_{L^{\prime}\oplus
H_{U^{\prime}}}=f^{\prime}.$

In words, $g$ is a linear extension of both $f$ and $f^{\prime}$.

###### Proof.

Note that there is only one way to extend $f$ to $L\oplus H_{U}\oplus
H_{U^{\prime}}$ in a manner that satisfies the side conditions given by
$U^{\prime}$. Let this function be $g$. We take $f^{\prime}$ to be
$g|_{L^{\prime}\oplus H_{U^{\prime}}}$. ∎

####  4.1.4 The Constraints

Suppose that $T_{1}$ is an assignment to $\mathcal{A}$ that assigns, to each
vertex $L\oplus H_{U}$, a linear function $T_{1}[L\oplus H_{U}]$ satisfying
the side conditions. Further suppose that $T_{2}$ is an assignment that
assigns to each vertex $R\in\mathcal{B}$ a linear function on $R$. The
verifier performs the following test, which also describes the constraints of
$\Psi$:

  1. 1.

Choose $U$ uniformly at random from $\mathcal{U}$.

  2. 2.

Choose $L\oplus H_{U}$ uniformly, where $\dim(L)=2\ell$ and $L\cap
H_{U}=\\{0\\}$, and choose $R\subseteq L$ of dimension $2(1-\delta)\ell$
uniformly.

  3. 3.

Choose $L^{\prime}\oplus H_{U^{\prime}}\in[L\oplus H_{U}]$ uniformly

  4. 4.

As in Lemma 4.2, extend $T_{1}[L^{\prime}\oplus H_{U^{\prime}}]$ to
$L^{\prime}\oplus H_{U^{\prime}}\oplus H_{U}$ in the unique manner that
respects the side conditions and let $\tilde{T}_{1}[L\oplus H_{U}]$ be the
restriction of this extension to $L\oplus H_{U}$.

  5. 5.

Accept if and only if $\tilde{T}_{1}[L\oplus H_{U}]|_{R}=T_{2}[R]$.

This finishes the description of our instance $\Psi$. It is clear that the
running time and instance size is $n^{O(k)}$ and that the alphabet size is
$O(q^{2\ell})$.

Before arguing about the completeness and soundness, we will present some
necessary tools. As is usually the case, showing completeness is relatively
easy, and all of the tools presented are for the much more complex soundness
analysis.

##  5 Tools for Soundness Analysis

In this section we will present all of the tools needed to analyze the
soundness of our PCP.

###  5.1 The $2\ell$ versus $2\ell(1-\delta)$ subspace agreement test

We begin by discussing the $2\ell$ versus $2\ell(1-\delta)$ test and our
decoding theorem for it. In our setting, we have a question $U\in\mathcal{U}$
for the first prover, and we consider the $2\ell$ versus $2\ell(1-\delta)$
test inside the space $\mathbb{F}_{q}^{U}$. In our setting this test passes
with probability at least $\varepsilon\geqslant q^{-2\ell(1-\delta^{\prime})}$
(where $\delta^{\prime}$ is, say $\delta^{\prime}=1000\delta$) and we will
want to use this fact to devise a strategy for the first prover. Below, we
first state and prove a basic decoding theorem, and then deduce from it a
quantitative better version that also incorporates the side conditions.

Let $T_{1}$ be a table that assigns, to each $L\in\operatorname{{\sf
Grass}}_{q}(\mathbb{F}_{q}^{U},2\ell)$, a linear function
$T_{1}[L]:L\xrightarrow[]{}\mathbb{F}_{q}$, and let $T_{2}$ be a table
assigning to each $R\in\operatorname{{\sf
Grass}}_{q}(\mathbb{F}_{q}^{U},2(1-\delta)\ell)$ a linear function
$T_{2}[R]\colon R\to\mathbb{F}_{q}$. We recall that $|U|=3k\gg 2\ell$. In this
section, we show that if tables $T_{1}$ and $T_{2}$ are
$\varepsilon$-consistent, namely

$\Pr_{\begin{subarray}{c}L\in\operatorname{{\sf
Grass}}_{q}(\mathbb{F}_{q}^{U},2\ell)\\\ R\in\operatorname{{\sf
Grass}}_{q}(\mathbb{F}_{q}^{U},2(1-\delta)\ell)\end{subarray}}[T_{1}[L]|_{R}=T_{2}[R]\;|\;R\subseteq
L]\geqslant\varepsilon.$

for $\varepsilon\geqslant q^{-2\ell(1-1000\delta)}$, then the table $T_{1}$
must have non-trivial agreement with a linear function on some zoom-in and
zoom-out combination of constant dimension. To prove that, we use Lemma 2.3
along with an idea from [BKS19].

######  Theorem 5.1.

Suppose that tables $T_{1}$ and $T_{2}$ are $\varepsilon$-consistent where
$\varepsilon\geqslant q^{-2(1-1000\delta)\ell}$. Then there exist subspaces
$Q\subset W$ and a linear function $f:W\xrightarrow[]{}\mathbb{F}_{q}$ such
that:

  1. 1.

$\operatorname{codim}(Q)+\dim(W)=\frac{10}{\delta}$.

  2. 2.

$f|_{L}\equiv T_{1}[L]$ for $\Omega(\varepsilon^{\prime})$-fraction of
$2\ell$-dimensional $L\in{{\sf Zoom}}[Q,W]$,

where $\varepsilon^{\prime}=q^{-2(1-1000\delta^{2})\ell}$.

###### Proof of Theorem 5.1.

Consider the bipartite graph $G$ whose sides are the vertices of ${\sf
Grass}_{q}(n,2\ell)$ and ${\sf Grass}_{q}(n,(1-\delta)2\ell)$, and its set of
edges $E$ consists of pairs $(L,R)$ such that $L\supseteq R$. Consider the
normalized adjacency operator $\mathcal{T}:L_{2}(\operatorname{{\sf
Grass}}_{q}(n,2\ell))\xrightarrow[]{}L_{2}(\operatorname{{\sf
Grass}}_{q}(n,2(1-\delta)\ell))$ of $G$, and let $\mathcal{T}^{*}$ be its
adjoint operator.

Choose a linear function $f:\mathbb{F}_{q}^{n}\xrightarrow[]{}\mathbb{F}_{q}$
uniformly at random and define the (random) sets of vertices

$S_{L,f}=\\{L\in{\sf Grass}_{q}(n,2\ell)\;|\;f|_{L}\equiv
T_{1}[L]\\}\quad\text{and}\quad S_{R,f}=\\{R\in{\sf
Grass}_{q}(n,2(1-\delta)\ell)\;|\;f|_{R}=T_{2}[R]\\}.$

Denote by $E(S_{L,f},S_{R,f})$ the set of edges with endpoints in $S_{L,f}$
and $S_{R,f}$. We lower bound the expected size of $E(S_{L,f},S_{R,f})$ over
the choice of $f$. Note that for each edge $(L,R)\in E$ such that
$T_{1}[L]|_{R}\equiv T_{2}[R]$, we have that $(L,R)\in E(S_{L,f},S_{R,f})$
with probability $q^{-2\ell}$. Indeed, with probability $q^{-2\ell}$ we have
that $T_{1}[L]\equiv f|_{L}$, and in that case we automatically get that
$T_{2}[R]=T_{1}[L]|_{R}\equiv(f|_{L})|_{R}=f|_{R}$. As the number of edges
$(L,R)$ such that $T_{1}[L]|_{R}\equiv T_{2}[R]$ is at least $\varepsilon|E|$,
we conclude that

$\mathop{\mathbb{E}}_{f}\left[\left|E(S_{L,f},S_{R,f})\right|\right]\geqslant\varepsilon
q^{-2\ell}|E|.$

Note that we also have that

$\mathop{\mathbb{E}}_{f}[\mu(S_{R,f})]=\mathop{\mathbb{E}}_{f}\left[\frac{|S_{R,f}|}{|R|}\right]=q^{-2\ell(1-\delta)}.$

Using Linearity of Expectation, we get that

$\mathop{\mathbb{E}}_{f}\left[\left|E(S_{L,f},S_{R,f})\right|-\frac{1}{2}\varepsilon
q^{2\delta\ell}\mu(S_{R,f})|E|\right]\geqslant\frac{1}{2}\varepsilon
q^{-2\ell}|E|,$

thus there exists $f$ for which the random variable on the left hand side is
at least $\frac{1}{2}\varepsilon q^{-2\ell}|E|$, and we fix $f$ so that

$\left|E(S_{L,f},S_{R,f})\right|\geqslant\frac{1}{2}\varepsilon
q^{2\delta\ell}\mu(S_{R,f})|E|+\frac{1}{2}\varepsilon q^{-2\ell}|E|.$ (2)

We claim that $S_{L,f}$ is not $(r,\varepsilon^{\prime})$-pseudo-random for
$r=\frac{10}{\delta}$ and $\varepsilon^{\prime}=q^{-2\ell(1-1000\delta^{2})}$.
Suppose for the sake of contradiction that this is not the case, and that
$S_{L,f}$ is $(r,\varepsilon^{\prime})$-pseudo-random. Denote
$\alpha=\mu(S_{L,f})$ and $\beta=\mu(S_{R,f})$. By Lemma 2.3 for any
$t\geqslant 4$ that is a power of $2$ we have

$\frac{1}{|E|}|E(S_{L},S_{R})|\leqslant
q^{O_{t,r}(1)}\beta^{\frac{t-1}{t}}\varepsilon^{\prime\frac{t-1}{t}}+5q^{-2r\delta\ell}\sqrt{\alpha\beta}\leqslant
q^{O_{t,r}(1)}\beta^{\frac{t-1}{t}}\varepsilon^{\prime\frac{t-1}{t}}.$ (3)

In the last inequality, we used the fact that by (2)

$\beta|E|=|S_{R,f}|\frac{|E|}{|R|}\geqslant|E(S_{L,f},S_{R,f})|\geqslant\frac{1}{2}\varepsilon
q^{-2\ell}|E|,$

so $\beta\geqslant\frac{1}{2}\varepsilon q^{-2\ell}\geqslant q^{-4\ell}$, and
thus the second term on the middle of (3) is negligible compared to the first
term there. Combining (2) and (3) gives us that

$\frac{1}{2}\varepsilon q^{2\delta\ell}\beta\leqslant
q^{O_{t,r}(1)}\beta^{\frac{t-1}{t}}\varepsilon^{\prime\frac{t-1}{t}}.$

Simplifying, using the definition of $\varepsilon^{\prime}$, the fact that
$\varepsilon\geqslant q^{-2\ell(1-1000\delta)}$ and the fact that
$\beta\geqslant q^{-4\ell}$ we get

$\frac{1}{2}q^{2\delta\ell}\leqslant
q^{O_{t,r}(1)}q^{\frac{4\ell}{t}}q^{\left(\frac{2}{t}+2000\left(\delta^{2}\frac{t-1}{t}-\delta\right)\right)\ell}.$

Investigating the second two exponents of $q$, we have that for
$t\geqslant\frac{1}{\delta-\delta^{2}}\geqslant 2$,

$\left(\frac{4}{t}+\frac{2}{t}+2000\left(\delta^{2}\frac{t-1}{t}-\delta\right)\right)\ell\leqslant-1994(\delta-\delta^{2})\ell.$

This implies that

$\frac{1}{2}q^{2\delta\ell}\leqslant
q^{O_{\delta}(1)}q^{1994(\delta^{2}-\delta)\ell}<1,$

and contradiction. It follows that $S_{L,f}$ is not
$(r,\varepsilon^{\prime})$-pseudo-random, and unraveling the definition of not
being pseudo-random gives the conclusion of the theorem. ∎

####  5.1.1 Finding a Large Fraction of Successful Zoom-Ins

Theorem 5.1 asserts the existence of a good pair of zoom-in and zoom-out
$(Q,W)$ on which the table $T_{1}$ has good agreement with a global linear
function. As discussed in the introduction, our argument requires a
quantitatively version asserting that there is a good fraction of zoom-ins
that work for us. Below, we state a strengthening of Theorem 5.1 achieving
this; it easily follows from Theorem 5.1, and we defer the proof to Section B.

######  Theorem 5.2.

Suppose that tables $T_{1}$ and $T_{2}$ are $\varepsilon$-consistent for
$\varepsilon\geqslant q^{-2\ell(1-1000\delta)}$. Then there exist positive
integers $r_{1}$ and $r_{2}$ satisfying $r_{1}+r_{2}=r=\frac{10}{\delta}$,
such that for at least $q^{-5\ell^{2}}$-fraction of the $r_{1}$-dimensional
subspaces $Q$, there exists a subspace $W\supseteq Q$ of codimension $r_{2}$
and a linear function $g_{Q,W}$ such that

$\Pr_{L\in\operatorname{{\sf
Grass}}_{q}(\mathbb{F}_{q}^{U},2\ell)}\left[g_{Q,W}|_{L}=T_{1}[L]\;|\;Q\subseteq
L\subseteq W\right]\geqslant q^{-2\ell(1-1000\delta^{2})}.$

###### Proof.

The proof is deferred to Section B. ∎

####  5.1.2 Incorporating Side Conditions for Zoom-Ins

Next, we require a version of Theorem 5.2 which also takes the side conditions
into account.

######  Theorem 5.3.

Let $U$ be a question to the first prover, let $T_{1}$ the first prover’s
table, including the side conditions, and suppose that

$\Pr_{\begin{subarray}{c}L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{U},2\ell),L\cap
H_{U}=\\{0\\}\\\ R\in{\sf
Grass}_{q}(\mathbb{F}_{q}^{U},2(1-\delta)\ell)\end{subarray}}[T_{1}[L\oplus
H_{U}]|_{R}=T_{2}[R]\;|\;R\subseteq L]=\varepsilon\geqslant
q^{-2(1-1000\delta)\ell}.$

Then there are parameters $r_{1}$ and $r_{2}$ such that
$r_{1}+r_{2}\leqslant\frac{10}{\delta}$, such that for at least
$q^{-6\ell^{2}}$ fraction of the $r_{1}$-dimensional subspaces
$Q\subseteq\mathbb{F}_{q}^{U}$, there exists $W\subseteq\mathbb{F}_{q}^{U}$ of
codimension $r_{2}$ containing $Q\oplus H_{U}$, and a global linear function
$g_{Q,W}:W\xrightarrow[]{}\mathbb{F}_{q}$ that respects the side conditions on
$H_{U}$ such that

$\Pr_{L}[g_{Q,W}|_{L\oplus H_{U}}=T_{1}[L\oplus H_{U}]\;|\;Q\subseteq
L\subseteq W]\geqslant\frac{q^{-2(1-1000\delta^{2})\ell}}{5}.$

###### Proof.

For any $2k$-dimensional subspace $A$ such that $H_{U}\oplus
A=\mathbb{F}_{q}^{U}$, let $T_{A}$ be the table given by
$T_{A}[L]=T_{1}[L\oplus H_{U}]|_{L}$ for all $2\ell$-dimensional subspaces
$L\subseteq A$. We can choose a $2\ell$-dimensional subspace $L$ such that
$L\cap H_{U}=\\{0\\}$ by first uniformly choosing $A$ such that $H_{U}\oplus
A=\mathbb{F}_{q}^{U}$, and then choosing $L\subseteq A$ of dimension $2\ell$
uniformly. Thus, defining

$p^{\prime}(A)=\Pr_{L\subseteq A,R\subseteq L}[T_{A}[L]|_{R}=T_{2}[R]],$

we have

$\mathop{\mathbb{E}}_{A}[p^{\prime}(A)]=\Pr_{L:\dim(L)=2\ell,L\cap
H_{U}=\\{0\\},R\subseteq L}[T_{1}[L\oplus
H_{U}]|_{R}=T_{2}[R]]\geqslant\varepsilon.$

In particular, for at least $\frac{\varepsilon}{4}$-fraction of $A$’s, we have
$p^{\prime}(A)\geqslant\frac{\varepsilon}{4}$. For such $A$’s, by Theorem 5.2,
there exist positive integers $r_{1}$ and $r_{2}$ such that for at least
$q^{-5\ell^{2}}$-fraction of $r_{1}$-dimensional zoom-ins $Q$, there exists a
zoom-out $W^{\prime}\supset Q$ of co-dimension $r_{2}$ and a linear function
$g_{Q,W^{\prime}}$ such that,

$\Pr_{Q\subseteq L\subseteq
W}[T_{A}[L]=g_{Q,W}|_{L}]\geqslant\frac{q^{-2(1-1000\delta^{2})\ell}}{4}.$

Let $W=W^{\prime}\oplus H_{U}$ and let
$g_{Q,W}:W\xrightarrow[]{}\mathbb{F}_{q}$ be the unique extension of
$g_{Q,W^{\prime}}$ to $W$ satisfying the side conditions. We claim that

$\Pr_{L:L\cap H_{U}=\\{0\\}}[g_{Q,W}|_{L\oplus H_{U}}=T_{1}[L\oplus
H_{U}]\;|\;Q\subseteq L\subseteq
W]\geqslant\frac{q^{-2(1-1000\delta^{2})\ell}}{5}.$

Indeed, for each $Q\subseteq L^{\prime}\subseteq W^{\prime}$ there are an
equal number of $L$ such that $Q\subseteq L\subseteq W$ and $L^{\prime}\oplus
H_{U}=L\oplus H_{U}$, so

$\displaystyle\Pr_{L:L\cap H_{U}=\\{0\\}}[g_{Q,W}|_{L\oplus
H_{U}}=T_{1}[L\oplus H_{U}]\;|\;Q\subseteq L\subseteq W]$
$\displaystyle\geqslant\Pr_{Q\subseteq L\subseteq
W}[T_{A}[L]=g_{Q,W}|_{L}]-\Pr_{Q\subseteq L\subseteq W}[L\cap
H_{U}\neq\\{0\\}]$
$\displaystyle\geqslant\frac{q^{-2(1-1000\delta^{2})\ell}}{5}.$

To conclude, we see that sampling $A$ and then $Q\subseteq A$ of dimension
$r_{1}$, we get that there is a zoom-out $W$ and a function $g_{Q,W}$
satisfying the conditions in the theorem with probability at least
$\frac{\varepsilon}{4}q^{-5\ell^{2}}$. As the marginal distribution over $Q$
is $q^{-\Omega(k)}$-close to uniform over all $r_{1}$-dimensional subspaces
the conclusion follows. ∎

###  5.2 The Covering Property

In this section, we present the so called “covering property”, which is a
feature of our PCP construction that allows us to move between the first
prover’s distribution over $2\ell$-dimensional subspaces of
$\mathbb{F}_{q}^{U}$ and the second prover’s distribution over
$2\ell$-dimensional subspaces of $\mathbb{F}_{q}^{V}$. Similar covering
properties are shown in [KS13, KMS17]; however, obtaining the optimal
quadratic-programming hardness result in Theorem 1.4 requires a stronger
analysis that goes beyond the covering properties of [KS13, KMS17]. We are
able to obtain a covering property with the following parameters:

$k=q^{2(1+c)\ell}\quad,\quad\beta=q^{-2(1+2c/3)\ell},$ (4)

where $c>0$ is a constant arbitrarily small relative to $\delta$.

####  5.2.1 The Basic Covering Property

To start, we state a basic form of the improved covering property that is
required in our analysis and defer its proof to Appendix C. Fix a question
$U=(e_{1},\ldots,e_{k})$ to the first prover and recall that
$H_{U}=\operatorname{span}(x_{e_{1}},\ldots,x_{e_{k}})$ where $x_{e_{i}}$ is
the vector that is one at coordinates corresponding to variables in $e_{i}$
and $0$ elsewhere. The covering property we show will relate the following two
distributions:

$\mathcal{D}:$

  * •

Choose $x_{1},\ldots,x_{2\ell}\in\mathbb{F}_{q}^{U}$ uniformly.

  * •

Output the list $(x_{1},\ldots,x_{2\ell})$.

$\mathcal{D}^{\prime}:$

  * •

Choose $V\subseteq U$ according to the Outer PCP.

  * •

Choose $x^{\prime}_{1},\ldots,x^{\prime}_{2\ell}\in\mathbb{F}_{q}^{V}$
uniformly, and lift these vectors to $\mathbb{F}_{q}^{U}$ by inserting $0$’s
into the missing coordinates.

  * •

Choose $w_{1},\ldots,w_{2\ell}\in H_{U}$ uniformly, and set
$x_{i}=x^{\prime}_{i}+w_{i}$ for $1\leqslant i\leqslant 2\ell$.

  * •

Output the list $(x_{1},\ldots,x_{2\ell})$.

With these two definitions, the covering property used in prior works asserted
that the distribution $\mathcal{D}$ is statistically close to a variant of the
distribution $\mathcal{D}^{\prime}$. This closeness is not good enough for us,
as we will want to consider events of rather small probability under
$\mathcal{D}$ and still assert that their probability is roughly the same in
$\mathcal{D}^{\prime}$. First, in these earlier works, the distribution
$\mathcal{D}^{\prime}$ was generated by a similar process to the above without
the addition of the random vectors $w_{1},\ldots,w_{2\ell}$ from $H_{U}$. As
explained in the introduction however, this distribution is not good enough
for the purpose of Theorem 1.4, and we must consider the distribution
$\mathcal{D}^{\prime}$ above. Second, the notion of statistical closeness is
too rough for us, and we show that in fact, almost all inputs $x$ are assigned
the same probability under these two distributions up to factor $1+o(1)$.

More precisely, set $\eta=q^{-100\ell^{100}}$ throughout this subsection. Our
covering property is the following statement:

######  Lemma 5.4.

Let $\eta$ be a parameter such that $q^{-100\ell^{100}}\leqslant\eta\leqslant
1/2$. There exists a small set
$E\subseteq\left(\mathbb{F}_{q}^{U}\right)^{2\ell}$ such that both
$\mathcal{D}(E)$ and $\mathcal{D}^{\prime}(E)$ are at most $\eta^{40}$, and
for all $(x_{1},\ldots,x_{2\ell})\notin E$ we have

$0.9\leqslant\frac{D(x_{1},\ldots,x_{2\ell})}{D^{\prime}(x_{1},\ldots,x_{2\ell})}\leqslant
1.1.$

###### Proof.

The proof is deferred to Appendix C.1. ∎

####  5.2.2 The Covering Property with Zoom-ins

Lemma 5.4 represents the most basic form of the covering property, and for out
application we require a version of it that incorporates zoom-ins and advice.
Namely, we will actually interested in the case where $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ are conditioned on some $r_{1}$-dimensional zoom-in
$Q$, for an arbitrary dimension $r_{1}\leqslant\frac{10}{\delta}$. To make
notation simpler, let us write $x=(x_{1},\ldots,x_{2\ell})$ and use
$\operatorname{span}_{r_{1}}(x)$ to denote
$\operatorname{span}(x_{1},\ldots,x_{r_{1}})$. Additionally, define

$\mathcal{D}_{Q}(\mathcal{L})=\mathcal{D}(x\in\mathcal{L}\;|\;\operatorname{span}_{r_{1}}(x)=Q)=\frac{\mathcal{D}(\\{x\in\mathcal{L}\;|\;\operatorname{span}_{r_{1}}(x)=Q\\})}{\mathcal{D}(\\{x\;|\;\operatorname{span}_{r_{1}}(x)=Q\\})}.$

From Lemma 5.4 we can conclude that for any
$\mathcal{L}\subseteq(\mathbb{F}_{q}^{U})^{2\ell}$ that is not too small, the
measure $\mathcal{D}^{\prime}_{Q}(\mathcal{L})$ is within at least a constant
factor of $\mathcal{D}_{Q}(\mathcal{L})$ for nearly all $Q$.

######  Lemma 5.5.

For any $\mathcal{L}\subseteq(\mathbb{F}_{q}^{U})^{2\ell}$, we have

$\Pr_{Q}\left[\mathcal{D}^{\prime}_{Q}(\mathcal{L})\geqslant
0.8\cdot\mathcal{D}_{Q}(\mathcal{L})-\eta^{20}\right]\geqslant 1-2\eta^{20},$

where $Q$ is the span of $r_{1}$ uniformly random vectors in
$\mathbb{F}_{q}^{U}$.

###### Proof.

Throughout the proof all of the expectations and probabilities over $Q$ choose
$Q$ as in the lemma statement. Let $E$ be the small set of points from Lemma
5.4. By assumption we have

$\mathop{\mathbb{E}}_{Q}[\mathcal{D}_{Q}(E)]\leqslant\eta^{40}\quad\text{and}\quad\mathop{\mathbb{E}}_{Q}[\mathcal{D}^{\prime}_{Q}(E)]\leqslant\eta^{40}.$

Thus, by Markov’s inequality, we have that with probability at least
$1-2\eta^{20}$, we have
$\mathcal{D}_{Q}(E),\mathcal{D}^{\prime}_{Q}(E)\leqslant\eta^{20}$. In this
case we have,

$\displaystyle\sum_{\operatorname{span}_{r_{1}}(x)=Q}D(x)\geqslant\sum_{\operatorname{span}_{r_{1}}(x)=Q,x\in\overline{E}}D(x)$
$\displaystyle\geqslant\sum_{\operatorname{span}_{r_{1}}(x)=Q,x\in\overline{E}}0.9\cdot\mathcal{D}^{\prime}(x)$
$\displaystyle=0.9\cdot\left(\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}^{\prime}(x)-\sum_{\operatorname{span}_{r_{1}}(x)=Q,x\in
E}\mathcal{D}^{\prime}(x)\right),$

where we applied Lemma 5.4 in the second transition. Dividing both sides by
$\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}^{\prime}(x)$ gives that

$\frac{\sum_{\operatorname{span}_{r_{1}}(x)=Q}D(x)}{\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}^{\prime}(x)}\geqslant
0.9(1-\mathcal{D}^{\prime}_{Q}(E))\geqslant 0.9(1-\eta^{20})\geqslant 0.89.$
(5)

It follows that

$\displaystyle\mathcal{D}^{\prime}_{Q}(\mathcal{L})$
$\displaystyle=\frac{\sum_{x\in\mathcal{L},\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}^{\prime}(x)}{\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}^{\prime}(x)}$
$\displaystyle\geqslant\frac{0.89\sum_{x\in\mathcal{L}\cap\overline{E},\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}^{\prime}(x)}{\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}(x)}$
$\displaystyle\geqslant\frac{0.9\cdot
0.89\cdot\sum_{x\in\mathcal{L}\cap\overline{E},\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}(x)}{\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}(x)}$
$\displaystyle\geqslant
0.8\cdot\mathcal{D}_{Q}(L)-\frac{\sum_{\operatorname{span}_{r_{1}}(x)=Q,x\in
E}\mathcal{D}(x)}{\sum_{\operatorname{span}_{r_{1}}(x)=Q}\mathcal{D}(x)}$
$\displaystyle=0.8\cdot\mathcal{D}_{Q}(L)-\mathcal{D}_{Q}(E)$
$\displaystyle\geqslant 0.8\cdot\mathcal{D}_{Q}(L)-\eta^{20},$

where we apply Equation (5) in the second transition and the assumption
$\mathcal{D}_{Q}(E)\leqslant\eta^{20}$ in the last transition. ∎

####  5.2.3 The Covering Property for the Advice

We will also need a similar, and simpler, version of the above lemma that
applies to $r_{1}$-dimensional subspaces for some constant
$r_{1}=O(\delta^{-1})$. This is to handle the fact that the zoom-in $Q$ is
sampled uniformly from $\mathbb{F}_{q}^{V}$ after $V$ is chosen according to
the outer PCP, and then lifted to a subspace over $\mathbb{F}_{q}^{U}$,
instead of uniformly from $\mathbb{F}_{q}^{U}$. Formally, let
$\mathcal{D}^{\prime}_{r_{1}}$ denote the former distribution over
$r_{1}$-dimensional subspaces $Q\subseteq\mathbb{F}_{q}^{U}$ and let
$\mathcal{D}_{r_{1}}$ denote the latter distribution over $r_{1}$-dimensional
subspaces $Q\subseteq\mathbb{F}_{q}^{U}$. These are the same as the
distributions $\mathcal{D}$ and $\mathcal{D}^{\prime}$ of the previous
subsection except over $\left(\mathbb{F}_{q}^{U}\right)^{r_{1}}$ instead of
$\left(\mathbb{F}_{q}^{U}\right)^{2\ell}$. We show the following.

######  Lemma 5.6.

Let $\mathcal{Q}$ be a set of $r_{1}$-dimensional subspaces in
$\mathbb{F}_{q}^{U}$ satisfying $\mathcal{D}_{r_{1}}(\mathcal{Q})\geqslant
q^{-10\ell^{10}}$. Then,

$\mathcal{D}^{\prime}_{r_{1}}(\mathcal{Q})\geqslant
0.8\cdot\mathcal{D}_{r_{1}}(Q).$

###### Proof of Lemma 5.6.

Take $E$ from Lemma 5.4, and define

$\mathcal{L}=\\{(x_{1},\ldots,x_{2\ell})\in\left(\mathbb{F}_{q}^{U}\right)^{2\ell}\;|\;\operatorname{span}(x_{1},\ldots,x_{r_{1}})\in\mathcal{Q}\\}.$

Then $\mathcal{D}_{r_{1}}(\mathcal{Q})=\mathcal{D}(\mathcal{L})$,
$\mathcal{D}^{\prime}_{r_{1}}(\mathcal{Q})=\mathcal{D}^{\prime}(\mathcal{L})$
and

$\mathcal{D}^{\prime}_{r_{1}}(\mathcal{Q})=\mathcal{D}^{\prime}(\mathcal{L})\geqslant\sum_{\begin{subarray}{c}x\in\mathcal{L}\\\
x\notin E\end{subarray}}\mathcal{D}^{\prime}(x)\geqslant
0.9\cdot\sum_{\begin{subarray}{c}x\in\mathcal{L}\\\ x\notin
E\end{subarray}}\mathcal{D}(x)\geqslant
0.9\cdot\mathcal{D}(\mathcal{L})-\mathcal{D}(E)\geqslant
0.8\cdot\mathcal{D}(\mathcal{L})=0.8\cdot\mathcal{D}_{r_{1}}(\mathcal{L}).$

where we use Lemma 5.4 in the second transition, and the fact that
$\mathcal{D}(E)\leqslant\eta$ and
$\mathcal{D}(\mathcal{L})=\mathcal{D}_{r_{1}}(\mathcal{Q})\geqslant
q^{-10\ell^{10}}$ in the penultimate transition. ∎

###  5.3 The Number of Maximal Zoom-Outs is Bounded

In Theorem 5.2, we showed that the two provers can agree on a zoom-in with
reasonable probability using their advice. The same cannot be said for zoom-
outs however, and to circumvent this issue we must develop further tools. In
this section, we define the notion of _maximal_ zoom-outs and show that for a
fixed zoom-in $Q$, the number of maximal zoom-outs is bounded.

####  5.3.1 Generic Sets of Subspaces

One of our primary concerns with respect to zoom-outs is that it is possible
for a prover to have many good zoom-outs to choose from (so that independent
sampling doesn’t work) but not enough to allow for advice-type solution. To
deal with large collections of zoom-outs we define a special property of zoom-
outs that is called “genericness”. To motivate it, note that if
$W_{1},W_{2}\subseteq V$ are distinct subspaces of co-dimension $r$, then
$W_{1}\cap W_{2}$ is a subspace whose co-dimension is between $2r$ and $r+1$.
For a typical pair of subspaces, the intersection $W_{1}\cap W_{2}$ has
dimension $2r$, in which case we say they are generic. Genericness is useful
probabilistically, since if $W_{1},W_{2}$ are generic, then the event that a
randomly chosen $2\ell$-dimensional subspace is contained in $W_{1}$, and the
event it is contained in $W_{2}$, are almost independent. Below is a more
general and formal definition:

######  Definition 5.7.

We say that a set $\mathcal{S}=\\{W_{1},\ldots,W_{N}\\}$ of codimension $r$
subspaces of $V$ is $t$-generic with respect to $V$ if for any $t$-distinct
subspaces, say $W_{i_{1}},\ldots,W_{i_{t}}\in\mathcal{S}$, we have
$\operatorname{codim}(\bigcap_{1\leqslant j\leqslant t}W_{i_{j}})=t\cdot r$.
When the ambient space $V$ is clear from context we simply say that
$\mathcal{S}$ is $t$-generic.

We remark that any set of subspaces that is $t$-generic with respect to $V$ is
also $t^{\prime}$-generic with respect to $V$ for any $t^{\prime}<t$. In this
section, we will show a couple of results regarding generic sets of subspaces
that will be used to bound the number of maximal zoom-outs in Section 8.

The result we need is a sunflower-type lemma, stating that any large set of
codimension $r$ subspaces inside $V$ contains a large set of subspaces that
are $t$-generic with respect to $V^{\prime}$ for some $V^{\prime}\subseteq V$.
Below is a formal statement.

######  Lemma 5.8.

Let $t,r\in\mathbb{N}$ be integers and let
$\mathcal{S}=\\{W_{1},\ldots,W_{N}\\}$ be a set of $N$ subspaces of co-
dimension $r$ inside of $V$. Then there exists a subspace $V^{\prime}\subseteq
V$ and a set of subspaces $\mathcal{S^{\prime}}\subseteq\mathcal{S}$ such
that:

  * •

$\left|\mathcal{S^{\prime}}\right|\geqslant\frac{N^{\frac{1}{(r+1)\cdot(t-1)!}}}{q^{r}}$.

  * •

Each $W_{i}\in\mathcal{S^{\prime}}$ is contained in $V^{\prime}$ and has co-
dimension $s$ with respect to $V^{\prime}$, where $s\leqslant r$.

  * •

$\mathcal{S^{\prime}}$ is $t$-generic with respect to $V^{\prime}$.

In order to show Lemma 5.8, we introduce two necessary lemmas. The first,
Lemma 5.9, states that for $j\geqslant 2$, any $j$-generic set of subspaces
contains a large $(j+1)$-generic set of subspaces. The second, Lemma
5.10,states that either a set of subspaces is already $2$-generic, or there
are many subspaces in the set that are contained in the same hyperplane. Using
this lemma, we can start from a large set of subspaces $\mathcal{S}$ inside of
an ambient space $V$ and iteratively reduce to the dimension of the ambient
space until we find a $2$-generic set of subspaces relative to the ambient
space. Indeed, either the set $\mathcal{S}$ is already $2$-generic, or there
is a hyperplane $V^{\prime}\subseteq V$ such that the set of subspaces in
$\mathcal{S}$ contained in $V^{\prime}$ is large. Taking this set to be the
new $\mathcal{S}$ and $V^{\prime}$ to be the new ambient space, we obtain a,
still, large set of subspaces, whose codimension is now one less. We may
repeat this process until $\mathcal{S}$ is a set of hyperplanes in the ambient
space, at which point it will be $2$-generic.

######  Lemma 5.9.

Let $\mathcal{S}=\\{W_{1},\ldots,\mathcal{W}_{N}\\}$ be a set of $N$-subspaces
of codimension $r$ inside of $V$ that is $j$-generic with respect to $V$, then
there is a subset $\\{W_{1},\ldots,W_{N^{\prime}}\\}\subseteq\mathcal{S}$ of
size $N^{\prime}\geqslant\frac{N^{1/j}}{q^{r}}$ that is $(j+1)$-generic with
respect to $V$.

###### Proof.

Fix any $j$ distinct subspaces in $\mathcal{S}$, say $W_{1},\ldots,W_{j}$ and
let $W=W_{1}\cap\cdots\cap W_{j}$. Since $\mathcal{S}$ is $j$-generic,
$\operatorname{codim}(W)=j\cdot r$. We claim that there are at most $q^{j\cdot
r}$ subspaces $W_{i^{\prime}}\in\mathcal{S}\setminus\\{W_{1},\ldots,W_{j}\\}$
such that $\operatorname{codim}(W\cap W_{i^{\prime}})\leqslant(j+1)r-1$. Call
such subspaces bad and suppose for the sake of contradiction that there are
greater than $q^{jr}$ bad subspaces $W_{i^{\prime}}$. Then for each bad
$W_{i^{\prime}}$ we have,

$\displaystyle\dim(W_{i^{\prime}}\oplus W)$
$\displaystyle=\dim(W_{i^{\prime}})+\dim(W)-\dim(W_{i^{\prime}}\cap W)$
$\displaystyle\leqslant(\dim(V)-r)+(\dim(V)-jr)-(\dim(V)-(j+1)r-1)$
$\displaystyle=\dim(V)-1.$

Therefore, for each $W_{i^{\prime}}$, the space $W\oplus W_{i^{\prime}}$ is
contained in a hyperplane $H$ such that $H\supseteq W$. There are at most
$q^{\operatorname{codim}(W)}-1=q^{j\cdot r}-1$ hyperplanes $H$ containing $W$,
and by the pigenhole principle it follows that there are two bad subspaces say
$W_{i^{\prime}_{1}},W_{i^{\prime}_{2}}$ that are both contained in the same
hyperplane $H$. This is a contradiction however, as by the $j$-genericness of
$\mathcal{S}$, we must have

$\displaystyle\dim(W_{i^{\prime}_{1}}\oplus W_{i^{\prime}_{2}})$
$\displaystyle=\dim(W_{i^{\prime}_{1}})+\dim(W_{i^{\prime}_{2}})-\dim(W_{i^{\prime}_{1}}\cap
W_{i^{\prime}_{2}})$ $\displaystyle=2(\dim(V)-r)-(\dim(V)-2r)$
$\displaystyle=\dim(V),$

and hence $W_{i^{\prime}_{1}}$ and $W_{i^{\prime}_{2}}$ cannot both be
contained in the hyperplane $H$.

The lemma now follows from the claim we have just shown. Construct a subset
$\mathcal{S^{\prime}}$ greedily as follows:

  1. 1.

Initialize $\mathcal{S^{\prime}}$ by picking $j$ arbitrary subspaces from
$\mathcal{S}$ and inserting them to $\mathcal{S^{\prime}}$.

  2. 2.

For any $j$ subspaces in $\mathcal{S^{\prime}}$, say $W_{1},\ldots,W_{j}$,
remove any $W^{\prime}\in\mathcal{S}$ which is bad for them.

  3. 3.

If $\mathcal{S}$ is not empty, pick some $W\in\mathcal{S}$, insert it to
$\mathcal{S^{\prime}}$ and iterate.

Note that trivially, the collection $\mathcal{S^{\prime}}$ will be
$(j+1)$-generic in the end of the process. To lower bound the size of
$\mathcal{S^{\prime}}$, note that when $|\mathcal{S^{\prime}}|=s$, the number
of elements from $\mathcal{S}$ that have been deleted is at most
$s^{j}q^{jr}$, and hence so long as this value is at most $N$, we may do
another iteration. Thus, we must have that
$s\geqslant\left(\frac{N}{q^{jr}}\right)^{1/j}=\frac{N^{1/j}}{q^{r}}$ when the
process terminates. ∎

######  Lemma 5.10.

Let $\\{W_{1},\ldots,W_{N}\\}$ be a set of subspaces of $V$ of codimension
$r$. Then for any integer $m\geqslant 1$, at least one of the following holds.

  * •

There are $m$ subspaces, way $W_{1},\ldots,W_{m}$ such that for every pair
$1\leqslant i\neq j\leqslant m$, $\operatorname{codim}(W_{i}\cap W_{j})=2r$.

  * •

There is a subspace $V^{\prime}\subseteq V$ of co-dimension $1$ that contains
$N^{\prime}=\frac{N}{mq^{r}}$ of these subspaces, say
$W_{1},\ldots,W_{N^{\prime}}$.

###### Proof.

Note that for any $1\leqslant i\neq j\leqslant N$, we have
$\operatorname{codim}(W_{i}\cap W_{j})\leqslant 2r$. Consider the graph with
vertices $W_{1},\ldots,W_{N}$ with $(W_{i},W_{j})$ an edge if and only if
$i\neq j$ and $\operatorname{codim}(W_{i}\cap W_{j})\leqslant 2r-1$. If every
vertex in this graph has degree at most $\frac{N}{m}$, then we are done as
there is an independent set of size $m$ and these subspaces satisfy the first
condition. Suppose this is not the case. Then there is a vertex, say $W_{N}$,
that has $\frac{N}{m}$ neighbors, say $W_{1},\ldots,W_{\frac{N}{m}}$. For
$1\leqslant i\leqslant\frac{N}{m}$, we have $\operatorname{codim}(W_{N}\cap
W_{i})\leqslant 2r-1$, so

$\dim(W_{i}\oplus W_{N})=\dim(W_{i})+\dim(W_{N})-\dim(W_{i}\cap
W_{N})\leqslant\dim(V)-1.$

Thus $W_{i}\oplus W_{N}$ is always contained in a codimension $1$ subspace of
$V$ that contains $W_{N}$. Since the number of such subspaces is $q^{r}-1$,
there must exist one subspace, say $V^{\prime}$, that contains at least
$\frac{N}{mq^{r}}$ of the subspaces in the list $W_{1},\ldots,W_{\frac{N}{m}}$
. ∎

Repeatedly applying Lemma 5.10 yields the following corollary.

######  Corollary 5.11.

Let $\\{W_{1},\ldots,W_{N}\\}$ be a set of subspaces of $V$ of codimension $r$
with respect to $V$. There exists a subspace $V^{\prime}\subset V$, an integer
$1\leqslant s\leqslant r$, and a subset of
$m\geqslant\frac{N^{\frac{1}{r+1}}}{q^{r}}$, say $\\{W_{1},\ldots,W_{m}\\}$,
all contained in $V^{\prime}$ such that,

  * •

Each $W_{i}$, $1\leqslant i\leqslant m$, has codimension $s$ with respect to
$V^{\prime}$.

  * •

Each $W_{i}\cap W_{j}$, $1\leqslant i\neq j\leqslant m$, has codimension $2s$.

###### Proof.

To start set $V^{\prime}=V$. If the $W_{i}$’s have codimension $1$ in
$V^{\prime}$ then the result holds.

Otherwise, if the conclusion does not hold, then apply Lemma 5.10 with
$m=\frac{N^{\frac{1}{r+1}}}{q^{r}}$. Either the first condition of Lemma 5.10
holds and we are done, or we can find a new subspace, $V^{\prime\prime}$, of
codimension $1$ inside the current $V^{\prime}$ containing at least
$\frac{N}{mq^{r}}$ of the $W_{i}$’s. Set $V^{\prime}=V^{\prime\prime}$ and
repeat. Note that the codimension of the $W_{i}$’s with respect to
$V^{\prime}$ drops by $1$ after every iteration, so we will repeat at most $r$
times before reaching the desired conclusion. This yields a list of $W_{i}$’s
that satisfy the conditions of size at least

$\frac{N}{(mq^{r})^{r}}=N^{\frac{1}{r+1}}\geqslant m.\qed$

With Corollary 5.11 and Lemma 5.9, we can prove Lemma 5.8

###### Proof of Lemma 5.8.

By Corollary 5.11, there is a set $\mathcal{S}^{\prime}$ of size
$|\mathcal{S}^{\prime}|\geqslant\frac{N^{\frac{1}{r+1}}}{q^{r}}$ and
$V^{\prime}\subseteq V$ such that $\mathcal{S^{\prime}}$ is $2$-generic with
respect to $V^{\prime}$, and each $W_{i}$ has (the same) codimension
$s\leqslant r$ with respect to $V^{\prime}$. Applying Lemma 5.9 $t-2$ times,
there is a set of $t$-generic subspaces relative to $V^{\prime}$,
$\mathcal{S}^{\prime\prime}\subseteq\mathcal{S^{\prime}}$, of size

$\left|\mathcal{S}^{\prime\prime}\right|\geqslant\left(\left(\left(\left(\frac{|\mathcal{S}^{\prime}|}{q^{r}}\right)^{\frac{1}{2}}\cdot\frac{1}{q^{r}}\right)^{\frac{1}{3}}\cdots\right)\cdot\frac{1}{q^{r}}\right)^{\frac{1}{t-1}}\geqslant\frac{\left|\mathcal{S}^{\prime}\right|^{\frac{1}{(t-1)!}}}{q^{r}}\
\geqslant\frac{N^{\frac{1}{(r+1)\cdot(t-1)!}}}{q^{r}}.\qed$

In addition to Lemma 5.8, we state another useful feature of generic sets of
subspaces, formalized in Lemma 5.12 below. The lemma asserts that if a
collection $\\{W_{1},\ldots,W_{N}\\}$ is generic, and one zooms-outs from the
ambient space $V$ into a hyperplane $H$, then one gets an induced collection
$\\{W_{1}\cap H,\ldots,W_{N}\cap H\\}$ which is almost as generic.

######  Lemma 5.12.

Let $\mathcal{S}=\\{W_{1},\ldots,W_{N}\\}$ be a set of subspaces of
codimension $r$ that is $t$-generic with respect to some space $V$ for an even
integer $t$, and let $H$ be a hyperplane in $V$. Then the set of subspaces
$\mathcal{S}^{\prime}=\\{W_{1}\cap H,\ldots,W_{N}\cap H\\}$ can be made a
$\frac{t}{2}$-generic set of subspaces with respect to $H$ with codimension
$r$ inside of $H$ by removing at most $\frac{t}{2}$ subspaces $W_{i}\cap H$
from it.

###### Proof.

Suppose that $\mathcal{S}^{\prime}$ is not $\frac{t}{2}$-generic with respect
to $H$ with codimension $r$ inside of $H$, as otherwise we are done. In this
case, there must exist $\frac{t}{2}$ distinct subspaces, say $W_{1}\cap
H,\ldots,W_{\frac{t}{2}}\cap H\in\mathcal{S}^{\prime}$ such that

$\operatorname{codim}\left(W_{1}\cap\cdots\cap W_{\frac{t}{2}}\cap
H\right)<\frac{t}{2}\cdot r+1,$

where the codimension is with respect to $V$. However, since $\mathcal{S}$ is
$t$-generic (and thus $\frac{t}{2}$-generic as well) with respect to $V$, this
implies that

$W_{1}\cap\cdots\cap W_{\frac{t}{2}}\subseteq H.$

Now delete $W_{1}\cap H,\ldots,W_{\frac{t}{2}}\cap H$ from
$\mathcal{S}^{\prime}$. We claim that the resulting set is
$\frac{t}{2}$-generic with respect to $H$. Suppose for the sake of
contradiction that it is not. Then there must be another $\frac{t}{2}$
distinct subspaces, say $W_{\frac{t}{2}+1}\cap H,\ldots,W_{t}\cap
H\in\mathcal{S}^{\prime}$ such that

$W_{\frac{t}{2}+1}\cap\cdots\cap W_{t}\subseteq H.$

This would imply

$\left(W_{1}\cap\cdots\cap
W_{\frac{t}{2}}\right)\oplus\left(W_{\frac{t}{2}+1}\cap\cdots\cap
W_{t}\right)\subseteq H.$

This is a contradiction however, as $\mathcal{S}$ is $t$-generic with respect
to $V$, so $\operatorname{codim}(W_{1}\cap\cdots\cap W_{t})=tr$, and

$\displaystyle\dim\left(W_{1}\cap\cdots\cap W_{\frac{t}{2}}\oplus
W_{\frac{t}{2}+1}\cap\cdots\cap W_{t}\right)$
$\displaystyle\qquad\qquad=\dim\left(W_{1}\cap\cdots\cap
W_{\frac{t}{2}}\right)+\dim\left(W_{\frac{t}{2}}\oplus
W_{\frac{t}{2}+1}\cap\cdots\cap W_{t}\right)-\dim\left(W_{1}\oplus
W_{2}\cap\cdots\cap W_{t}\right)$
$\displaystyle\qquad\qquad=2\left(\dim(V)-\frac{t}{2}r\right)-\dim(V)+tr=\dim(V)>\dim(H),$

and contradiction. ∎

######  Lemma 5.13.

Let $\mathcal{W}$ be a set of subspaces that is $2^{K}$ generic with respect
to $V$ and let $B$ be a subspace of codimension $j$. Then, the set of
subspaces,

$\mathcal{W}_{B}=\\{W_{i}\cap B\;|\;W_{i}\in\mathcal{W}\\},$

can be made $2^{K-j}$ generic with respect to $B$ by removing at most
$j2^{K-1}$ subspaces.

###### Proof.

There is a sequence of subspaces $V=B_{0}\supseteq
B_{1}\supseteq\cdots\supseteq B_{j}=B$, such that $B_{i+1}$ is a hyperplane
inside of $B_{i}$. Do the following,

  1. 1.

Initialize $\mathcal{W}_{0}=\mathcal{W}$ and set $i=1$.

  2. 2.

Set $\mathcal{W}_{i}=\\{W_{k}\cap B_{i}\;|\;W_{k}\in\mathcal{W}_{i-1}\\}$, and
then remove the minimal number of subspaces to turn $\mathcal{W}_{i}$ into a
$2^{K-i}$-generic collection with respect to $B_{i}$.

  3. 3.

Stop if $i=j$, otherwise, increase $i$ by $1$ and return to step $2$.

It is clear that the output is a set of subspaces
$\mathcal{W}_{j}\subseteq\mathcal{W}_{B}$ that is $2^{K-j}$-generic with
respect to $B$. Furthermore, during each iteration, at most
$2^{K-i-1}\leqslant 2^{K-1}$ subspaces are removed by Lemma 5.12, and the
result follows. ∎

####  5.3.2 The Sampling Lemma

As explained earlier, the notion of genericness is useful probabilistically,
and in this section we state and prove a sampling lemma about generic
collections which is necessary for our analysis. Fix an arbitrary zoom-in
$Q\subseteq V$ of dimension $a$, and let
$\mathcal{S}=\\{W_{1},\ldots,W_{m}\\}$ be a $2$-generic collection of
subspaces of $V$ of codimension $r$ all containing $Q$. Also let $\mathcal{A}$
be a set of $j$-dimensional subspaces containing $Q$. For the remainder of
this subsection, use ${\sf Zoom}[Q,V]$ to denote the set of $j$-dimensional
subspaces in $V$ containing $Q$. Consider the following two probability
measures over ${\sf Zoom}[Q,V]$:

  1. 1.

The distribution $\mu$ which is uniform over ${\sf Zoom}[Q,V]$.

  2. 2.

The distribution $\nu$, wherein a subspace is sampled by first picking
$i\in\\{1,\ldots,m\\}$ uniformly and then sampling a subspace from ${\sf
Zoom}[Q,W_{i}]$ uniformly.

The main content of this section is the following lemma, asserting that the
measures $\mu$ and $\nu$ are close in statistical distance provided that $m$
is large. More precisely:

######  Lemma 5.14.

For any $\mathcal{L}\subset{\sf Zoom}[Q,V]$ we have

$\left|\nu(\mathcal{L})-\mu(\mathcal{L})\right|\leqslant\frac{3q^{\frac{r}{2}(j-a)}}{\sqrt{m}}.$

We now set up some notations for the proof of Lemma 5.14. For $L\in{\sf
Zoom}[Q,V]$ let

$N(L)=|\\{W_{i}\in\mathcal{S}\;|\;L\subseteq W_{i}\\}|,$

and for an arbitrary pair of distinct $W_{i},W_{i^{\prime}}\in\mathcal{S}$
define the following quantities:

$\displaystyle D=|\\{L\in{\sf Zoom}[Q,V]\;|\;L\subseteq
W_{i}\\}=\begin{bmatrix}{n-a-r}\\\ {j-a}\end{bmatrix}_{q},\qquad
p_{1}=\Pr_{L\in{\sf Zoom}[Q,V]}[L\subseteq W_{i}]$
$\displaystyle\qquad\qquad\qquad p_{2}=\Pr_{L\in{\sf Zoom}[Q,V]}[L\subseteq
W_{i}\cap W_{i^{\prime}}]=\frac{\begin{bmatrix}{n-a-2r}\\\
{j-a}\end{bmatrix}_{q}}{\begin{bmatrix}{n-a}\\\ {j-a}\end{bmatrix}_{q}}.$ (6)

We note that all of these quantities are well defined as they do not depend on
the identity of $W_{i}$ and $W_{i^{\prime}}$. The first two equations are
clear and the third uses the fact that $\mathcal{S}$ is $2$-generic. Thus,

$\mu(L)=\frac{1}{|{\sf
Zoom}[Q,V]|}=\frac{p_{1}}{D},\qquad\qquad\qquad\nu(L)=\frac{N(L)}{m}\cdot\frac{1}{D}=\frac{N(L)}{mD}.$
(7)

For the first equation, we are using the fact that $|{\sf Zoom}[Q,V]|\cdot
p_{1}=D$, while the second equation is evident. In the following claim we
analyze the expectation and variance of $N(L)$ when $L$ is chosen uniformly
form ${\sf Zoom}[Q,V]$:

######  Claim 5.15.

$\mathop{\mathbb{E}}_{L\in{\sf Zoom}[Q,V]}[N(L)]=p_{1}m$ and
$\operatorname{var}(N(L))\leqslant p_{1}m$. where the variance is over uniform
$L\in{\sf Zoom}[Q,V]$.

###### Proof.

By linearity of expectation

$\mathop{\mathbb{E}}_{L\in{\sf Zoom}[Q,V]}[N(L)]=\sum_{i=1}^{m}\Pr_{L\in{\sf
Zoom}[Q,V]}[L\subseteq W_{i}]=p_{1}m,$

and we move on to the variance analysis. To bound
$\mathop{\mathbb{E}}_{L\in{\sf Zoom}[Q,V]}[N(L)^{2}]$, write

$\displaystyle\mathop{\mathbb{E}}_{L\in{\sf Zoom}[Q,V]}[N(L)^{2}]$
$\displaystyle=\mathop{\mathbb{E}}_{L\in{\sf
Zoom}[Q,V]}\left[\left(\sum_{i=1}^{m}\mathbbm{1}_{L\subseteq
W_{i}}\right)^{2}\right]$ $\displaystyle\leqslant m\cdot\Pr_{L\in{\sf
Zoom}[Q,V]}[L\subseteq W_{i}]+m^{2}\cdot\Pr_{L\in{\sf Zoom}[Q,V]}[L\subseteq
W_{i}\cap W_{i^{\prime}}]$ $\displaystyle=p_{1}m+p_{2}m^{2}.$

It follows that,

$\operatorname{var}(N(L))\leqslant p_{1}m+p_{2}m^{2}-p_{1}^{2}m^{2}.$

Finally note that $p_{2}$ and $p_{1}^{2}$ are nearly the same value, and it
can be checked using Equation (6) that $p_{2}\leqslant p_{1}^{2}$ and so
$\operatorname{var}(N(U))\leqslant p_{1}m$. ∎

Combining Chebyshev’s inequality with Claim 5.15, we conclude the following
lemma which will be useful for us later on.

######  Lemma 5.16.

For any $c>0$ it holds that

$\Pr_{L\in{\sf Zoom}[Q,V]}\Biggl{[}\left|N(L)-p_{1}m\right|\geqslant c\cdot
p_{1}m\Biggr{]}\leqslant\frac{1}{c^{2}p_{1}m}\leqslant\frac{q^{r(j-a)}}{c^{2}m}.$

###### Proof.

This is an immediate result of Chebyshev’s inequality with the bounds from
Claim 5.15. ∎

Lastly, we use Claim 5.15 to prove Lemma 5.14.

###### Proof of Lemma 5.14.

We have,

$|\mu(\mathcal{L})-\nu(\mathcal{L})|=\frac{1}{mD}|\sum\limits_{L\in\mathcal{L}}N(L)-p_{1}m|\leqslant\frac{1}{mD}\sum\limits_{L\in\mathcal{L}}|N(L)-p_{1}m|\leqslant\frac{|{\sf
Zoom}[Q,V]|}{mD}\mathop{\mathbb{E}}_{L}[|N(L)-p_{1}m|],$

and by Cauchy-Schwartz we get that

$|\mu(\mathcal{L})-\nu(\mathcal{L})|\leqslant\frac{|{\sf
Zoom}[Q,V]|}{mD}\sqrt{\operatorname{var}(N(L))}.$

Plugging in Claim 5.15 and using $|{\sf Zoom}[Q,V]|=D/p_{1}$ we get that

$|\mu(\mathcal{L})-\nu(\mathcal{L})|\leqslant\frac{1}{\sqrt{p_{1}m}}\leqslant\frac{3q^{\frac{r}{2}(j-a)}}{\sqrt{m}}.\qed$

####  5.3.3 Bound on Maximal Zoom-outs

For this subsection, we work in the second prover’s space,
$\mathbb{F}_{q}^{V}$, and make the assumption that $|V|\gg\ell$, say
$|V|\geqslant 2^{100}q^{\ell}$ to be concrete. We first establish several
results in the simplified setting where there is no zoom-in. After that we
show how to deduce an analogous result with a zoom-in. Throughout this
section, we fix $T$ to be a table that assigns to each $L\in{\sf
Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)$ a linear function on $L$.

######  Definition 5.17.

Given a table $T$ on ${\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)$ and a
subspace $Q\subseteq\mathbb{F}_{q}^{V}$, we call a zoom-out, function pair,
$(W,g_{W})$, where $W\subseteq\mathbb{F}_{q}^{V}$ and
$f:W\xrightarrow[]{}\mathbb{F}_{q}$, $(C,s)$-maximal with respect to $T$ on
$Q$ if

$\Pr_{L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[g_{W}|_{L}\equiv
T[L]\;|\;Q\subseteq L\subseteq W]\geqslant C,$

and there does not exist another zoom-out function pair,
$(W^{\prime},g_{W^{\prime}})$ such that $\mathbb{F}_{q}^{V}\supseteq
W^{\prime}\supsetneq W$,
$g_{W^{\prime}}:\mathbb{F}_{W}^{\prime}\xrightarrow[]{}\mathbb{F}_{q}$,
$g_{W^{\prime}}|_{W}\equiv g|_{W}$ and

$\Pr_{L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[g_{W^{\prime}}|_{L}\equiv
T[L]\;|\;Q\subseteq L\subseteq W^{\prime}]\geqslant sC.$

In the case that $Q=\\{0\\}$, we say that $(W,g_{W})$ is $(C,s)$-maximal with
respect to $T$.

In the above statement, $C$ should be thought of as small and $s$ should be
thought of as an absolute constant. With this in mind, a zoom-out $W$ and a
linear function on it $g_{W}$ is called maximal if there is no zoom-out
$W^{\prime}$ that strictly contains $W$, and an extension of $g_{W}$ to
$g_{W^{\prime}}$, that has the same agreement with $T$ as $g_{W}$ (up to
constant factors). As an immediate consequence of the definition of
$(C,s)$-maximal, we have the following lemma, which roughly states that every
zoom-out for which there that has a linear function with good agreement inside
the zoom-out is contained in a maximal zoom-out (with only slightly worse
agreement).

######  Lemma 5.18.

Let $T$ be a table on ${\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)$,
$Q\subseteq\mathbb{F}_{q}^{V}$, and $W\subseteq\mathbb{F}_{q}^{V}$ be a
subspace of codimension $r$ containing $Q$. Suppose that there exists a linear
function $g_{W}:W\xrightarrow[]{}\mathbb{F}_{q}$ such that

$\Pr_{L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[g_{W}|_{L}\equiv
T[L]\;|\;Q\subseteq L\subseteq W]\geqslant C.$

Then there exists a subspace $W^{\prime}\supseteq W$ and a linear function
$g_{W^{\prime}}:W^{\prime}\xrightarrow[]{}\mathbb{F}_{q}$ such that
$g_{W^{\prime}}|_{W}\equiv g_{W}$ and $(g_{W^{\prime}},W^{\prime})$ is
$(Cs^{-r},s)$-maximal and a linear function
$g_{W^{\prime}}:W^{\prime}\xrightarrow[]{}\mathbb{F}_{q}$ such that

$\Pr_{L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[g_{W^{\prime}}|_{L}\equiv
T[L]\;|\;Q\subseteq L\subseteq W]\geqslant C.$

###### Proof.

This is an immediate consequence of Definition 5.17. If $(W,g_{W})$ is
$(C,s)$-maximal then we are done. Otherwise, there must exist
$W_{1},g_{W_{1}}$ such that $W_{1}\supsetneq W$, $g_{W_{1}}|_{W}\equiv g_{W}$
and

$\Pr_{L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[g_{W_{1}}|_{L}\equiv
T[L]\;|\;Q\subseteq L\subseteq W_{1}]\geqslant sC.$

We can repeat this argument at most $r$ times before obtaining some
$(g_{W^{\prime}},W^{\prime})$ that is $(Cs^{-r},s)$ maximal and satisfies
$W^{\prime}\supseteq W$ and $g_{W^{\prime}}|_{W}\equiv g_{W}$. ∎

The following result, which is key to our analysis gives an upper bound on the
number of maximal zoom-outs. This lemma is in fact equivalent to Lemma 1.7,
and its proof is deferred to Section 8. In order to present the lemma cleanly,
we set the following parameters for the remainder of the section, which can
all be considered constant

$\xi=\delta^{5},\quad\delta_{2}=\frac{\xi}{100},\quad
t=\left(2^{2+10/\delta_{2}}\right)!\;.$

######  Lemma 5.19.

Let $T$ be a table on ${\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)$ with
$|V|\geqslant 2^{100}q^{\ell}$ and set $r\leqslant\frac{10}{\delta}$,
$C\geqslant q^{-2(1-\delta^{5})\ell}$, and

$N\geqslant q^{100\left(t-1\right)!r^{2}\ell\xi^{-1}}.$

Suppose that $(W_{1},f_{1}),\ldots,(W_{N},f_{N})$ are zoom-out, function pairs
such that the $W_{i}$’s are all distinct and for each $1\leqslant i\leqslant
m$, $\operatorname{codim}(W_{i})=r$, and

$\Pr_{L\in{\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[f_{i}|_{L}\equiv
T[L]\;|\;L\subseteq W_{i}]\geqslant C.$

Then there is a a subspace $V^{\prime}$, a linear function
$h^{\prime}:V^{\prime}\xrightarrow[]{}\mathbb{F}_{q}$, and a set of subspaces
$\mathcal{W}^{\prime}\subseteq\\{W_{1},\ldots,W_{N}\\}$ of size $N\geqslant
q^{50r\ell\xi^{-1}}$

  * •

Each $W_{i}\in\mathcal{W}^{\prime}$ is strictly contained in $V^{\prime}$ and
has codimension $r^{\prime}<r$ with respect to $V^{\prime}$.

  * •

$\mathcal{W}^{\prime}$ is $2$-generic with respect to $V^{\prime}$.

  * •

For any $W_{i}\in\mathcal{W}^{\prime}$, $h^{\prime}|_{W_{i}}\equiv f_{i}$.

###### Proof.

The proof is deferred to Section 8. ∎

To bound the number of maximal zoom-outs, we will also need the following list
decoding property.

######  Lemma 5.20.

Let $T$ be a table on ${\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)$, let $Q$ be
an $r_{1}$-dimensional subspace, and let $W\supseteq Q$ be a subspace of
codimension $r_{2}$. Suppose that $2\ell$ is sufficiently large and
$\dim(W)\geqslant 20\ell$. Let $f_{1},\ldots,f_{m}$ be a list of distinct
linear functions such that $f_{i}|_{L}\equiv T[L]$ for at least
$\beta$-fraction of the $2\ell$-dimensional subspaces $L$ such that
$Q\subseteq L\subseteq W$, for $\beta\geqslant 2q^{-2\ell+r_{1}}+c$, and
$c>0$. Then,

$m\leqslant\frac{4}{c^{2}}\leqslant\frac{4}{\beta^{2}}.$

###### Proof.

The proof is deferred to Appendix D ∎

Combining Lemma 5.19 with Lemma 5.20, yields a bound on the number of $(C,s)$
maximal zoom-out function pairs with respect to a table $T$ on $Q$.

######  Theorem 5.21.

For any table $T$ on ${\sf Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)$ such that
$|V|\geqslant q^{\ell}$, any subspace $Q\subseteq\mathbb{F}_{q}^{V}$ of
dimension $r_{1}\leqslant\frac{10}{\delta}$ and any $C\geqslant
q^{-2(1-\delta^{3})\ell}$, the number of $(C,\frac{1}{5})$-maximal zoom-out,
function pairs with respect to $T$ on $Q$ is at most $\frac{40}{\delta}\cdot
C^{-2}\cdot q^{100\left(t-1\right)!r^{2}\ell\xi^{-1}}$.

###### Proof.

Suppose for the sake of contradiction that
$(W_{1},f_{1}),\ldots,(W_{M},f_{M})$ are
$M>\frac{40}{\delta}C^{-2}q^{100(t-1)!r^{2}\ell\xi^{-1}}$ distinct pairs that
are $(C,\frac{1}{5})$ maximal with respect to $T$ on $Q$. By Lemma 5.20, for
each $W_{i}$, there are at most $4C^{-2}$ functions
$f:W\xrightarrow[]{}\mathbb{F}_{q}$ such that $f|_{L}\equiv T[L]$ for at least
$C$-fraction of the $L\in{\sf Zoom}[Q,W]$. Thus, there are $C^{2}M/4$ distinct
$W_{i}$’s appearing in the pairs, and there is a codimension
$r_{2}\leqslant\frac{10}{\delta}$ such there are
$\frac{M}{\frac{40}{\delta}C^{-2}}=N\geqslant
q^{100\left(t-1\right)!r^{2}\ell\xi^{-1}}$ pairs, say,
$(W_{1},f_{1}),\ldots,(W_{N},f_{N})$ zoom-out function pairs that are
$(C,\frac{1}{5})$ maximal with respect to $T$ on $Q$ such that the $W_{i}$’s
are all distinct and of codimension $r_{2}$ in $\mathbb{F}_{q}^{V}$.

Write $\mathbb{F}_{q}^{V}=Q\oplus A$. For each $L\subseteq\mathbb{F}_{q}^{V}$
of dimension $2\ell$ containing $Q$, there is a unique $L^{\prime}\subseteq A$
such that $L=Q\oplus L^{\prime}$. Define the table $T^{\prime}$ that assigns
linear functions to each $L^{\prime}\in{\sf Grass}_{q}(A,2\ell-\dim(Q))$ by

$T^{\prime}[L^{\prime}]\equiv T[L^{\prime}\oplus Q]|_{L^{\prime}}$ (8)

For each $1\leqslant i\leqslant N$, let $W^{\prime}_{i}\subseteq A$ be the
unique subspace such that $W_{i}=W^{\prime}_{i}\oplus Q$. We have that
$f_{i}|_{L^{\prime}}=T^{\prime}[L^{\prime}]$ for at least $C$-fraction of
$L^{\prime}\in{\sf Grass}_{q}(W^{\prime}_{i},2\ell-\dim(Q))$.

By Lemma 5.19 there exists a subspace $V^{\prime}$, a linear function
$h^{\prime}:V^{\prime}\xrightarrow[]{}\mathbb{F}_{q}$, and a subcollection
$\mathcal{W}^{\prime}\subseteq\\{W^{\prime}_{1},\ldots,W^{\prime}_{m}\\}$ of
size at least $m\geqslant q^{50r\ell\xi^{-1}}$ such that

  * •

Each $W^{\prime}_{i}\in\mathcal{W}^{\prime}$ is has codimension $1\leqslant
r^{\prime}\leqslant r_{2}$ with respect to $V^{\prime}$.

  * •

$\mathcal{W}^{\prime}$ is $2$-generic with respect to $V^{\prime}$.

  * •

For any $W^{\prime}_{i}\in\mathcal{W}$, $h^{\prime}|_{W^{\prime}_{i}}=f_{i}$.

Let $\mathcal{W}=\\{W_{i}\;|\;W^{\prime}_{i}\in\mathcal{W}^{\prime}\\}$ and
extend $h^{\prime}$ to the function $h^{\star}$ on $V^{\star}=V^{\prime}\oplus
Q$ so that, $h^{\star}|_{W_{i}}\equiv f_{i}$ for at least $q^{-r_{1}}$ of the
$W_{i}$ in $\mathcal{W}$. It follows that there is a set
$\mathcal{V}=\\{W_{i}\in\mathcal{W}\;|\;h^{\star}|_{W_{i}}\equiv f_{i}\\}$ of
size $|\mathcal{V}|\geqslant mq^{-r_{2}}\geqslant mq^{-\frac{10}{\delta}}$.

Furthermore, because $\mathcal{W}^{\prime}$ is $2$-generic inside of
$V^{\prime}$, $\mathcal{W}$ is $2$-generic inside of $V^{\star}$. We will now
finish the proof by applying Lemma 5.14 on $\mathcal{V}$. Specifically, let
$\nu$ denote the measure over ${\sf Zoom}[Q,W^{\star}]$ generated by choosing
$W_{i}\in\mathcal{V}$ and then $L\in{\sf Zoom}[Q,W^{\star}]$ conditioned on
$L\subseteq W_{i}$, let $\mu$ denote the uniform measure over ${\sf
Zoom}[Q,W^{\star}]$, and let

$\mathcal{L}=\\{L\subseteq{\sf Zoom}[Q,V^{\star}]\;|\;h^{\star}|_{L}\equiv
T[L]\\}.$

Since $h^{\star}|_{W_{i}}\equiv f_{i}$ for every $W_{i}\in\mathcal{V}$, we
have

$\nu(\mathcal{L})\geqslant\mathop{\mathbb{E}}_{W_{i}\in\mathcal{V}}\left[\Pr_{L\in{\sf
Zoom}[Q,W_{i}]}[f_{i}|_{L}\equiv T[L]]\right]\geqslant C.$

By Lemma 5.14 with $a=r_{1},r=r_{2},$ and $j=2\ell$, it follows that

$\mu(\mathcal{L})\geqslant\frac{1}{2}\cdot\left(C-\frac{3q^{r_{2}}(2\ell-
r_{1})}{\sqrt{m}q^{-r_{1}}}\right)\geqslant\frac{C}{5}.$

Summing everything up, this shows that there is a zoom-out function pair
$(V^{\star},h^{\star})$ such that $V^{\star}\supsetneq W_{i}$ and
$h^{\star}|_{W_{i}}\equiv f_{i}$ for at least one $i$, and
$\Pr_{L\subseteq{\sf
Grass}_{q}(\mathbb{F}_{q}^{V},2\ell)}[h^{\star}|_{L}\equiv T[L]\;|\;Q\subseteq
L\subseteq V^{\star}]\geqslant\frac{C}{5}$. This contradicts the assumption
that $(W_{i},f_{i})$ is $(C,\frac{1}{5})$-maximal with respect to $T$ on $Q$.
∎

###  5.4 An Auxiliary Lemma

We conclude this section with an auxiliary lemma that will be used in the
analysis.

######  Lemma 5.22.

Let $U$ be a fixed question to the first prover in the Outer PCP consisting of
$3k$-variables in some set of $k$ equations. Let $V\subseteq U$ be a random
question to the second prover chosen according to the Outer PCP. Let
$W\subseteq\mathbb{F}_{q}^{U}$ be a subspace of co-dimension $s$. Then, with
probability at least $1-2s\beta$ over the choice of the question $V$, we have

$\dim(W\cap\mathbb{F}_{q}^{V})=|V|-s.$

###### Proof.

Say that $W$ is given by the constraints $\langle
h_{1},x\rangle=0,\ldots,\langle h_{s},x\rangle=0$ for $h_{1},\ldots,h_{s}$
linearly independent. We can view
$\mathbb{F}_{q}^{V}\subseteq\mathbb{F}_{q}^{U}$ as being defined by the
constraints $\langle v_{i_{1}},x\rangle=0,\ldots,\langle
v_{i_{t}},x\rangle=0$, where $i_{1},\ldots,i_{t}$ correspond to the variables
$x_{i_{1}},\ldots,x_{i_{t}}$ in $U\setminus V$. The event
$\dim(W\cap\mathbb{F}_{q}^{V})=|V|-s$ is equivalent to the event that
$h_{1},\ldots,h_{b},v_{i_{1}},\ldots,v_{i_{t}}$ are linearly independent.
Since $h_{1},\ldots,h_{s}$ are linearly independent, there are $s$-coordinates
such that the restrictions of $h_{1},\ldots,h_{s}$ to these $s$-coordinates
are linearly independent. If none of $i_{1},\ldots,i_{t}$ are in this set of
$s$ coordinates, then $h_{1},\ldots,h_{b},x_{i_{1}},\ldots,x_{i_{t}}$ are
linearly independent. Conditioned on the size of $U\setminus V$ being $t$,
this event happens with probability at least $1-ts/k$, and as the expectation
of $t$ is $2\beta k$ it follows that the probability in question is at least
$1-2s\beta$. ∎

##  6 Analysis of the PCP

In this section we show completeness and soundness analysis of the composed
PCP construction $\Psi$ from Section 4. As usual, the completeness analysis is
straightforward and the soundness analysis will consist the bulk of our
effort.

###  6.1 Completeness