there are no distinct $i,j\in[k]$ such that $w_{i}=w_{j}$ but
$\alpha_{i}\neq\alpha_{j}$.

The distribution $\\{\mathbf{Z}_{w}\\}=\mu_{w}$ is defined as
$\mu_{w}(\alpha)=\mu_{S_{w}}(\alpha|_{S_{w}})$ if
$\alpha\in{\mathbb{F}}_{2}^{w}$ is plausible for $w$, and $\mu_{w}(\alpha)=0$
otherwise.

####  7.3.2 Tensoriality

A key algorithm in the list decoding framework is propagation rounding (7.16),
which solves a CSP to find solutions close to a codeword. Suppose
$W(k)\subseteq[n]^{k}$ is a collection of walks, or more generally, a
collection of any $k$-tuples. The algorithm starts with a local PSD ensemble
$\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ which is the solution to an SOS
program for list decoding. Propagation rounding takes this solution and
conditions some of the variables according to a random assignment to these
variables to yield another local PSD ensemble $\mathbf{Z}^{\prime}$.

######  Algorithm 7.16 (Propagation Rounding Algorithm, adapted from
[AJQ+20]).

Input An $(L+2k)$-local PSD ensemble
$\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ and collection
$W(k)\subseteq[n]^{k}$. Output A random assignment
$(\sigma_{1},\ldots,\sigma_{n})\in{\mathbb{F}}_{2}^{n}$ and $2k$-local PSD
ensemble $\mathbf{Z}^{\prime}$. 1. Choose $m\in\left\\{1,\ldots,L/k\right\\}$
uniformly at random. 2. For $j=1,\dots,m$, sample a walk $w_{j}$ independently
and uniformly from $W(k)$. 3. Write $S=\bigcup_{j=1}^{m}\textup{set}(w_{j})$
for the set of the seed vertices. 4. Sample an assignment
$\sigma:S\rightarrow{\mathbb{F}}_{2}$ according to the local distribution
$\\{\mathbf{Z}_{S}\\}$. 5. Set
$\mathbf{Z}^{\prime}=\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}|\mathbf{Z}_{S}=\sigma\\}$,
i.e. the local ensemble $\mathbf{Z}$ conditioned on agreeing with $\sigma$. 6.
For all $i\in[n]$, sample independently
$\sigma_{i}\sim\\{\mathbf{Z}^{\prime}_{i}\\}$. 7. Output
$(\sigma_{1},\ldots,\sigma_{n})$ and $\mathbf{Z}^{\prime}$.

If the collection $W(k)\subseteq[n]^{k}$ used in the direct sum lifting is
amenable to SOS rounding, the conditioned ensemble $\mathbf{Z}^{\prime}$ will
be able to recover a word close to some codeword on the list. This is
quantified by the following tensorial properties. We will see shortly how
splittability will be used to obtain tensoriality in our setting.

######  Definition 7.17 (Tensorial Walk Collection).

Let $W(k)\subseteq[n]^{k}$, $\mu\in[0,1]$, and $L\in\mathbb{N}$. Define
$\Omega$ to be the set of all tuples $(m,S,\sigma)$ obtainable in propagation
rounding (7.16) on $W(k)$ with SOS degree parameter $L$. We say that $W(k)$ is
$(\mu,L)$-tensorial if the local PSD ensemble $\mathbf{Z}^{\prime}$ returned
by propagation rounding satisfies

$\operatorname*{\mathbb{E}}_{\Omega}\operatorname*{\mathbb{E}}_{w\in
W(k)}{\left\lVert\\{\mathbf{Z}_{w}^{\prime}\\}-\left\\{\mathbf{Z}_{w(1)}^{\prime}\right\\}\cdots\left\\{\mathbf{Z}_{w(k)}^{\prime}\right\\}\right\rVert_{1}}\leq\mu.$
(4)

The framework actually uses a strengthening of the above property, in which
variables for pairs of walks chosen independently approximately behave as a
product.

######  Definition 7.18 (Two-Step Tensorial Walk Collection).

Let $W(k)\subseteq[n]^{k}$, $\mu\in[0,1]$, and $L\in\mathbb{N}$. Define
$\Omega$ to be the set of all tuples $(m,S,\sigma)$ obtainable in propagation
rounding (7.16) on $W(k)$ with SOS degree parameter $L$. We say that $W(k)$ is
$(\mu,L)$-two-step tensorial if it is $(\mu,L)$-tensorial and the local PSD
ensemble $\mathbf{Z}^{\prime}$ returned by propagation rounding satisfies the
additional condition

$\operatorname*{\mathbb{E}}_{\Omega}\operatorname*{\mathbb{E}}_{w,w^{\prime}\in
W(k)}{\left\lVert\\{\mathbf{Z}_{w}^{\prime}\mathbf{Z}_{w^{\prime}}^{\prime}\\}-\left\\{\mathbf{Z}_{w}^{\prime}\right\\}\left\\{\mathbf{Z}_{w^{\prime}}^{\prime}\right\\}\right\rVert_{1}}\leq\mu.$

####  7.3.3 From Directed to Undirected

In order to apply the list decoding framework using the directed split
operator $\mathsf{S}_{k_{1},k_{2},k_{3}}$, we will replace it with the
symmetrized version

$\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})=\begin{pmatrix}0&\mathsf{S}_{k_{1},k_{2},k_{3}}\\\
\left(\mathsf{S}_{k_{1},k_{2},k_{3}}\right)^{{\dagger}}&0\end{pmatrix}$

and show how $\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})$ corresponds to a
particular undirected graph.

######  Definition 7.19.

Let $0\leq k_{1}\leq k_{2}<k_{3}$. We define the operator
$\mathfrak{S}_{k_{2},k_{3},k_{1}}\colon\mathbb{R}^{W[k_{1},k_{2}]}\rightarrow\mathbb{R}^{W[k_{2}+1,k_{3}]}$
such that for every $f\in{\mathbb{R}}^{W[k_{1},k_{2}]}$,

$\left(\mathfrak{S}_{k_{2},k_{3},k_{1}}(f)\right)(w^{\prime})\coloneqq{\mathbb{E}}_{w:ww^{\prime}\in
W[k_{1},k_{3}]}[f(w)],$

for every $w^{\prime}\in W[k_{2}+1,k_{3}]$.

The operator $\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})$ defines an
undirected weighted bipartite graph on the vertices $W[k_{1},k_{2}]\cup
W[k_{2}+1,k_{3}]$. We can see that $\mathfrak{S}_{k_{2},k_{3},k_{1}}$ is the
adjoint of $\mathsf{S}_{k_{1},k_{2},k_{3}}$, which means that each edge
$ww^{\prime}$ in this graph is weighted according to the transition
probability from one walk to the other whenever one of $w$, $w^{\prime}$ is in
$W[k_{1},k_{2}]$ and the other is in $W[k_{2}+1,k_{3}]$.

######  Claim 7.20.

$\left(\mathsf{S}_{k_{1},k_{2},k_{3}}\right)^{{\dagger}}=\mathfrak{S}_{k_{2},k_{3},k_{1}}.$

###### Proof.

Let $f\in C^{W[k_{1},k_{2}]}$ and $g\in C^{W[k_{2}+1,k_{3}]}$. For $i\leq j$,
define $\Pi_{i,j}$ to be the uniform distribution on $W[i,j]$. We show that
$\left\langle
f,\mathsf{S}_{k_{1},k_{2},k_{3}}g\right\rangle=\left\langle\mathfrak{S}_{k_{2},k_{3},k_{1}}f,g\right\rangle$.
On one hand we have

$\displaystyle\left\langle f,\mathsf{S}_{k_{1},k_{2},k_{3}}g\right\rangle$
$\displaystyle={\mathbb{E}}_{w\in
W[k_{1},k_{2}]}\left[f(w){\mathbb{E}}_{w^{\prime}:ww^{\prime}\in
W[k_{1},k_{3}]}[g(w^{\prime})]\right]$ $\displaystyle={\mathbb{E}}_{w\in
W[k_{1},k_{2}]}\left[f(w)\sum_{w^{\prime}\in
W[k_{2}+1,k_{3}]}\frac{\Pi_{k_{1},k_{3}}(ww^{\prime})}{\Pi_{k_{1},k_{2}}(w)}g(w^{\prime})\right]$
$\displaystyle=\sum_{w\in
W[k_{1},k_{2}]}\Pi_{k_{1},k_{2}}(w)f(w)\sum_{w^{\prime}\in
W[k_{2}+1,k_{3}]}\frac{\Pi_{k_{1},k_{3}}(ww^{\prime})}{\Pi_{k_{1},k_{2}}(w)}g(w^{\prime})$
$\displaystyle=\sum_{ww^{\prime}\in
W[k_{1},k_{3}]}f(w)g(w^{\prime})\Pi_{k_{1},k_{3}}(ww^{\prime}).$

On the other hand we have

$\displaystyle\left\langle\mathfrak{S}_{k_{2},k_{3},k_{1}}f,g\right\rangle$
$\displaystyle={\mathbb{E}}_{w^{\prime}\in
W[k_{2}+1,k_{3}]}\left[{\mathbb{E}}_{w:ww^{\prime}\in
W[k_{1},k_{3}]}[f(w)]g(w^{\prime})\right]$
$\displaystyle={\mathbb{E}}_{w^{\prime}\in W[k_{2}+1,k_{3}]}\left[\sum_{w\in
W[k_{1},k_{2}]}\frac{\Pi_{k_{1},k_{3}}(ww^{\prime})}{\Pi_{k_{2}+1,k_{3}}(w^{\prime})}f(w)g(w^{\prime})\right]$
$\displaystyle=\sum_{w^{\prime}\in
W[k_{2}+1,k_{3}]}\Pi_{k_{2}+1,k_{3}}(w^{\prime})\sum_{w\in
W[k_{1},k_{2}]}\frac{\Pi_{k_{1},k_{3}}(ww^{\prime})}{\Pi_{k_{2}+1,k_{3}}(w^{\prime})}f(w)g(w^{\prime})$
$\displaystyle=\sum_{ww^{\prime}\in
W[k_{1},k_{3}]}f(w)g(w^{\prime})\Pi_{k_{1},k_{3}}(ww^{\prime}).$

Hence,
$\mathfrak{S}_{k_{2},k_{3},k_{1}}=(\mathsf{S}_{k_{1},k_{2},k_{3}})^{{\dagger}}$
as claimed.

####  7.3.4 Variables for Walks on the $s$-wide Replacement Product

When analyzing walks on the $s$-wide replacement product, we actually need to
use two separate, but related, local PSD ensembles. In Ta-Shma’s construction,
the vertices of the outer graph $G$ correspond to positions in the base code
$\mathcal{C}_{0}\subseteq{\mathbb{F}}_{2}^{n}$, where $n=\left\lvert
V(G)\right\rvert$. Given a vertex $(v,h)\in V(G)\times V(H)$ in the $s$-wide
replacement product and codeword $z\in\mathcal{C}_{0}$, $(v,h)$ is assigned
bit $z_{v}$, regardless of the vertex $h$ of the inner graph. We will enforce
this property by working with variables in $V(G)$ rather than the full
$V(G)\times V(H)$. The local PSD ensemble
$\mathbf{Z}=\\{\mathbf{Z}_{v}\\}_{v\in V(G)}$ contains one variable for every
vertex of $G$, with local distributions for sets of variables up to a given
size. For a walk $w$ on the $s$-wide replacement product, we will use
$\mathbf{Z}_{w}$ as an abbreviation for $\mathbf{Z}_{S_{w}}$, where $S_{w}$ is
the set of all $G$-components of vertices visited on the walk.

The constraints of the CSP are placed on walks on the $s$-wide replacement
product that do care about the $H$-component of the vertices, so we define a
second local PSD ensemble $\mathbf{Y}=\\{\mathbf{Y}_{(v,h)}\\}_{(v,h)\in
V(G)\times V(H)}$ with a variable for each vertex of the $s$-wide replacement
product of $G$ and $H$. It is this collection $\mathbf{Y}$ for which we need
to prove tensoriality in order to use the list decoding framework. When we
perform propagation rounding, we condition the ensemble $\mathbf{Z}$ on a
random assignment $\sigma$ to a subset $S\subseteq V(G)$, rather than
conditioning $\mathbf{Y}$ on a random assignment to a subset of $V(G)\times
V(H)$. Working with $\mathbf{Z}$ ensures that the rounded assignments will be
consistent on each cloud of the $s$-wide replacement product. Since the bit
assigned to a vertex $(v,h)$ only depends on $v$, independent rounding of
$\\{\mathbf{Z}\mid\mathbf{Z}_{S}=\sigma\\}$ will also yield the desired
rounding of $\\{\mathbf{Y}\mid\mathbf{Z}_{S}=\sigma\\}$.

We can define $\mathbf{Y}$ based on the ensemble $\mathbf{Z}$ more concretely.
Suppose $S^{\prime}\subseteq V(G)\times V(H)$ is a subset of size at most $p$,
where $p$ is the locality of the ensemble, and define $T=\\{v\mid(v,h)\in
S^{\prime}\\}$. The distribution $\mu_{S^{\prime}}$ of
$\mathbf{Y}_{S^{\prime}}$ is defined based on the distribution $\mu_{T}$ of
$\mathbf{Z}_{T}$ by $\mu_{S^{\prime}}(\alpha)=\mu_{T}(\alpha|_{T})$, where
$\alpha\in{\mathbb{F}}_{2}^{S^{\prime}}$ is an assignment to $S^{\prime}$
whose value on each vertex $(v,h)$ only depends on $v$.

Observe that the introduction of the ensemble $\mathbf{Y}$ is only necessary
on the first level of the Ta-Shma code cascade between the codes
$\mathcal{C}_{0}$ and $\mathcal{C}_{1}$, which takes place on the $s$-wide
replacement product. Higher levels of the cascade use walks on graphs whose
vertices are the walks from the level below. The association of the bits of a
codeword to the vertices of this graph has no consistency requirement, so we
simply use a single local ensemble $\mathbf{Z}$ with a variable for each
vertex.

###  7.4 Splittability Implies Tensoriality

The connection between splittability and tensoriality will be made with the
help of a version of the triangle inequality.

######  Claim 7.21 (Triangle inequality, adapted from [AJQ+20]).

Let $s\in\mathbb{N}^{+}$ and $\mathcal{T}$ be an $s$-interval splitting tree.
Then

$\operatorname*{\mathbb{E}}_{w\in
W[0,s-1]}{\left\lVert\\{\mathbf{Z}_{w}\\}-\prod_{i=0}^{s-1}\left\\{\mathbf{Z}_{w(i)}\right\\}\right\rVert_{1}}\leq\sum_{(k_{1},k_{2},k_{3})\in\mathcal{T}}~{}\operatorname*{\mathbb{E}}_{w\in
W[k_{1},k_{3}]}{\left\lVert\\{\mathbf{Z}_{w}\\}-\left\\{\mathbf{Z}_{w(k_{1},k_{2})}\right\\}\left\\{\mathbf{Z}_{w(k_{2}+1,k_{3})}\right\\}\right\rVert_{1}},$

where the sum is taken over the labels of the internal nodes of $\mathcal{T}$.

To prove tensoriality, we will use the method of [BRS11] and [AJT19] to show
that we can break correlations over expanding collections of tuples arising in
the $s$-wide replacement product of the form

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}ww^{\prime}\in
W[k_{1},k_{3}]\\\ w\in W[k_{1},k_{2}],w^{\prime}\in
W[k_{2}+1,k_{3}]\end{subarray}}{\left\lVert\\{\mathbf{Z}_{ww^{\prime}}\\}-\\{\mathbf{Z}_{w}\\}\\{\mathbf{Z}_{w^{\prime}}\\}\right\rVert_{1}}$

appearing on the right-hand side of the triangle inequality.

####  7.4.1 The First Level of the Cascade

We now check the technical details to obtain tensoriality for the first
lifting in the code cascade between the codes $\mathcal{C}_{0}$ and
$\mathcal{C}_{1}$, which corresponds to taking $s$ steps in Ta-Shma’s
construction. Recall that in order to obtain an assignment
$z^{\prime}\in\mathbb{F}_{2}^{n}$ whose lifting is consistent on vertices with
the same $G$-component, we need to prove tensoriality for the ensemble
$\mathbf{Y}$ with a variable for each vertex in $V(G)\times V(H)$.

The proof of tensoriality will make use of a specific entropic potential
function. For an arbitrary random variable $\mathbf{X}$ taking values in a
finite set $[q]$, define the function $\mathcal{H}(\mathbf{X})$ as

$\mathcal{H}(\mathbf{X})~{}\coloneqq~{}\frac{1}{q}\sum_{a\in[q]}\textup{H}(\mathbb{1}_{[\mathbf{X}=a]})~{}=~{}{\mathbb{E}}_{a\in[q]}\textup{H}(\mathbb{1}_{[\mathbf{X}=a]}),$

where H is the binary entropy function. Using this, we define a potential
function for a weighted undirected graph $G$.

######  Definition 7.22 (Graph Potential).

Let $G=(V,E)$ be a weighted graph with edge distribution $\Pi_{E}$. Let
$\Pi_{V}$ be the marginal distribution on $V$. Suppose that
$\\{\mathbf{Y}_{i}\\}_{i\in V}$ is a $p$-local PSD ensemble for some $p\geq
1$. We define $\Phi^{G}$ to be

$\Phi^{G}~{}\coloneqq~{}\mathchoice{\underset{i\sim\Pi_{V}}{\mathbb{E}}\left[\mathcal{H}(\mathbf{Y}_{i})\right]}{{\mathbb{E}}_{i\sim\Pi_{V}}[\mathcal{H}(\mathbf{Y}_{i})]}{{\mathbb{E}}_{i\sim\Pi_{V}}[\mathcal{H}(\mathbf{Y}_{i})]}{{\mathbb{E}}_{i\sim\Pi_{V}}[\mathcal{H}(\mathbf{Y}_{i})]}.$

Let $\mathcal{T}$ be an $s$-interval splitting tree associated with the
$s$-wide replacement product of graphs $G$ and $H$. We define

$\Phi^{\mathcal{T}}\coloneqq\sum_{(k_{1},k_{2},k_{3})\in\mathcal{T}}\Phi^{\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})},$

where $\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})$ is the associated
bipartite undirected graph of the operator $\mathsf{S}_{k_{1},k_{2},k_{3}}$.

######  Lemma 7.23 (Splittability Implies Tensoriality).

Let $W[0,s-1]$ be the walk collection of the $s$-wide replacement product of
two graphs $G$ and $H$. If $L\geq 128\cdot(s^{4}\cdot 2^{4s}/\mu^{4})$ and
$W[0,s-1]$ is $\tau$-splittable with $\tau\leq\mu/(4s\cdot 2^{4s})$, then
$W[0,s-1]$ is $(\mu,L)$-tensorial.

###### Proof.

We need to show that

$\operatorname*{\mathbb{E}}_{w\in
W[0,s-1]}{\left\lVert\\{\mathbf{Y}_{w}^{\prime}\\}-\prod_{i=0}^{s-1}\left\\{\mathbf{Y}_{w(i)}^{\prime}\right\\}\right\rVert_{1}}\leq\mu,$

which can be proven by adapting a potential argument technique from [BRS11].
First, set the potential

$\Phi_{m}=\operatorname*{\mathbb{E}}_{S\sim\Pi_{m}}{\operatorname*{\mathbb{E}}_{\sigma\sim\\{\mathbf{Z}_{S}\\}}{\Phi^{\mathcal{T}}_{\mid\mathbf{Z}_{S}=\sigma}}},$
(5)

where the distribution $\Pi_{m}$ on $S\subseteq V(G)$ is obtained from the
process of choosing $S$ in propagation rounding (7.16) once $m$ has been
fixed. Consider the error term

$\mu_{m}\coloneqq\operatorname*{\mathbb{E}}_{S\sim\Pi_{m}}{\operatorname*{\mathbb{E}}_{\sigma\sim\\{\mathbf{Z}_{S}\\}}{D(S,\sigma)}},$
(6)

where $D(S,\sigma)\coloneqq\operatorname*{\mathbb{E}}_{w\in
W[0,s-1]}\left\lVert\\{\mathbf{Y}_{w}\mid\mathbf{Z}_{S}=\sigma\\}-\prod_{i=0}^{s-1}\left\\{\mathbf{Y}_{w(i)}\mid\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}$.
If $\mu_{m}\geq\mu/2$, then

$\operatorname*{\mathbb{P}}_{S\sim\Pi_{m},\sigma\sim\\{\mathbf{Z}_{S}\\}}\left[D(S,\sigma)\geq\mu_{m}/2\right]\geq\frac{\mu}{4}.$

For each choice of $S$ and $\sigma$ such that $D(S,\sigma)\geq\mu/2$, applying
the triangle inequality from 7.21 to the conditioned variables gives us

$\displaystyle\frac{\mu}{2}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{w\in
W[0,s-1]}{\left\lVert\\{\mathbf{Y}_{w}\mid\mathbf{Z}_{S}=\sigma\\}-\prod_{i=0}^{s-1}\left\\{\mathbf{Y}_{w(i)}\mid\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}$
$\displaystyle\leq\sum_{(k_{1},k_{2},k_{3})\in\mathcal{T}}~{}\operatorname*{\mathbb{E}}_{w\in
W[k_{1},k_{3}]}{\left\lVert\\{\mathbf{Y}_{w}\mid\mathbf{Z}_{S}=\sigma\\}-\left\\{\mathbf{Y}_{w(k_{1},k_{2})}\mid\mathbf{Z}_{S}=\sigma\right\\}\left\\{\mathbf{Y}_{w(k_{2}+1,k_{3})}\mid\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}.$

Hence, there exists $(k_{1},k_{2},k_{3})$ such that

$\frac{\mu}{2s}\leq\operatorname*{\mathbb{E}}_{w\in
W[k_{1},k_{3}]}{\left\lVert\\{\mathbf{Y}_{w}\mid\mathbf{Z}_{S}=\sigma\\}-\left\\{\mathbf{Y}_{w(k_{1},k_{2})}\mid\mathbf{Z}_{S}=\sigma\right\\}\left\\{\mathbf{Y}_{w(k_{2}+1,k_{3})}\mid\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}.$

Note that choosing $w\in W[0,s-1]$ uniformly and restricting to
$w(k_{1},k_{3})$ gives a uniformly random element of $W[k_{1},k_{3}]$. If we
choose $w(k_{1},k_{2})$ or $w(k_{2}+1,k_{3})$ with equal probability, then the
final walk is distributed according to the stationary measure of
$\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})$. Let $w^{\prime}$ denote the
chosen walk. Observe that $\mathbf{Y}_{w^{\prime}}$ is a deterministic
function of $\mathbf{Z}_{w^{\prime}}\mid\mathbf{Z}_{S}=\sigma$. Now, we sample
$\mathbf{Z}_{w^{\prime}}\mid\mathbf{Z}_{S}=\sigma$, which gives us a sample of
$\mathbf{Y}_{w^{\prime}}$. Applying Lemma A.1, we have

$\Phi^{\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})}_{|\\{\mathbf{Y}_{w^{\prime}}|\mathbf{Z}_{S}=\sigma\\}}\leq\Phi^{\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})}_{\mathbf{Z}_{S}=\sigma}-\frac{\mu^{2}}{16s^{2}\cdot
2^{4s}}.$

This conditioning on an assignment to
$\mathbf{Z}_{\textup{set}(w^{\prime})}\mid\mathbf{Z}_{S}=\sigma$ does not
increase the other terms of $\Phi^{\mathcal{T}}$ associated to split operators
other than $\mathcal{U}(\mathsf{S}_{k_{1},k_{2},k_{3}})$ since entropy is non-
increasing under conditioning. Similarly, conditioning on the remaining
variables that are part of $w$ but not $w^{\prime}$ does not increase
$\Phi^{\mathcal{T}}$. Then, we obtain

$\Phi_{m}-\Phi_{m+1}\geq\operatorname*{\mathbb{P}}_{S\sim\Pi_{m},\sigma\sim\\{\mathbf{Z}_{S}\\}}\left[D(S,\sigma)\geq\mu_{m}/2\right]\cdot\frac{\mu^{2}}{16s^{2}\cdot
2^{4s}}.$

Since $s\geq\Phi_{1}\geq\cdots\geq\Phi_{L/(s+1)}\geq 0$, there can be at most
$32s^{3}\cdot 2^{4s}/\mu^{3}$ indices $m\in[L/s]$ such that
$\mu_{m}\geq\mu/2$. In particular, since the total number of indices is $L/s$,
we have

$\operatorname*{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]\leq\frac{\mu}{2}+\frac{s}{L}\cdot\frac{32s^{3}\cdot
2^{4s}}{\mu^{3}}.$

Our choice of $L$ is more than enough to ensure
$\mathchoice{\underset{m\in[L/s]}{\mathbb{E}}\left[\mu_{m}\right]}{{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]}{{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]}{{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]}\leq\mu$.

Applying the list decoding framework will require the stronger property of
two-step tensoriality, which we can obtain under the same assumptions.

######  Lemma 7.24 (Splittability Implies Two-step Tensoriality).

Let $W[0,s-1]$ be the walk collection of the $s$-wide replacement product of
two graphs $G$ and $H$. If $L\geq 128\cdot(s^{4}\cdot 2^{4s}/\mu^{4})$ and
$W[0,s-1]$ is $\tau$-splittable with $\tau\leq\mu/(4s\cdot 2^{4s})$, then
$W[0,s-1]$ is $(\mu,L)$-two-step tensorial.

###### Proof.

Under our assumptions the $(\mu,L)$-tensorial property follows from Lemma 7.23
(which is the only place where the assumption on $\tau$ is used), so we only
need to show

$\operatorname*{\mathbb{E}}_{w,w^{\prime}\in
W[0,s-1]}{\left\lVert\\{\mathbf{Y}_{w}^{\prime}\mathbf{Y}_{w^{\prime}}^{\prime}\\}-\left\\{\mathbf{Y}_{w}^{\prime}\right\\}\left\\{\mathbf{Y}_{w^{\prime}}^{\prime}\right\\}\right\rVert_{1}}\leq\mu,$

which can be proven by adapting a potential argument technique from [BRS11].
First, set the potential

$\Phi_{m}=\operatorname*{\mathbb{E}}_{S\sim\Pi_{m}}{\operatorname*{\mathbb{E}}_{\sigma\sim\\{\mathbf{Z}_{S}\\}}{\operatorname*{\mathbb{E}}_{w\in
W[0,s-1]}{\mathcal{H}(\mathbf{Y}_{w}\mid\mathbf{Z}_{S}=\sigma)}}},$ (7)

where the distribution $\Pi_{m}$ on $S\subseteq V(G)$ is obtained from the
process of choosing $S$ in propagation rounding (7.16) once $m$ has been
fixed. Consider the error term

$\mu_{m}\coloneqq\operatorname*{\mathbb{E}}_{S\sim\Pi_{m}}{\operatorname*{\mathbb{E}}_{\sigma\sim\\{\mathbf{Z}_{S}\\}}{D(S,\sigma)}},$
(8)

where $D(S,\sigma)\coloneqq\mathchoice{\underset{w,w^{\prime}\in
W[0,s-1]}{\mathbb{E}}\left[\left\lVert\\{\mathbf{Y}_{w}\mathbf{Y}_{w^{\prime}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Y}_{w}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Y}_{w^{\prime}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}\right]}{{\mathbb{E}}_{w,w^{\prime}\in
W[0,s-1]}[\left\lVert\\{\mathbf{Y}_{w}\mathbf{Y}_{w^{\prime}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Y}_{w}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Y}_{w^{\prime}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}]}{{\mathbb{E}}_{w,w^{\prime}\in
W[0,s-1]}[\left\lVert\\{\mathbf{Y}_{w}\mathbf{Y}_{w^{\prime}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Y}_{w}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Y}_{w^{\prime}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}]}{{\mathbb{E}}_{w,w^{\prime}\in
W[0,s-1]}[\left\lVert\\{\mathbf{Y}_{w}\mathbf{Y}_{w^{\prime}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Y}_{w}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Y}_{w^{\prime}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}]}$.
If $\mu_{m}\geq\mu/2$, then

$\operatorname*{\mathbb{P}}_{S\sim\Pi_{m},\sigma\sim\\{\mathbf{Z}_{S}\\}}\left[D(S,\sigma)\geq\mu_{m}/2\right]\geq\frac{\mu}{4}.$

Let $G^{\prime}=(V=W[0,s-1],E)$ be the graph with edges
$E=\\{\\{w,w^{\prime}\\}\mid w,w^{\prime}\in W[0,s-1]\\}$. Local correlation
(expectation over the edges) on this graph $G^{\prime}$ is the same as global
correlation (expectation over two independent copies of vertices). Then, we
obtain 888See [AJT19] or [BRS11] for the details.

$\Phi_{m}-\Phi_{m+1}\geq\operatorname*{\mathbb{P}}_{S\sim\Pi_{m},\sigma\sim\\{\mathbf{Z}_{S}\\}}\left[D(S,\sigma)\geq\mu_{m}/2\right]\cdot\frac{\mu^{2}}{2\cdot
2^{2s}}.$

Since $1\geq\Phi_{1}\geq\cdots\geq\Phi_{L/(s+1)}\geq 0$, there can be at most
$8\cdot 2^{2s}/\mu^{3}$ indices $m\in[L/s]$ such that $\mu_{m}\geq\mu/2$. In
particular, since the total number of indices is $L/s$, we have

$\operatorname*{\mathbb{E}}_{m\in[L/s]}{\mu_{m}}\leq\frac{\mu}{2}+\frac{k}{L}\cdot\frac{8\cdot
2^{2s}}{\mu^{3}}.$

Our choice of $L$ is more than enough to ensure
$\mathchoice{\underset{m\in[L/s]}{\mathbb{E}}\left[\mu_{m}\right]}{{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]}{{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]}{{\mathbb{E}}_{m\in[L/s]}[\mu_{m}]}\leq\mu$.

We have already established that $W[0,s-1]$ is $\tau$-splittable with
$\tau=\sigma_{2}(G)+2\sigma_{2}(H)+\sigma_{2}(H)^{2}$ in Corollary 7.13, so we
can obtain $(\mu,L)$-two-step tensoriality for any $\mu$ if this quantity is
small enough.

####  7.4.2 Higher Levels of the Cascade

We now discuss tensoriality of the other levels of the cascade between
$\mathcal{C}_{i-1}$ and $\mathcal{C}_{i}$ for $i\geq 2$. Tensorial properties
are simpler to establish here than on the first level of the cascade. The
relevant split operators are special cases of $\mathsf{S}_{k_{1},k_{2},k_{3}}$
where $k_{1}\equiv 0\pmod{s}$ and $k_{2},k_{3}\equiv-1\pmod{s}$. The main
difference now is that we can associate the parity bits of $\mathcal{C}_{i-1}$
with the vertices of $\mathcal{U}(\mathsf{S}_{r,r}^{\bigtriangleup})$, which
themselves represent walks. As this association of parity bits doesn’t need to
satisfy a consistency condition, we only need to work with a single ensemble
$\mathbf{Z}$ instead of working with two different ensembles as in the
previous case. The proofs of Lemma 7.23 and Lemma 7.24 with these slight
modifications give us two-step tensoriality.

######  Lemma 7.25 (Two-step Tensoriality for Higher Levels).

Let $W(k)$ be the set of walks defined using $(k-1)$ steps of the operator
$\mathsf{S}_{r,r}^{\bigtriangleup}$. If $L\geq 128\cdot(k^{4}\cdot
2^{4k}/\mu^{4})$ and $W(k)$ is $\tau$-splittable with $\tau\leq\mu/(4k\cdot
2^{4k})$, then $W(k)$ is $(\mu,L)$-two-step tensorial.

We know that the collection of walks obtained from
$\sigma_{2}(\mathsf{S}_{r,r}^{\bigtriangleup})$ is
$(\sigma_{2}(G)+2\cdot\sigma_{2}(H)+\sigma_{2}(H)^{2})$-splittable, so the
parameters necessary to obtain two-step tensoriality are the same as in the
first level of the cascade.

##  8 Choosing Parameters for Ta-Shma’s Construction

We explore how some choices of parameters for Ta-Shma’s construction interact
with the requirements of our decoding algorithm. The analysis is divided into
rounds of increasingly stronger decoding guarantees with later rounds relying
on the codes obtained in previous rounds. Naturally, the stronger guarantees
come with more delicate and technical considerations. We briefly summarize the
goals of each round and some key parameters.

  1. 1.

Round I: For any constant $\beta>0$, we obtain _efficient unique decodable_
codes $\mathcal{C}_{\ell}$ with distance at least $1/2-\varepsilon$ and rate
$\Omega(\varepsilon^{2+\beta})$ for infinitely many _discrete_ values of
$\varepsilon>0$ (with $\varepsilon$ as close to $0$ as desired). In this
regime, it suffices for the expansion of $H$ to be constant. This round leads
to Theorem 6.6.

  2. 2.

Round II: Similar to Round I, but now $\varepsilon$ can be any value in an
interval $(0,b)$ with $b<1/2$ being a function of $\beta$. Again the expansion
of $H$ can be constant. This round leads to Theorem 6.7.

  3. 3.

Round III: We want $\beta$ to vanish as $\varepsilon$ vanishes (this is
qualitatively similar to Ta-Shma’s result). In this regime, we make the
expansion of $H$ be a function of $\varepsilon$, and we rely on the uniquely
decodable codes of Round II. This round leads to Theorem 1.1.

  4. 4.

Round IV: For any constant $\beta_{0}>0$, we obtain _efficient list decodable_
codes $\mathcal{C}_{\ell}$ with list decoding radius $1/2-\beta_{0}$ and rate
$\Omega(\varepsilon^{2+\beta})$ with $\beta\rightarrow 0$ as
$\varepsilon\rightarrow 0$. In this regime, we make the expansion of $H$ be a
function of $\varepsilon$, and we rely on the uniquely decodable codes of
Round III. This round leads to Theorem 1.2.

The way we choose parameters for Ta-Shma’s construction borrows heavily from
Ta-Shma’s arguments in [TS17]. We fix some notation common to all rounds. A
graph is said to be an $(n,d,\lambda)$-graph provided it has $n$ vertices, is
$d$-regular, and has second largest singular value of its normalized adjacency
matrix at most $\lambda$.

######  Notation 8.1.

We use the following notation for the graphs $G$ and $H$ used in the $s$-wide
replacement product.

  * -

The outer graph $G$ will be an $(n^{\prime},d_{1},\lambda_{1})$-graph.

  * -

The inner graph $H$ will be a $(d_{1}^{s},d_{2},\lambda_{2})$-graph.

The parameters $n^{\prime},d_{1},d_{2},\lambda_{1},\lambda_{2}$ and $s$ will
be chosen in the subsequent sections.

###  8.1 Round I: Initial Analysis

We are given the dimension $D$ of the desired code and
$\varepsilon\in(0,1/2)$. We set a parameter $\alpha\leq 1/128$ such that (for
convenience) $1/\alpha$ is a power of $2$ and

$\frac{\alpha^{5}}{4\log_{2}(1/\alpha)}\geq\frac{1}{\log_{2}(1/\varepsilon)}.$
(9)

We can assume that $\alpha\leq 1/128$ satisfy Eq. 9 since otherwise
$\varepsilon$ is a constant and we can use the list decodable codes from
[AJQ+20]. The use of Eq. 9 will be clear shortly. It becomes a necessity from
round III onward. For rounds I and II, the parameter $\alpha$ will be a
constant, but it will be useful to establish the analysis in more generality
now so that subsequent rounds can reuse it.

The inner graph $H$. The choice of $H$ is similar to Ta-Shma’s choice. More
precisely, we set $s=1/\alpha$ and $d_{2}=s^{4s^{2}}$ (Ta-Shma took
$d_{2}=s^{4s}$). We obtain a Cayley graph
$H=\textup{Cay}(\mathbb{F}_{2}^{4s\log_{2}(d_{2})},A)$ such that $H$ is an
$(n_{2}=d_{2}^{4s},d_{2},\lambda_{2})$ graph where
$\lambda_{2}=b_{2}/\sqrt{d_{2}}$ and $b_{2}=4s\log_{2}(d_{2})$. (The set of
generators, $A$, comes from a small bias code derived from a construction of
Alon et al. [AGHP92], but we will rely on Ta-Shma’s analysis embodied in Lemma
B.2 and not discuss it further.)

The base code $\mathcal{C}_{0}$. Set
$\varepsilon_{0}=1/d_{2}^{2}=\lambda_{2}^{4}/b_{2}^{4}\leq\lambda_{2}^{4}/3$
(this choice differs from Ta-Shma’s and it appears because we are essentially
working with $H^{2}$ rather than $H$). We will choose a base code
$\mathcal{C}_{0}$ such that the desired code will be obtained as a direct sum
lifting of $\mathcal{C}_{0}$, and because this lifting preserves the
dimension, the dimension of $\mathcal{C}_{0}$ should be $D$. We choose
$\mathcal{C}_{0}$ to be an $\varepsilon_{0}$-balanced code with dimension $D$
and block length $n=O_{\varepsilon_{0}}(D)$. For instance, we can start with
any good (constant rate and relative distance) linear base code
$\mathcal{C}_{0}$ that has an efficient unique decoding algorithm and obtain a
$\varepsilon_{0}$-balanced lifted code that can be efficiently unique decoded
(as long as $\varepsilon_{0}$ is constant) using the framework in [AJQ+20].

The outer graph $G$. Set $d_{1}=d_{2}^{4}$ so that $n_{2}=d_{1}^{s}$ as
required by the $s$-wide replacement product. We apply Ta-Shma’s explicit
Ramanujan graph Lemma B.1 with parameters $n$, $d_{1}$ and $\theta$ to obtain
an $(n^{\prime},d_{1},\lambda_{1})$ Ramanujan graph $G$ with $\lambda_{1}\leq
2\sqrt{2}/\sqrt{d_{1}}$ and $n^{\prime}\in[(1-\theta)n,n]$ or
$n^{\prime}\in[(1-\theta)2n,2n]$. Here, $\theta$ is an error parameter that we
set as $\theta=\lambda_{2}^{4}/6$ (this choice of $\theta$ differs from Ta-
Shma). Because we can construct words with block length $2n$ (if needed) by
duplicating each codeword, we may assume w.l.o.g. that $n^{\prime}$ is close
to $n$ and $(n-n^{\prime})\leq\theta n\leq 2\theta n^{\prime}$. See Appendix B
for a more formal description of this graph.

Note that $\lambda_{1}\leq\lambda_{2}^{4}/6$ since $\lambda_{1}\leq
3/\sqrt{d_{1}}=3/d_{2}^{2}=3\cdot\lambda_{2}^{4}/b_{2}^{4}\leq\lambda_{2}^{4}/6$.
Hence, $\varepsilon_{0}+2\theta+2\lambda_{1}\leq\lambda_{2}^{4}$.

The walk length. Set the walk length $t-1$ to be the smallest integer such
that

$(\lambda_{2}^{2})^{(1-5\alpha)(1-\alpha)(t-1)}\leq\varepsilon.$

This will imply using Ta-Shma’s analysis that the bias of the final code is at
most $\varepsilon$ as shown later.

$s=1/\alpha,\text{ such that
}\frac{\alpha^{5}}{4\log_{2}(1/\alpha)}\geq\frac{1}{\log_{2}(1/\varepsilon)}$
$H:(n_{2},d_{2},\lambda_{2}),\quad n_{2}=d_{1}^{s},\quad
d_{2}=s^{4s^{2}},\quad\lambda_{2}=\frac{b_{2}}{\sqrt{d_{2}}},\quad
b_{2}=4s\log d_{2}$ $G:(n^{\prime},d_{1},\lambda_{1}),\quad n^{\prime}\approx
n=O(D/\varepsilon_{0}^{c}),\quad
d_{1}=d_{2}^{4},\quad\lambda_{1}\leq\frac{2\sqrt{2}}{d_{1}}$ $t:\text{
smallest integer such that
}(\lambda_{2}^{2})^{(1-5\alpha)(1-\alpha)(t-1)}\leq\varepsilon$

######  Claim 8.2.

We have $t-1\geq s/\alpha=s^{2}$.

###### Proof.

Using $d_{2}=s^{4s^{2}}$ and Eq. 9, we have

$\displaystyle\left(\frac{1}{\lambda_{2}^{2}}\right)^{(1-5\alpha)(1-\alpha)s/\alpha}$
$\displaystyle\leq\left(\frac{1}{\lambda_{2}^{2}}\right)^{s/\alpha}=\left(\frac{d_{2}}{b_{2}^{2}}\right)^{s/\alpha}\leq\left(d_{2}\right)^{s/\alpha}=s^{4s^{3}/\alpha}$
$\displaystyle=2^{4s^{3}\log_{2}(s)/\alpha}=2^{4\log_{2}(1/\alpha)/\alpha^{4}}\leq
2^{\log_{2}(1/\varepsilon)}=\frac{1}{\varepsilon}.$

Hence, $\varepsilon\leq(\lambda_{2}^{2})^{(1-5\alpha)(1-\alpha)s/\alpha}$ and
thus $t-1$ must be at least $s/\alpha$.

######  Remark 8.3.

By our choice of $t$, we have
$(\lambda_{2}^{2})^{(1-5\alpha)(1-\alpha)(t-2)}\geq\varepsilon$. Since
$1/(t-1)\leq\alpha$, we get
$(\lambda_{2}^{2})^{(1-5\alpha)(1-\alpha)^{2}(t-1)}\geq\varepsilon$.

Final Bias. We denote by $\mathcal{C}_{\ell}$ the final code obtained by $t$
steps of the $s$-wide replacement product. The bias of $\mathcal{C}_{\ell}$ is
given by Corollary 4.10 (which in turn is a simple corollary of Ta-Shma’s 4.9)
as shown next.

######  Corollary 8.4.

The code $\mathcal{C}_{\ell}$ is $\varepsilon$-balanced.

###### Proof.

Using Corollary 4.10, we have that the final bias

$\displaystyle
b\coloneqq\left(\sigma_{2}(H^{2})^{s-1}+(s-1)\cdot\sigma_{2}(H^{2})^{s-2}+(s-1)^{2}\cdot\sigma_{2}(H^{2})^{s-4}\right)^{\lfloor(t-1)/s\rfloor}$

is bounded by

$\displaystyle b$
$\displaystyle\leq(3(s-1)^{2}\sigma_{2}(H^{2})^{s-4})^{((t-1)/s)-1}$
$\displaystyle(\text{Using }\sigma_{2}(H^{2})\leq 1/3s^{2})$
$\displaystyle\leq((\sigma_{2}(H^{2})^{s-5})^{(t-1-s)/s}$
$\displaystyle=\sigma_{2}(H^{2})^{(1-5/s)(1-s/(t-1))(t-1)}$
$\displaystyle\leq\sigma_{2}(H^{2})^{(1-5\alpha)(1-\alpha)(t-1)}$
$\displaystyle=\left(\lambda_{2}^{2}\right)^{(1-5\alpha)(1-\alpha)(t-1)}\leq\varepsilon,$

where the last inequality follows from $s=1/\alpha$ and $t-1\geq s/\alpha$,
the latter from 8.2.

Rate. The proof of the rate follows a similar structure of Ta-Shma’s original
argument except that we take $s$ to be a constant independent of $\varepsilon$
so that $\varepsilon_{0}$, $\lambda_{1}$, and $\lambda_{2}$ are also constants
independent of $\varepsilon$. Note that we previously said $\alpha=1/s$ needs
to satisfy Equation 9, but that implies only an upper bound for $s$, and
smaller (even constant) values for $s$ are still permissible.

######  Claim 8.5.

$\mathcal{C}_{\ell}$ has rate $\Omega(\varepsilon^{2+26\cdot\alpha})$ provided
$\varepsilon_{0}>0$ is constant.

###### Proof.

The support size is the number of walks of length $t$ on the $s$-wide
replacement product of $G$ and $H$ (each step of the walk has $d_{2}^{2}$
options), which is

$\displaystyle|V(G)||V(H)|d_{2}^{2(t-1)}=n^{\prime}\cdot d_{1}^{s}\cdot
d_{2}^{2(t-1)}$ $\displaystyle=n^{\prime}\cdot d_{2}^{2(t-1)+4s}\leq n\cdot
d_{2}^{2(t-1)+4s}$ $\displaystyle=\Theta_{\varepsilon_{0}}\left(D\cdot
d_{2}^{2(t-1)+4s}\right)$
$\displaystyle=\Theta\left(D\cdot(d_{2}^{2})^{t-1+2s}\right)$
$\displaystyle=O\left(D\cdot(d_{2}^{2})^{(1+2\alpha)(t-1)}\right),$

where the penultimate equality follows from the assumption that
$\varepsilon_{0}$ is a constant.

Note that $d_{2}^{\alpha}=d_{2}^{1/s}=s^{4s}\geq b_{2}$ since
$b_{2}=4s\log_{2}(d_{2})=16s^{3}\log_{2}(s)\leq s^{4}$ (recall that
$s=1/\alpha\geq 128$). Thus,

$d_{2}^{1-2\alpha}=\frac{d_{2}}{d_{2}^{2\alpha}}\leq\frac{d_{2}}{b_{2}^{2}}=\frac{1}{\sigma_{2}(H^{2})}.$

We obtain

$\displaystyle(d_{2}^{2})^{(t-1)}$
$\displaystyle\leq\left(\frac{1}{\sigma_{2}(H^{2})}\right)^{\frac{2(t-1)}{1-2\alpha}}$
$\displaystyle\leq\left(\frac{1}{\varepsilon}\right)^{\frac{2}{(1-2\alpha)(1-5\alpha)(1-\alpha)^{2}}}$
(Using Remark 8.3)
$\displaystyle\leq\left(\frac{1}{\varepsilon}\right)^{2(1+10\alpha)},$

which implies a block length of

$O\left(D\cdot(d_{2}^{2})^{(1+2\alpha)(t-1)}\right)=O\left(D\left(\frac{1}{\varepsilon}\right)^{2(1+10\alpha)(1+2\alpha)}\right)=O\left(D\left(\frac{1}{\varepsilon}\right)^{2(1+13\alpha)}\right).$

######  Lemma 8.6 (Codes Near the GV bound I).

For every constant $\beta>0$, there exists a sufficiently large constant $s$
in the above analysis so that for any dimension value $D\in\mathbb{N}^{+}$
(sufficiently large) and $\varepsilon>0$ (sufficiently small) the final code
$\mathcal{C}_{N,\varepsilon,\beta}$, where $N$ is the block length, satisfies

  * -

$\mathcal{C}_{N,\varepsilon,\beta}$ is $\varepsilon$-balanced,

  * -

$\mathcal{C}_{N,\varepsilon,\beta}$ has rate $\Omega(\varepsilon^{2+\beta})$,
and

  * -

$\mathcal{C}_{N,\varepsilon,\beta}$ is a linear code of dimension $D$.

######  Remark 8.7.

As a consequence of code cascading, the final attainable walk lengths have the
form $s^{\ell}-1$ where $\ell$ is a positive integer. Given $\beta>0$, we have
infinitely many values of $\varepsilon$ attainable by such walk lengths which
gives infinitely many codes $\mathcal{C}_{N,\varepsilon,\beta}$. This means
that although the bias $\varepsilon$ cannot be arbitrary, we have an infinite
sequence of values of $\varepsilon$ for which the rates of the codes
$\mathcal{C}_{N,\varepsilon,\beta}$ are near the GV bound. In Section 8.2, we
show how to bypass this artificial limitation. These codes are used in the
proof of Theorem 6.6.

We can view the above analysis as defining a function $\Gamma$ that receives

  * -

the dimension $D\in\mathbb{N}^{+}$,

  * -

the final bias $\varepsilon>0$,

  * -

the approximating error $\alpha\in(0,1/128]$ with $s\coloneqq 1/\alpha$ being
a power of two, and

  * -

a multiplying factor $Q\in\mathbb{N}^{+}$ such that $d_{2}=s^{4s^{2}\cdot Q}$
(in the above $Q$ was $1$).

and outputs a tuple of parameters
$(t,\varepsilon_{0},\theta,d_{1},\lambda_{1},n^{\prime})$, graphs $G$ and $H$
(as above) where, in particular, the number of steps $t\in\mathbb{N}^{+}$ is
such that the final code $\mathcal{C}_{\ell}$ has bias at most $\varepsilon$
and rate $\Omega(\varepsilon^{2+26\cdot\alpha})$.

In future rounds, $\Gamma$ may be called with $Q=s$ instead of $Q=1$. This
will cause $d_{2}$ to increase from $s^{4s^{2}}$ to $s^{4s^{2}\cdot Q}$, and
so in the proof of 8.2, $2^{4\log_{2}(1/\alpha)/\alpha^{4}}$ will be replaced
by $2^{4\log_{2}(1/\alpha)/\alpha^{5}}$. This explains why Eq. 9 has a
stricter requirement than needed in the $Q=1$ case above.

###  8.2 Round II: A More Careful Analysis

We are given the dimension of the code $D$ and $\varepsilon\in(0,1/2)$. As
before, we set a parameter $\alpha\leq 1/128$ such that (for convenience)
$1/\alpha$ is a power of $2$. Set $s=1/\alpha$ and $Q=s$.

Apply $\Gamma$ to $(D,\varepsilon,\alpha,Q)$ to obtain all parameters except
$t$. Choose $t$ to be the smallest integer satisfying

$(\lambda_{2}^{2})^{(1-5\alpha)(1-2\alpha)(1-\alpha)(t-1)}\leq\varepsilon,$

where observe that an extra $(1-2\alpha)$ factor appears in the exponent. This
change in $t$ will worsen the rate but by losing a factor of
$\frac{1}{1-2\alpha}$ in the exponent, we can lower bound the rate. That is,
$(d_{2}^{2})^{-(t-1)}=\Omega(\varepsilon^{\frac{2+26\cdot\alpha}{1-2\alpha}})$.

Set $\ell\in\mathbb{N}^{+}$ to be the smallest value such that $s^{\ell}\geq
t$ (here we are implicitly assuming that $t>s$). If $s^{\ell}=t$, we are done
since we can use all the parameters returned by $\Gamma$ for the construction
of $\mathcal{C}_{\ell}$. Now assume $s^{\ell}>t$ and let $\zeta=t/s^{\ell-1}$.
Note that $\zeta\in(1,s)$. Choose $P$ to be the integer in the interval
$[Q,s\cdot Q]$ such that

$0\leq\frac{P}{Q}-\zeta\leq\frac{1}{Q}.$

Because $s^{\ell}>t$, and only powers of $s$ may be chosen for walk length, we
might overshoot in walk length by a multiplicative factor of $s$. This will
cause a corresponding decay in rate computation that we cannot afford. To
overcome this, in the last level of the cascade between codes
$\mathcal{C}_{\ell-1}$ and $\mathcal{C}_{\ell}$, perform the direct sum over
walks of length $(P-1)$ instead of length $(s-1)$. The new total number of
vertices is $t^{\prime}=Ps^{\ell-1}$. Note that $P$ can be as large as
$s^{2}$, so our splittability guarantee of $W(P)$ (the walk collection from
the lift between $\mathcal{C}_{\ell-1}$ and $\mathcal{C}_{\ell}$) has to be
strong enough to accommodate this larger arity and not only arity $s$.

######  Claim 8.8.

We have $t-1\leq\frac{t^{\prime}-1}{Q}\leq(1+2\alpha)(t-1)$.

###### Proof.

By construction, we have the sequence of implications

$\displaystyle 0\leq\frac{P}{Q}s^{\ell-1}-\zeta
s^{\ell-1}\leq\frac{s^{\ell-1}}{Q}$ $\displaystyle\Rightarrow$ $\displaystyle
0\leq\frac{t^{\prime}}{Q}-t\leq\frac{s^{\ell-1}}{Q}\leq\frac{t}{Q}$
$\displaystyle\Rightarrow$ $\displaystyle
t-\frac{1}{Q}\leq\frac{t^{\prime}-1}{Q}\leq(t-1)\left(1+\frac{1}{Q}\right)+1,$

from which we obtain

$t-1\leq t-\frac{1}{Q}\leq\frac{t^{\prime}-1}{Q}$

and

$\frac{t^{\prime}-1}{Q}\leq(t-1)\left(1+\frac{1}{Q}\right)+1=(1+\alpha)(t-1)+1<(1+2\alpha)(t-1),$

the latter using $Q=s=1/\alpha$.

We apply $\Gamma$ again but this time to $(D,\varepsilon,\alpha,1)$ to obtain
new parameters $(t^{\prime\prime},\varepsilon_{0}^{\prime}$,
$\theta^{\prime}$, $d_{1}^{\prime}$, $\lambda_{1}^{\prime}$,
$n^{\prime\prime})$, and graphs $G^{\prime}$ and $H^{\prime}$.

######  Claim 8.9.

The code $\mathcal{C}_{\ell}^{\prime}$ obtained by $t^{\prime}$ walk steps on
the $s$-wide replacement product of $G^{\prime}$ and $H^{\prime}$ from the
second application of $\Gamma$ has bias at most $\varepsilon$ and rate
$\Omega(\varepsilon^{2+40\alpha})$.

###### Proof.

Let $d_{2}=s^{4s^{2}\cdot Q}$, $b_{2}=4s\log_{2}(d_{2})$ and
$\lambda_{2}=b_{2}/\sqrt{d_{2}}$ be the parameters of the first invocation of
$\Gamma$. Recall that $t$ was chosen to be the smallest integer satisfying

$(\lambda_{2}^{2})^{(1-5\alpha)^{2}(1-\alpha)(t-1)}\leq\varepsilon.$

Let $d_{2}^{\prime}=s^{4s^{2}}$, $b_{2}^{\prime}=4s\log_{2}(d_{2}^{\prime})$
and $\lambda_{2}^{\prime}=b_{2}^{\prime}/\sqrt{d_{2}^{\prime}}$ be the
parameters of the second invocation of $\Gamma$. Observe that

$\displaystyle(\lambda_{2}^{\prime})^{Q}$
$\displaystyle=\frac{(b_{2}^{\prime})^{Q}}{\sqrt{(d_{2}^{\prime})^{Q}}}=\frac{(b_{2}^{\prime
Q})}{\sqrt{d_{2}}}=\frac{(16s^{3}\log_{2}(s))^{Q}}{s^{2s^{2}\cdot Q}}$
$\displaystyle\leq\frac{s^{4Q}}{s^{2s^{2}\cdot Q}}=\frac{1}{s^{2s^{2}\cdot
Q(1-\frac{2}{s^{2}})}}=\left(\frac{1}{s^{2s^{2}\cdot
Q}}\right)^{1-2\alpha}\leq\left(\frac{b_{2}}{\sqrt{d_{2}}}\right)^{1-2\alpha}=\lambda_{2}^{1-2\alpha}.$

Then the bias of $\mathcal{C}^{\prime}_{\ell}$ is at most

$\displaystyle(((\lambda_{2}^{\prime})^{Q})^{2})^{(1-5\alpha)(1-\alpha)(t^{\prime}-1)/Q}$
$\displaystyle\leq(\lambda_{2}^{2})^{(1-5\alpha)(1-2\alpha)(1-\alpha)(t^{\prime}-1)/Q}$
$\displaystyle\leq(\lambda_{2}^{2})^{(1-5\alpha)(1-2\alpha)(1-\alpha)(t-1)}\leq\varepsilon.$

For the rate computation of $\mathcal{C}^{\prime}_{\ell}$, we will lower bound
the term $((d^{\prime}_{2})^{2})^{-(t^{\prime}-1)}$. Since
$d_{2}=(d_{2}^{\prime})^{Q}$,
$(d_{2}^{2})^{-(t-1)}=\Omega(\varepsilon^{\frac{2+26\cdot\alpha}{1-2\alpha}})$
and $\frac{t^{\prime}-1}{Q}\leq(1+2\alpha)(t-1)$ (the latter by 8.8), the rate
of $\mathcal{C}_{\ell}^{\prime}$ is

$\Omega(((d^{\prime}_{2})^{2})^{-(t^{\prime}-1)})=\Omega((d_{2}^{2})^{-(t^{\prime}-1)/Q})=\Omega((d_{2}^{2})^{-(1+2\alpha)(t-1)})=\Omega((\varepsilon^{2+26\cdot\alpha})^{\frac{1+2\alpha}{1-2\alpha}})=\Omega(\varepsilon^{2+40\cdot\alpha}).$

###  8.3 Round III: Vanishing $\beta$ as $\varepsilon$ Vanishes

We are given the dimension of the code $D$ and $\varepsilon\in(0,1/2)$. As
before, we set a parameter $\alpha\leq 1/128$ such that (for convenience)
$1/\alpha$ is a power of $2$. Set $s\coloneqq 1/\alpha$.

We will consider the regime where $s$ is a function of $\varepsilon$. As a
consequence, the parameters
$d_{2},\lambda_{2},d_{1},\lambda_{1},\varepsilon_{0}$ will also depend on
$\varepsilon$. Since $x\leq 1/\log_{2}(1/x)$ for $x\leq 1/2$ (and $\alpha\leq
1/2$), if $\alpha$ satisfies $\alpha^{6}/4\geq 1/\log_{2}(1/\beta)$, it also
satisfies Eq. 9 (we lose a log factor by replacing $1/\log_{2}(1/\alpha)$ by
$\alpha$, but we will favor simplicity of parameters). In particular, we can
set $\alpha$ so that $s$ is

$s=\Theta((\log_{2}(1/\varepsilon))^{1/6}),$

and satisfy Eq. 9.

We follow the same choices as in Round II except for the base code
$\mathcal{C}_{0}$.

The base code $\mathcal{C}_{0}$. Set
$\varepsilon_{0}=1/d_{2}^{2}=\lambda_{2}^{4}/b_{2}^{4}\leq\lambda_{2}^{4}/3$.
We choose an $\varepsilon_{0}$-balanced code $\mathcal{C}_{0}$ with support
size $n=O(D/\varepsilon_{0}^{c})$ where $c=2.001$ (this choice of $c$ is
arbitrary, it is enough to have $c$ as a fixed small constant) using the
construction from Round II. It is crucial that we can unique decode
$\mathcal{C}_{0}$ (using our algorithm), since this is required in order to
apply the list decoding framework.

Note that $\varepsilon_{0}$ is no longer a constant. For this reason, we need
to consider the rate computation of the final code $\mathcal{C}_{\ell}$ more
carefully. The proof will follow an argument similar to Ta-Shma’s.

######  Claim 8.10.

$\mathcal{C}_{\ell}$ has rate $\Omega(\varepsilon^{2+26\cdot\alpha})$ where
$\alpha=\Theta(1/(\log_{2}(1/\varepsilon))^{1/6})$.

###### Proof.

The support size is the number of walks of length $t-1$ on the $s$-wide
replacement product of $G$ and $H$ (each step of the walk has $d_{2}^{2}$
options), which is

$\displaystyle|V(G)||V(H)|d_{2}^{2(t-1)}=n^{\prime}\cdot d_{1}^{s}\cdot
d_{2}^{2(t-1)}$ $\displaystyle=n^{\prime}\cdot d_{2}^{2(t-1)+4s}\leq n\cdot
d_{2}^{2(t-1)+4s}$
$\displaystyle=\Theta\left(\frac{D}{\varepsilon_{0}^{c}}\cdot
d_{2}^{2(t-1)+4s}\right)$
$\displaystyle=\Theta\left(D\cdot(d_{2}^{2})^{(t-1)+2s+2.001}\right)$
$\displaystyle=O\left(D\cdot(d_{2}^{2})^{(1+2\alpha)(t-1)}\right).$

From this point the proof continues exactly as the proof of 8.5.

###  8.4 Round IV: Arbitrary Gentle List Decoding

In round III, when we take

$s=\Theta((\log_{2}(1/\varepsilon))^{1/6}),$

we will have $\lambda_{2}=4s\log(s^{4s^{2}})/s^{2s^{2}}\leq s^{-s^{2}}$
provided $s$ is large enough. This non-constant $\lambda_{2}$ will allow us
perform “gentle” list decoding with radius arbitrarily close to $1/2$. More
precisely, we have the following.

######  Theorem 8.11 (Gentle List Decoding (restatement of Theorem 1.2)).

For every $\varepsilon>0$ sufficiently small, there are explicit binary linear
Ta-Shma codes $\mathcal{C}_{N,\varepsilon,\beta}\subseteq\mathbb{F}_{2}^{N}$
for infinitely many values $N\in\mathbb{N}$ with

  1. (i)

distance at least $1/2-\varepsilon/2$ (actually $\varepsilon$-balanced),

  2. (ii)

rate $\Omega(\varepsilon^{2+\beta})$ where
$\beta=O(1/(\log_{2}(1/\varepsilon))^{1/6})$, and

  3. (iii)

a list decoding algorithm that decodes within radius
$1/2-2^{-\Theta((\log_{2}(1/\varepsilon))^{1/6})}$ in time
$N^{O_{\varepsilon,\beta}(1)}$.

###### Proof.

We consider some parameter requirements in order to apply the list decoding
framework Theorem 9.1 between $\mathcal{C}_{\ell-1}$ and $\mathcal{C}_{\ell}$.
Suppose we want to list decode within radius $1/2-\sqrt{\eta}$. For parity
sampling, we need

$s\geq\Theta(\log_{2}(1/\eta)).$

Since the number of vertices in a walk can be at most $s^{2}$, for
splittability we need

$\eta^{8}/(s^{2}\cdot 2^{2s^{2}})\geq 2\cdot s^{-s^{2}}.$

In particular, we can take $\eta=2^{-\Theta(s)}$ and satisfy both conditions
above.

##  9 Instantiating the List Decoding Framework

We established the tensoriality (actually two-step tensoriality) and parity
sampling properties of every lifting between consecutive codes
$\mathcal{C}_{i-1}$ and $\mathcal{C}_{i}$ in Ta-Shma’s cascade. Using these
properties, we will be able to invoke the list decoding framework from
[AJQ+20] to obtain the following list decoding result.

######  Theorem 9.1 (Restatement of Theorem 6.1).

Let $\eta_{0}\in(0,1/4)$ be a constant, $\eta\in(0,\eta_{0})$, and

$k\geq k_{0}(\eta)\coloneqq\Theta(\log(1/\eta)).$

Suppose $\mathcal{C}\subseteq{\mathbb{F}}_{2}^{n}$ is an $\eta_{0}$-balanced
linear code and $\mathcal{C}^{\prime}=\operatorname{dsum}_{W(k)}(\mathcal{C})$
is the direct sum lifting of $\mathcal{C}$ on a $\tau$-splittable collection
of walks $W(k)$, where $W(k)$ is either the set of walks $W[0,s]$ on an
$s$-wide replacement product graph or a set of walks using the random walk
operator $\mathsf{S}_{r,r}^{\bigtriangleup}$. There exists an absolute
constant $K>0$ such that if

$\tau\leq\tau_{0}(\eta,k)\coloneqq\frac{\eta^{8}}{K\cdot k\cdot 2^{4k}},$

then the code $\mathcal{C}^{\prime}$ is $\eta$-balanced and can be efficiently
list decoded in the following sense:

If $\tilde{y}$ is $(1/2-\sqrt{\eta})$-close to $\mathcal{C}^{\prime}$, then we
can compute the list

$\mathcal{L}(\tilde{y},\mathcal{C},\mathcal{C}^{\prime})\coloneqq\left\\{(z,\operatorname{dsum}_{W(k)}(z))\mid
z\in\mathcal{C},\Delta\left\lparen\operatorname{dsum}_{W(k)}(z),\tilde{y}\right\rparen\leq\frac{1}{2}-\sqrt{\eta}\right\\}$

in time

$n^{O(1/\tau_{0}(\eta,k)^{4})}\cdot f(n),$

where $f(n)$ is the running time of a unique decoding algorithm for
$\mathcal{C}$. Otherwise, we return
$\mathcal{L}(\tilde{y},\mathcal{C},\mathcal{C}^{\prime})=\emptyset$ with the
same running time of the preceding case 999In the case $\tilde{y}$ is not
$(1/2-\sqrt{\eta})$-close to $\mathcal{C}^{\prime}$, but the SOS program turns
out to be feasible, some of the calls to the unique decoding algorithm of
$\mathcal{C}$ (issued by the list decoding framework) might be outside all
unique decoding balls. Such cases may be handled by returning failure if the
algorithm does not terminate by the time $f(n)$. Even if a codeword in
$\mathcal{C}$ is found, the pruning step of list decoding [AJQ+20] will return
an empty list for $\mathcal{L}(\tilde{y},\mathcal{C},\mathcal{C}^{\prime})$
since $\tilde{y}$ is not $(1/2-\sqrt{\eta})$-close to $\mathcal{C}$..

###  9.1 List Decoding Framework

We recall the precise statement of the list decoding framework tailored to
direct sum lifting.

######  Theorem 9.2 (List Decoding Theorem (Adapted from [AJQ+20])).

Suppose $\operatorname{dsum}_{W(k)}$ is an $(\eta^{8}/2^{30},L)$-two-step
tensorial direct sum lifting from an $\eta_{0}$-balanced code
$\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ to $\mathcal{C}^{\prime}$ on a
multiset $W(k)\subseteq[n]^{k}$ which is a $(1/2+\eta_{0}/2,\eta)$-parity
sampler.

Let $\tilde{y}\in{\mathbb{F}}_{2}^{W(k)}$ be $(1/2-\sqrt{\eta})$-close to
$\mathcal{C}^{\prime}$. Then the List Decoding algorithm returns the coupled
code list $\mathcal{L}(\widetilde{y},\mathcal{C},\mathcal{C}^{\prime})$.
Furthermore, the running time is
$n^{O(L+k)}\left({\mathrm{polylog}}(1/\eta)+f(n)\right)$ where $f(n)$ is the
running time of an unique decoding algorithm of $\mathcal{C}$.

We apply the list decoding framework of Theorem 9.2 to the liftings arising in
the Ta-Shma cascade to obtain Theorem 9.1. This requires choosing parameters
so that both the parity sampling and tensoriality requirements are met at
every level of the cascade, which we do by appealing to our results from
Section 7.

###### Proof of Theorem 9.1.

We want to define parameters for $\tau$-splittability so that $W(k)$ satisfies
strong enough parity sampling and tensoriality assumptions to apply Theorem
9.2.

For parity sampling, we require $W(k)$ to be an $(1/2+\eta_{0}/2,\eta)$-parity
sampler. Suppose $W(k)$ is $\tau$-splittable with $\tau<1/16$. By Corollary
7.4 or Corollary 7.7 and splittability, the collection of walks $W(k)$ is an
$(\eta_{0}^{\prime},\eta^{\prime})$-parity sampler, where
$\eta^{\prime}\leq(\eta_{0}^{\prime}+2\tau)^{\lfloor(k-1)/2\rfloor}$. To
achieve the desired parity sampling, we take
$\eta_{0}^{\prime}=1/2+\eta_{0}/2$ and choose a value of $k$ large enough so
that $\eta^{\prime}\leq\eta$. Using the assumption $\eta_{0}<1/4$, we compute

$\eta^{\prime}=(\eta_{0}^{\prime}+2\tau)^{\lfloor(k-1)/2\rfloor}\leq(1/2+\eta_{0}/2+2\tau)^{k/2-1}<(3/4)^{k/2-1},$

which will be smaller than $\eta$ as long as $k$ is at least

$k_{0}(\eta)=2\left(1+\frac{\log(1/\eta)}{\log(4/3)}\right)=\Theta(\log(1/\eta)).$

Achieving this level of parity sampling also ensures that the lifted code
$\mathcal{C}^{\prime}$ is $\eta$-balanced.

The list decoding theorem also requires $(\eta^{8}/2^{30},L)$-two-step
tensoriality. Lemma 7.24 (with $s=k$) and Lemma 7.25 each provide
$(\mu,L)$-two-step tensoriality for $\tau$-splittable walk collections on the
$s$-wide replacement product and using $\mathsf{S}_{r,r}^{\bigtriangleup}$,
respectively, with

$L\geq\frac{128k^{4}\cdot 2^{4k}}{\mu^{4}}\text{\quad and
\quad}\tau\leq\frac{\mu}{4k\cdot 2^{4k}}.$

To get $\mu=\eta^{8}/2^{30}$, we require

$L\geq\frac{K^{\prime}\cdot k^{4}\cdot 2^{4k}}{\eta^{32}}\text{\quad and
\quad}\tau\leq\tau_{0}(\eta,k)=\frac{\eta^{8}}{K\cdot k\cdot 2^{4k}},$

where $K$ and $K^{\prime}$ are (very large) constants. This ensures that
$\tau$ is small enough for the parity sampling requirement as well. With these
parameters, the running time for the list decoding algorithm in Theorem 9.2
becomes

$n^{O(L+k)}({\mathrm{polylog}}(1/\eta)+f(n))=n^{O(L)}\cdot
f(n)=n^{O(1/\tau_{0}(\eta,k)^{4})}\cdot f(n).$

For decoding in fixed polynomial time, we also need a variation of list
decoding where we don’t run the unique decoding algorithm of the base code and
only obtain an approximate list of solutions. The proof is very similar to the
proof of Theorem 9.1 above.

######  Theorem 9.3 (Restatement of Theorem 6.12).

Let $\eta_{0}\in(0,1/4)$ be a constant, $\eta\in(0,\eta_{0})$,
$\zeta=1/8-\eta_{0}/8$, and

$k\geq k_{0}^{\prime}(\eta)\coloneqq\Theta(\log(1/\eta)).$

Suppose $\mathcal{C}\subseteq{\mathbb{F}}_{2}^{n}$ is an $\eta_{0}$-balanced
linear code and $\mathcal{C}^{\prime}=\operatorname{dsum}_{W(k)}(\mathcal{C})$
is the direct sum lifting of $\mathcal{C}$ on a $\tau$-splittable collection
of walks $W(k)$, where $W(k)$ is either the set of walks $W[0,s]$ on an
$s$-wide replacement product graph or a set of walks using the random walk
operator $\mathsf{S}_{r,r}^{\bigtriangleup}$. There exists an absolute
constant $K>0$ such that if

$\tau\leq\tau_{0}(\eta,k)\coloneqq\frac{\eta^{8}}{K\cdot k\cdot 2^{4k}},$

then the code $\mathcal{C}^{\prime}$ is $\eta$-balanced, $W(k)$ is a
$(1-2\zeta,\eta)$-parity sampler, and we have the following:

If $\tilde{y}$ is $(1/2-\sqrt{\eta})$-close to $\mathcal{C}^{\prime}$, then we
can compute a $\zeta$-cover $\mathcal{L}^{\prime}$ of the list

$\mathcal{L}(\tilde{y},\mathcal{C},\mathcal{C}^{\prime})\coloneqq\left\\{(z,\operatorname{dsum}_{W(k)}(z))\mid
z\in\mathcal{C},\Delta\left\lparen\operatorname{dsum}_{W(k)}(z),\tilde{y}\right\rparen\leq\frac{1}{2}-\sqrt{\eta}\right\\}$

in which $\Delta(y^{\prime},\tilde{y})\leq 1/2-\sqrt{\eta}$ for every
$(z^{\prime},y^{\prime})\in\mathcal{L}^{\prime}$ 101010A randomized rounding
will ensure this, but see Appendix D for obtaining this property
deterministically., in time

$n^{O(1/\tau_{0}(\eta,k)^{4})}.$

Otherwise, we return $\mathcal{L}^{\prime}=\emptyset$ with the same running
time of the preceding case.

###### Proof.

The list decoding framework produces a cover $\mathcal{L}^{\prime}$ of the
list $\mathcal{L}(\tilde{y},\mathcal{C},\mathcal{C}^{\prime})$, and, as its
final step, corrects the cover to obtain the actual list
$\mathcal{L}(\tilde{y},\mathcal{C},\mathcal{C}^{\prime})$ by running the
unique decoding algorithm of $\mathcal{C}$ on each entry of
$\mathcal{L}^{\prime}$ (see [AJQ+20] for details). Using Theorem 9.2 with a
$(1-2\zeta,\eta)$-parity sampler and omitting this final step of the
algorithm, we can obtain the $\zeta$-cover $\mathcal{L}^{\prime}$ in time
$n^{O(L+k)}{\mathrm{polylog}}(1/\eta)$.

The tensoriality part of the proof of Theorem 9.1 applies here unchanged, so
we need only make sure $k$ is large enough to yield the stronger parity
sampling necessary for this theorem. As in that proof, we have that $W(k)$ is
an $(\eta_{0}^{\prime},\eta^{\prime})$-parity sampler with
$\eta^{\prime}\leq(\eta_{0}^{\prime}+2\tau)^{\lfloor(k-1)/2\rfloor}$. Take
$\eta_{0}^{\prime}=1-2\zeta=3/4+\eta_{0}/4$. Using $\eta_{0}<1/4$ and assuming
$\tau<1/16$, we have

$\eta^{\prime}\leq(\eta_{0}^{\prime}+2\tau)^{\lfloor(k-1)/2\rfloor}\leq(3/4+\eta_{0}/4+2\tau)^{k/2-1}<(15/16)^{k/2-1},$

which will be smaller than $\eta$ as long as $k$ is at least

$k_{0}^{\prime}(\eta)=2\left(1+\frac{\log(1/\eta)}{\log(16/15)}\right)=\Theta(\log(1/\eta)).$

## Acknowledgement

We thank Amnon Ta-Shma for suggesting the problem of decoding in fixed
polynomial running time (with the exponent of $N$ independent of
$\varepsilon$) which led us to think about Theorem 6.9. Part of this work was
done when some of the authors were visiting the Simons Institute in Berkeley,
and we thank them for their kind hospitality.

## References

  * [ABN+92] N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth.  Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs.  IEEE Transactions on Information Theory, 28:509–516, 1992.
  * [AGHP92] N. Alon, O. Goldreich, J. Håstad, and R. Peralta.  Simple constructions of almost $k$-wise independent random variables.  Random Structures and Algorithms, 3(3):289–304, 1992.
  * [AJQ+20] Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani.  List decoding of direct sum codes.  In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, pages 1412–1425. SIAM, 2020.
  * [AJT19] Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani.  Approximating constraint satisfaction problems on high-dimensional expanders.  In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science, pages 180–201, 2019.
  * [Ari09] E. Arikan.  Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels.  IEEE Transactions on Information Theory, 55(7):3051–3073, July 2009\.
  * [Aro02] Sanjeev Arora.  How NP got a new definition: a survey of probabilistically checkable proofs.  In Proceedings of the International Congress of Mathematicians, pages 637–648, 2002.  Volume 3.
  * [Bog12] Andrej Bogdanov.  A different way to improve the bias via expanders.  Lecture notes, April 2012.  URL: http://www.cse.cuhk.edu.hk/~andrejb/csc5060/notes/12L12.pdf.
  * [BRS11] Boaz Barak, Prasad Raghavendra, and David Steurer.  Rounding semidefinite programming hierarchies via global correlation.  In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, pages 472–481, 2011.
  * [Cha16] Siu On Chan.  Approximation resistance from pairwise-independent subgroups.  J. ACM, 63(3), August 2016.
  * [Chu97] F. R. K. Chung.  Spectral Graph Theory.  American Mathematical Society, 1997.
  * [CT06] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing).  Wiley-Interscience, New York, NY, USA, 2006.
  * [DDG+15] Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar.  Direct sum testing.  ITCS ’15, pages 327–336, New York, NY, USA, 2015. ACM.
  * [Del75] P. Delsarte.  The association schemes of coding theory.  In Combinatorics, pages 143–161. Springer Netherlands, 1975.
  * [DHK+19] Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma.  List decoding with double samplers.  In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms, pages 2134–2153, 2019.
  * [DK17] Irit Dinur and Tali Kaufman.  High dimensional expanders imply agreement expanders.  In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science, pages 974–985, 2017.
  * [DS14] Irit Dinur and David Steurer.  Direct product testing.  In Proceedings of the 29th IEEE Conference on Computational Complexity, CCC ’14, pages 188–196, 2014.
  * [Gal62] R. Gallager.  Low-density parity-check codes.  IRE Transactions on Information Theory, 8(1):21–28, 1962.
  * [GI01] Venkatesan Guruswami and Piotr Indyk.  Expander-based constructions of efficiently decodable codes.  In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 658–667, 2001.
  * [GI03] Venkatesan Guruswami and Piotr Indyk.  Linear time encodable and list decodable codes.  In Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.
  * [GI04] Venkatesan Guruswami and Piotr Indyk.  Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.  In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, pages 756–757, 2004.
  * [Gil52] E.N. Gilbert.  A comparison of signalling alphabets.  Bell System Technical Journal, 31:504–522, 1952.
  * [GKO+17] Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf.  Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound.  In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 2073–2091, 2017.
  * [GR06] Venkatesan Guruswami and Atri Rudra.  Explicit capacity-achieving list-decodable codes.  In Proceedings of the 38th ACM Symposium on Theory of Computing, pages 1–10, 2006.
  * [GR08] Venkatesan Guruswami and Atri Rudra.  Concatenated codes can achieve list-decoding capacity.  In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pages 258–267, 2008.
  * [Gri01] Dima Grigoriev.  Linear lower bound on degrees of positivstellensatz calculus proofs for the parity.  Theor. Comput. Sci., 259(1-2):613–622, 2001.
  * [GRS19] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan.  Essential coding theory.  2019\.
  * [GRY19] Venkatesan Guruswami, Andrii Riazanov, and Min Ye.  Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity.  Electronic Colloquium on Computational Complexity (ECCC), 26:154, 2019.
  * [GS11] Venkatesan Guruswami and Ali Kemal Sinop.  Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives.  In FOCS, pages 482–491, 2011.
  * [Gur05] Venkatesan Guruswami.  Algebraic-geometric generalizations of the Parvaresh-Vardy codes.  Electronic Colloquium on Computational Complexity (ECCC), (132), 2005.
  * [Gur09] Venkatesan Guruswami.  List decoding of binary codes–a brief survey of some recent results.  In Coding and Cryptology, pages 97–106. Springer Berlin Heidelberg, 2009.
  * [Gur10] Venkatesan Guruswami.  Bridging Shannon and Hamming: List error-correction with optimal rate.  In ICM, 2010.
  * [Ham50] Richard Hamming.  Error detecting and error correcting codes.  Bell System Technical Journal, 29:147–160, 1950.
  * [Hås97] J. Håstad.  Some optimal inapproximability results.  In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 1–10, 1997.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798–859, 2001.
  * [HRW17] B. Hemenway, N. Ron-Zewi, and M. Wootters.  Local list recovery of high-rate tensor codes applications.  In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science, pages 204–215, Oct 2017.
  * [IKW09] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson.  New direct-product testers and 2-query PCPs.  In Proceedings of the 41st ACM Symposium on Theory of Computing, STOC ’09, pages 131–140, 2009.
  * [IW97] Russell Impagliazzo and Avi Wigderson.  $P=BPP$ unless $E$ has sub-exponential circuits.  In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 220–229, 1997.
  * [LPS88] Alexander Lubotzky, R. Phillips, and Peter Sarnak.  Ramanujan graphs.  Combinatorica, 8:261–277, 1988.
  * [MMT11] Alexander May, Alexander Meurer, and Enrico Thomae.  Decoding random linear codes in $\tilde{\mathcal{O}}(2^{0.054n})$.  In Advances in Cryptology – ASIACRYPT 2011, pages 107–124, 2011\.
  * [MRRW77] R. McEliece, E. Rodemich, H. Rumsey, and L. Welch.  New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities.  IEEE Transactions on Information Theory, 23(2):157–166, 1977.
  * [MRRZ+19] Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters.  LDPC codes achieve list decoding capacity, 2019.  arXiv:1909.06430.
  * [NN90] J. Naor and M. Naor.  Small-bias probability spaces: efficient constructions and applications.  In Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 213–223, 1990.
  * [NS09] Michael Navon and Alex Samorodnitsky.  Linear programming bounds for codes via a covering argument.  Discrete Comput. Geom., 41(2):199–207, March 2009.
  * [RT12] Prasad Raghavendra and Ning Tan.  Approximating CSPs with global cardinality constraints using SDP hierarchies.  In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 373–387, 2012.
  * [RVW00] O. Reingold, S. Vadhan, and A. Wigderson.  Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors.  In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, 2000.
  * [Sha48] Claude Shannon.  A mathematical theory of communications.  Bell System Technical Journal, 27:379–423, 623–656, 1948.
  * [SKS19] Ronen Shaltiel, Swastik Kopparty, and Jad Silbak.  Quasilinear time list-decodable codes for space bounded channels.  2019\.
  * [Sti08] Henning Stichtenoth.  Algebraic Function Fields and Codes.  Springer Publishing Company, Incorporated, 2nd edition, 2008.
  * [Tho83] C. Thommesen.  The existence of binary linear concatenated codes with Reed- Solomon outer codes which asymptotically meet the Gilbert-Varshamov bound.  IEEE Transactions on Information Theory, 29(6):850–853, November 1983.
  * [TS17] Amnon Ta-Shma.  Explicit, almost optimal, epsilon-balanced codes.  In Proceedings of the 49th ACM Symposium on Theory of Computing, STOC 2017, pages 238–251, New York, NY, USA, 2017. ACM.
  * [Var57] R.R. Varshamov.  Estimate of the number of signals in error correcting codes.  Doklady Akademii Nauk SSSR, 117:739–741, 1957.
  * [vL99] Jacobus H. van Lint.  Introduction to Coding Theory.  Springer-Verlag, 1999.

##  Appendix A Auxiliary Results to Obtain Tensoriality

A key result used in the SOS rounding analysis is embodied in Lemma A.1 below.
Roughly speaking, it quantifies the decrease in the potential $\Phi^{G}$,
under conditioning on a random $\mathbf{Y}_{i}$ for $i\sim V$, when the
ensemble $\\{\mathbf{Y}_{i}\\}$ has non-trivial correlation over the edges and
$G$ is a strong enough expander graph. A generalization of this result to low
threshold rank graphs was present in [BRS11]. To derive sharper parameters in
the simpler expander case and to make the presentation self-contained, we give
(essentially) a full proof of this result.

######  Lemma A.1 (Progress Lemma).

Suppose $G$ satisfy $\lambda_{2}(G)\leq\beta^{2}/q^{4}$. If

$\mathchoice{\underset{i\sim
j}{\mathbb{E}}\left[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}\right]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}\geq\beta,$

then

$\mathchoice{\underset{j\sim
V}{\mathbb{E}}\left[\Phi^{G}_{|\mathbf{Y}_{j}}\right]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}\leq\Phi^{G}-\frac{\beta^{2}}{4\cdot q^{4}}.$

###  A.1 Expander Case

We will need the following characterization of the spectral gap of regular
graph $G$. We denote by $\mathsf{A}_{G}$ its adjacency operator and by
$\mathsf{L}_{G}$ its Laplacian operator [Chu97].

######  Fact A.2 (Spectral Gap [Chu97]).

$\lambda_{2}(\mathsf{L}_{G})~{}=~{}\min_{v_{1},\dots,v_{n}\in\mathbb{R}^{n}}\frac{{\mathbb{E}}_{i\sim
j}\left\lVert v_{i}-v_{j}\right\rVert^{2}}{{\mathbb{E}}_{i,j\sim V}\left\lVert
v_{i}-v_{j}\right\rVert^{2}}.$

Using the above characterization, we derive the following local-to-global
result.

######  Lemma A.3 (Local-to-Global).

Let $v_{1},\dots,v_{n}\in\mathbb{R}^{n}$ be vectors in the unit ball. Suppose
$\lambda_{2}(\mathsf{L}_{G})\geq 1-\beta/2$ (equivalently
$\lambda_{2}(\mathsf{A}_{G})\leq\beta/2$). If ${\mathbb{E}}_{i\sim
j}\left\langle v_{i},v_{j}\right\rangle\geq\beta$, then

${\mathbb{E}}_{i,j\sim V}\left\langle
v_{i},v_{j}\right\rangle~{}\geq~{}\frac{\beta}{2}.$

###### Proof.

Using A.2, we have

$\lambda_{2}(\mathsf{L}_{G})~{}\leq~{}\frac{{\mathbb{E}}_{i\sim V}\left\lVert
v_{i}\right\rVert^{2}-{\mathbb{E}}_{i\sim j}\left\langle
v_{i},v_{j}\right\rangle}{{\mathbb{E}}_{i\sim V}\left\lVert
v_{i}\right\rVert^{2}-{\mathbb{E}}_{i,j\sim V}\left\langle
v_{i},v_{j}\right\rangle}.$

Set $\lambda_{2}=\lambda_{2}(\mathsf{L}_{G})$. We consider two cases:
$\lambda_{2}\leq 1$ and $\lambda_{2}>1$. First, suppose $\lambda_{2}\leq 1$.
Then

$\displaystyle{\mathbb{E}}_{i,j\sim V}\left\langle v_{i},v_{j}\right\rangle$
$\displaystyle~{}\geq~{}\frac{1}{\lambda_{2}}{\mathbb{E}}_{i\sim
j}\left\langle
v_{i},v_{j}\right\rangle-\left(\frac{1-\lambda_{2}}{\lambda_{2}}\right){\mathbb{E}}_{i\sim
V}\left\lVert v_{i}\right\rVert^{2}$
$\displaystyle~{}\geq~{}\frac{1}{\lambda_{2}}\left(\beta-\left(1-\lambda_{2}\right)\right)$
$\displaystyle~{}\geq~{}\frac{1}{\lambda_{2}}\left(\beta-\left(\frac{\beta}{2}\right)\right)\geq\frac{\beta}{2}.$

Now suppose $\lambda_{2}>1$. Then

$\displaystyle{\mathbb{E}}_{i,j\sim V}\left\langle v_{i},v_{j}\right\rangle$
$\displaystyle~{}\geq~{}\frac{1}{\lambda_{2}}{\mathbb{E}}_{i\sim
j}\left\langle
v_{i},v_{j}\right\rangle-\left(\frac{1-\lambda_{2}}{\lambda_{2}}\right){\mathbb{E}}_{i\sim
V}\left\lVert v_{i}\right\rVert^{2}$
$\displaystyle~{}\geq~{}\frac{1}{\lambda_{2}}{\mathbb{E}}_{i\sim
j}\left\langle
v_{i},v_{j}\right\rangle\geq\frac{1}{\lambda_{2}}\cdot\beta\geq\frac{\beta}{2},$

where the last inequality follows from $\lambda_{2}\leq 2$ for any graph $G$.

#### More Preliminaries

We will need some standard notions in information theory [CT06].

######  Definition A.4 (Relative Entropy/Kullback-Leibler Divergence).

The relative entropy of two distributions $D_{1}$ and $D_{2}$ with support
contained in $\mathcal{Q}$ is

$\textup{KL}(D_{1},D_{2})~{}\coloneqq~{}\sum_{a\in\mathcal{Q}}D_{1}(a)\log\left(\frac{D_{1}(a)}{D_{2}(a)}\right).$

######  Notation A.5.

Let $\mathbf{X}$ be a random variable. We denote by $\\{\mathbf{X}\\}$ the
distribution of $\mathbf{X}$.

######  Definition A.6 (Mutual Information).

Let $\mathbf{X},\mathbf{Y}$ be two random variables. The mutual information
$\textup{I}(\mathbf{X},\mathbf{Y})$ is

$\textup{I}(\mathbf{X},\mathbf{Y})~{}\coloneqq~{}\textup{KL}(\\{\mathbf{X},\mathbf{Y}\\},\\{\mathbf{X}\\}\\{\mathbf{Y}\\}).$

######  Fact A.7.

$\textup{I}(\mathbf{X},\mathbf{Y})~{}=~{}\textup{H}(\mathbf{X})-\textup{H}(\mathbf{X}|\mathbf{Y}).$

######  Fact A.8 (Fact B.5 of Raghavendra and Tan [RT12]).

Let $\mathbf{X}_{a}$ and $\mathbf{X}_{b}$ be indicator random variables. Then

$\textup{Cov}(\mathbf{X}_{a},\mathbf{X}_{b})^{2}~{}\leq~{}2\cdot\textup{I}(\mathbf{X}_{a},\mathbf{X}_{b}).$

#### Progress Lemma

We are ready to prove Lemma A.1 which we restate below for convenience.

######  Lemma A.9 (Progress Lemma (restatement of Lemma A.1)).

Suppose $G$ satisfy $\lambda_{2}(G)\leq\beta^{2}/q^{4}$. If

$\mathchoice{\underset{i\sim
j}{\mathbb{E}}\left[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}\right]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}\geq\beta,$

then

$\mathchoice{\underset{j\sim
V}{\mathbb{E}}\left[\Phi^{G}_{|\mathbf{Y}_{j}}\right]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}\leq\Phi^{G}-\frac{\beta^{2}}{4\cdot q^{4}}.$

###### Proof.

Firstly, we show how to relate the distances
$\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}$
over the edges $i\sim j$ to certain covariances. Let $a,b\in[q]^{2}$. Observe
that

$\left\lvert\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\right\rvert~{}=~{}\left\lvert\Pr[\mathbf{Y}_{i}=a\wedge\mathbf{Y}_{j}=b]-\Pr[\mathbf{Y}_{i}=a]\Pr[\mathbf{Y}_{j}=b]\right\rvert.$

We have

$\displaystyle\mathchoice{\underset{i\sim
j}{\mathbb{E}}\left[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}\right]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}~{}\geq~{}$
$\displaystyle\left(\mathchoice{\underset{i\sim
j}{\mathbb{E}}\left[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\left|\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\right|\right]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\left|\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\right|]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\left|\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\right|]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\left|\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\right|]}\right)^{2}$
$\displaystyle~{}\geq~{}$
$\displaystyle\frac{1}{q^{4}}\left(\mathchoice{\underset{i\sim
j}{\mathbb{E}}\left[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}\right]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}{{\mathbb{E}}_{i\sim
j}[\left\lVert\\{\mathbf{Y}_{i}\mathbf{Y}_{j}\\}-\\{\mathbf{Y}_{i}\\}\\{\mathbf{Y}_{j}\\}\right\rVert_{1}]}\right)^{2}\geq\frac{\beta^{2}}{q^{4}}.$

Note that the graph $\mathcal{F}\coloneqq G\otimes J/q$ is an expander with
$\lambda_{2}(G\otimes J/q)=\lambda_{2}(G)$. Moreover, the matrix
$\mathsf{C}\coloneqq\\{\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\\}_{i,j\in
V;a,b\in[q]^{2}}$ is PSD since the vectorization
$\\{v_{i,a}-{\mathbb{E}}[\mathbf{Y}_{i,a}]\cdot v_{\emptyset}\\}_{i\in
V;a\in[q]}$ gives a Gram matrix decomposition of $\mathsf{C}$. Thus, the
covariance matrix
$\\{\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}\\}_{i,j\in
V;a,b\in[q]^{2}}$ is also PSD since it is the Schur product (i.e., entrywise
product) of two PSD matrices, namely, $\mathsf{C}\circ\mathsf{C}$. Therefore,
we are in position of applying the local-to-global Lemma A.3 with the expander
$\mathcal{F}$ and a vectorization for $\mathsf{C}\circ\mathsf{C}$. We have

$\displaystyle\frac{\beta^{2}}{q^{4}}$
$\displaystyle~{}\leq~{}\mathchoice{\underset{i\sim
j}{\mathbb{E}}\left[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}\right]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}{{\mathbb{E}}_{i\sim
j}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}$
$\displaystyle~{}\leq~{}2\mathchoice{\underset{i,j\sim V^{\otimes
2}}{\mathbb{E}}\left[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}\right]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\frac{1}{q^{2}}\sum_{a,b\in[q]^{2}}\textup{Cov}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)^{2}]}$
(local-to-global Lemma A.3)
$\displaystyle~{}\leq~{}\frac{4}{q^{2}}\mathchoice{\underset{i,j\sim
V^{\otimes
2}}{\mathbb{E}}\left[\sum_{a,b\in[q]^{2}}\textup{I}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)\right]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a,b\in[q]^{2}}\textup{I}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a,b\in[q]^{2}}\textup{I}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a,b\in[q]^{2}}\textup{I}\left(\mathbf{Y}_{i,a},\mathbf{Y}_{j,b}\right)]}$
(A.8) $\displaystyle~{}\leq~{}\frac{4}{q^{2}}\mathchoice{\underset{i,j\sim
V^{\otimes
2}}{\mathbb{E}}\left[\sum_{a,b\in[q]^{2}}\textup{H}\left(\mathbf{Y}_{i,a}\right)-\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j,b}\right)\right]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a,b\in[q]^{2}}\textup{H}\left(\mathbf{Y}_{i,a}\right)-\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j,b}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a,b\in[q]^{2}}\textup{H}\left(\mathbf{Y}_{i,a}\right)-\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j,b}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a,b\in[q]^{2}}\textup{H}\left(\mathbf{Y}_{i,a}\right)-\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j,b}\right)]}$
$\displaystyle~{}\leq~{}\frac{4}{q}\left[\mathchoice{\underset{i\sim
V}{\mathbb{E}}\left[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}\right)\right]}{{\mathbb{E}}_{i\sim
V}[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}\right)]}{{\mathbb{E}}_{i\sim
V}[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}\right)]}{{\mathbb{E}}_{i\sim
V}[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}\right)]}-\mathchoice{\underset{i,j\sim
V^{\otimes
2}}{\mathbb{E}}\left[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j}\right)\right]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\sum_{a\in[q]}\textup{H}\left(\mathbf{Y}_{i,a}|\mathbf{Y}_{j}\right)]}\right]$
$\displaystyle~{}=~{}4\left[\mathchoice{\underset{i\sim
V}{\mathbb{E}}\left[\mathcal{H}\left(\mathbf{Y}_{i}\right)\right]}{{\mathbb{E}}_{i\sim
V}[\mathcal{H}\left(\mathbf{Y}_{i}\right)]}{{\mathbb{E}}_{i\sim
V}[\mathcal{H}\left(\mathbf{Y}_{i}\right)]}{{\mathbb{E}}_{i\sim
V}[\mathcal{H}\left(\mathbf{Y}_{i}\right)]}-\mathchoice{\underset{i,j\sim
V^{\otimes
2}}{\mathbb{E}}\left[\mathcal{H}\left(\mathbf{Y}_{i}|\mathbf{Y}_{j}\right)\right]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\mathcal{H}\left(\mathbf{Y}_{i}|\mathbf{Y}_{j}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes
2}}[\mathcal{H}\left(\mathbf{Y}_{i}|\mathbf{Y}_{j}\right)]}{{\mathbb{E}}_{i,j\sim
V^{\otimes 2}}[\mathcal{H}\left(\mathbf{Y}_{i}|\mathbf{Y}_{j}\right)]}\right]$
$\displaystyle~{}=~{}4\left[\Phi^{G}-\mathchoice{\underset{j\sim
V}{\mathbb{E}}\left[\Phi^{G}_{|\mathbf{Y}_{j}}\right]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}\right].$

Therefore, we have $\mathchoice{\underset{j\sim
V}{\mathbb{E}}\left[\Phi^{G}_{|\mathbf{Y}_{j}}\right]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}{{\mathbb{E}}_{j\sim
V}[\Phi^{G}_{|\mathbf{Y}_{j}}]}\leq\Phi^{G}-\beta^{2}/(4\cdot q^{4})$, as
claimed.

##  Appendix B Explicit Structures

We recall some explicit structures used in Ta-Shma’s construction.

###  B.1 Explicit Ramanujan Graphs

The outer graph $G$ in the $s$-wide replacement product was chosen to be a
Ramanujan graph. Ta-Shma provides a convenient lemma to efficiently obtain
explicit Ramanujan graphs given the intended number of vertices $n$ (which
might end up being nearly twice this much), the expansion $\lambda$ and an
error parameter $\theta>0$. These Ramanujan graphs are based on the LPS
construction [LPS88]. Due to number theoretic reasons, we might be forced to
work with slightly different parameters, but this is not an issue.

######  Lemma B.1 (Lemma 2.10 [TS17]).

For every $\theta>0$, there exists an algorithm that given $n$ and
$\lambda\in(0,1)$ runs in time ${\mathrm{poly}}(n)$ and outputs a Ramanujan
graph $G$ such that

  * -

$G$ has degree $d\leq 8/\lambda$,

  * -

$\sigma_{2}(G)\leq\lambda$, and

  * -

$\left\lvert V(G)\right\rvert$ is either in the range $[(1-\theta)n,n]$ or in
the range $[(1-\theta)2n,2n]$.

Moreover, the algorithm outputs a locally invertible function
$\varphi\colon[d]\rightarrow[d]$ computable in polynomial time in its input
length.

###  B.2 Explicit Biased Distribution

The inner graph $H$ in the $s$-wide replacement product is chosen to be a
Cayley graph on $\mathbb{Z}_{2}^{m}$ for some positive integer $m$. Ta-Shma
uses the construction of Alon et al. [AGHP92] (AGHP) to deduce a result
similar to Lemma B.2 below. To compute the refined parameter version of our
main result Theorem 1.1, we will need the specifics of the AGHP construction.

######  Lemma B.2 (Based on Lemma 6 [TS17]).

For every $\beta=\beta(m)$, there exists a fully explicit set
$A\subseteq\mathbb{Z}_{2}^{m}$ such that

  * -

$\left\lvert A\right\rvert\leq 4\cdot m^{2}/\beta^{2}$, and

  * -

for every $S\subseteq[m]$, we have $\left\lvert{\mathbb{E}}_{z\in
A}\chi_{S}(z)\right\rvert\leq\beta$.

Furthermore, if $m/\beta$ is a power of $2$, then $\left\lvert
A\right\rvert=m^{2}/\beta^{2}$. In particular, the graph
$\textup{Cay}(\mathbb{Z}_{2}^{m},A)$ is a $(n=2^{m},d=\left\lvert
A\right\rvert,\lambda=\beta)$ expander graph.

######  Remark B.3.

Given $d,m\in\mathbb{N}^{+}$ such that $d$ is the square of a power of $2$
with $d\leq 2^{m}$, by setting $\beta=m/\sqrt{d}$ we can use Lemma B.2 with
$\beta$ and $m$ (note that $m/\beta$ is a power of $2$) to obtain a Cayley
graph $\textup{Cay}(\mathbb{Z}_{2}^{m},A)$ with parameters
$(n=2^{m},d=\left\lvert A\right\rvert,\lambda=\beta)$.

##  Appendix C Zig-Zag Spectral Bound

We prove the zig-zag spectral bound 4.4.

######  Claim C.1.

Let $G$ be an outer graph and $H$ be an inner graph used in the $s$-wide
replacement product. For any integer $0\leq i\leq s-1$,

$\sigma_{2}((I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H}))\leq\sigma_{2}(G)+2\cdot\sigma_{2}(H)+\sigma_{2}(H)^{2}.$

###### Proof.

Let $v$ be a unit vector such that $v\bot\mathbf{1}$, and decompose it into
$v=u+w$ such that $u\in\mathcal{W}^{\parallel}=\textup{span}\\{a\otimes
b\in\mathbb{R}^{V(G)}\otimes\mathbb{R}^{V(H)}\mid b=\mathbf{1}\\}$ and
$w\in\mathcal{W}^{\bot}=(\mathcal{W}^{\parallel})^{\bot}$.

$\displaystyle\left|\left\langle
v,(I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H})v\right\rangle\right|\leq$
$\displaystyle\left|\left\langle
u,(I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H})u\right\rangle\right|+\left|\left\langle
u,(I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H})w\right\rangle\right|+$
$\displaystyle\left|\left\langle
w,(I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H})u\right\rangle\right|+\left|\left\langle
w,(I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H})w\right\rangle\right|$
$\displaystyle\leq$ $\displaystyle\left|\left\langle
u,G_{i}u\right\rangle\right|+|(I\otimes\mathsf{A}_{H})w|+$
$\displaystyle|(I\otimes\mathsf{A}_{H})w|+|(I\otimes\mathsf{A}_{H})w|^{2}$
$\displaystyle\leq$ $\displaystyle\left|\left\langle
u,G_{i}u\right\rangle\right|+2\sigma_{2}(H)+\sigma_{2}^{2}(H)$

To bound $\left|\left\langle
u,(I\otimes\mathsf{A}_{H})G_{i}(I\otimes\mathsf{A}_{H})u\right\rangle\right|$,
observe that $u=x\otimes\mathbf{1}$ for some $x\in\mathbb{R}^{V(G)}$. Then,

$0=\left\langle v,\mathbf{1}\right\rangle=\left\langle
u,\mathbf{1}\right\rangle+\left\langle w,\mathbf{1}\right\rangle=\left\langle
u,\mathbf{1}\right\rangle=\left\langle x,\mathbf{1}_{G}\right\rangle$

so that $x\bot\mathbf{1}_{G}$. Because $u$ is uniform over $H$-component,
$\left|\left\langle u,G_{i}u\right\rangle\right|=\left|\left\langle
x,Gx\right\rangle\right|\leq\sigma_{2}(G)$, which completes the proof.

We also derive a (simple) tighter bound for the expansion of the zig-zag
product in a particular parameter regime.

######  Claim C.2.

Let $G$ be a $\lambda_{1}$-two-sided expander and $H$ be a $\lambda_{2}$-two-
sided expander such that both are regular graphs. If
$\lambda_{1}\leq\lambda_{2}$, then

$\sigma_{2}(G\operatorname{\leavevmode\hbox to9.42pt{\vbox
to9.42pt{\pgfpicture\makeatletter\hbox{\hskip 4.70757pt\lower-4.70757pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.50757pt}{0.0pt}\pgfsys@curveto{4.50757pt}{2.48949pt}{2.48949pt}{4.50757pt}{0.0pt}{4.50757pt}\pgfsys@curveto{-2.48949pt}{4.50757pt}{-4.50757pt}{2.48949pt}{-4.50757pt}{0.0pt}\pgfsys@curveto{-4.50757pt}{-2.48949pt}{-2.48949pt}{-4.50757pt}{0.0pt}{-4.50757pt}\pgfsys@curveto{2.48949pt}{-4.50757pt}{4.50757pt}{-2.48949pt}{4.50757pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.22221pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{\rm z}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}H)\leq
2\cdot\lambda_{2}.$

###### Proof.

Let $v=a\cdot v^{\parallel}+b\cdot v^{\perp}$ with $a^{2}+b^{2}=1$ be such
that $v\perp 1$. In particular, if $v^{\parallel}=v^{G}\otimes 1^{H}$, then
$v^{G}\perp 1^{G}$ since otherwise $\left\langle v,1\right\rangle=\left\langle
v^{G},1^{G}\right\rangle\neq 0$. We have

$\displaystyle\max_{a,b\in\mathbb{R}\colon
a^{2}+b^{2}=1}a^{2}\cdot\lambda_{1}+2ab\cdot\lambda_{2}+b^{2}\cdot\lambda_{2}^{2}$
$\displaystyle\leq\max_{a,b\in\mathbb{R}\colon
a^{2}+b^{2}=1}a^{2}\cdot\lambda_{2}+2ab\cdot\lambda_{2}+b^{2}\cdot\lambda_{2}$
$\displaystyle=\max_{a,b\in\mathbb{R}\colon
a^{2}+b^{2}=1}\lambda_{2}+2ab\cdot\lambda_{2},$

where the inequality follows from the assumption $\lambda_{1}\leq\lambda_{2}$
(and trivially $\lambda_{2}^{2}\leq\lambda_{2}$) and the equality follows from
$a^{2}+b^{2}=1$. Since we also have $2ab=(a+b)^{2}-(a^{2}+b^{2})\leq 1$, the
result follows.

##  Appendix D Derandomization

To unique decode in fixed polynomial time (i.e.,
${\mathrm{poly}}(n/\varepsilon)$) we need to prune the list of coupled words
$\mathcal{L}$ covering the list
$\mathcal{L}^{*}(\tilde{y})=\\{(z,y=\operatorname{dsum}(z))\mid
z\in\mathcal{C},\Delta(\tilde{y},y)\leq 1/2-\sqrt{n}\\}$ of codewords we want
to retrieve. To do so, given
$(z^{*},y^{*}=\operatorname{dsum}(z^{*}))\in\mathcal{L}^{*}(\tilde{y})$, we
need to have $(z,y=\operatorname{dsum}(z))\in\mathcal{L}$ such that

  1. 1.

$\left\lvert\left\langle
y^{*},\operatorname{dsum}(z)\right\rangle\right\rvert$ is not too small, and

  2. 2.

$\left\langle\tilde{y},\operatorname{dsum}(z)\right\rangle$ is not too small
(in order to apply Lemma 6.11).

The slice $(S,\sigma)$ of the SOS solution from which $y^{*}$ is recoverable
satisfies in expectation

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\langle
y^{*},\operatorname{dsum}(z)\right\rangle^{2}\right]\geq 3\eta^{2},$

and

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\langle\tilde{y},\operatorname{dsum}(z)\right\rangle\right]\geq
3\sqrt{\eta}/2.$

Moreover, since $z\mapsto\left\langle
y^{*},\operatorname{dsum}(z)\right\rangle^{2}$ and
$z\mapsto\left\langle\tilde{y},\operatorname{dsum}(z)\right\rangle$ are
$O(1/n)$-Lipschitz 111111In this fixed polynomial time regime, the parameters
$s,d_{1},d_{2},\varepsilon_{0},\eta$ are constant independent of the final
bias $\varepsilon$. with respect to the $\ell_{1}$-norm, Hoeffding’s
inequality gives

$\operatorname*{\mathbb{P}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\langle
y^{*},\operatorname{dsum}(z)\right\rangle^{2}<\eta^{2}\right]\leq\exp\left(-\Theta(n)\right),$

and

$\operatorname*{\mathbb{P}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\langle\tilde{y},\operatorname{dsum}(z)\right\rangle<\sqrt{\eta}\right]\leq\exp\left(-\Theta(n)\right).$

At least randomly, such a $z$ can be easily found. In [AJQ+20], alternatively
to satisfying Item 1 it was shown that by choosing $z^{\prime}\in\\{\pm
1\\}^{n}$ by majority vote, i.e.

$z^{\prime}_{i}=\operatorname*{\arg\\!\max}_{b\in\\{\pm
1\\}}\operatorname*{\mathbb{P}}[\mathbf{Z}_{i}=b]$

for $i\in[n]$, one has that $\left\lvert\left\langle
z^{*},z^{\prime}\right\rangle\right\rvert$ is large which is enough to address
the first item. More precisely implicit in [AJQ+20], for any constant
$\beta\in(0,1)$ as long as parity sampling is sufficiently strong we have

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\langle
z^{\prime},z\right\rangle^{2}\right]\geq 1-\beta.$

Similarly $z\mapsto\left\langle z^{\prime},z\right\rangle^{2}$ is
$O(1/n)$-Lipschitz with respect to the $\ell_{1}$-norm, so Hoeffding’s
inequality yields

$\operatorname*{\mathbb{P}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\langle
z^{\prime},z\right\rangle^{2}<1-\beta/2\right]\leq\exp\left(-\Theta(n)\right).$

However, we want to efficiently and deterministically find a $z$ satisfying
$\left\langle z^{\prime},z\right\rangle^{2}\geq 1-\beta/2$ as well as
satisfying Item 2. Note that at this stage in the decoding process $y^{*}$ is
not known (without issuing a recursive unique decoding call), so running
expectation maximization to satisfy item Item 1 would not be possible.
Fortunately, the majority $z^{\prime}$ can be cheaply computed without a
recursive call to an unique decoder. On the other hand $z$ satisfying only
Item 2 can be found by expectation maximization. The challenge is to satisfy
both conditions at the same time. For this reason, we design a simultaneous
expectation maximization derandomization procedure tailored to our setting.

###  D.1 Abstract Derandomization: Simultaneous Expectation Maximization

Suppose that $\Omega$ is a probability space where two random variables
$\mathbf{A}$ and $\mathbf{B}$ are defined satisfying the following first
moment conditions

${\mathbb{E}}\left[\mathbf{A}\right]\geq a\quad\text{ and
}\quad{\mathbb{E}}\left[\mathbf{B}\right]\geq 1-\beta.$

We provided a sufficient conditions so that $\omega\in\Omega$ satisfying

$\mathbf{A}(\omega)\geq a^{\prime}\quad\text{ and }\quad\mathbf{B}(\omega)\geq
1-\beta^{\prime}$

can be efficiently deterministically found with the aid of an oracle, where
$a\approx a^{\prime}$ and $\beta\approx\beta^{\prime}$. More precisely, we
have the following lemma.

######  Lemma D.1.

Let $\Omega=(\\{-1,1\\}^{n},\nu_{1}\times\cdots\times\nu_{n})$ be a
probability space with a product distribution. Suppose $\mathbf{A}\in[-1,1]$
is a random variable on $\Omega$ satisfying, for $a>0$ and for some function
$e_{A}\colon\mathbb{N}\rightarrow\mathbb{R}^{+}$,

$\operatorname*{\mathbb{P}}\left[\mathbf{A}<a\right]\leq e_{A}(n).$

Suppose $\mathbf{B}\in[-1,1]$ is a random variable on $\Omega$ satisfying, for
some function
$e_{B}\colon\mathbb{N}\times\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$,

$\operatorname*{\mathbb{P}}\left[\mathbf{B}<1-\beta\right]\leq
e_{B}(n,\beta).$

Suppose that there is an oracle to evaluate
${\mathbb{E}}\left[\mathbf{A}\mathbf{B}^{2k}\right]$ under any product
distribution $\mu_{1}^{\prime}\times\cdots\times\mu_{n}^{\prime}$ for
$k\in\mathbb{N}$. Given $\delta,\beta\in(0,1)$, if

$e_{A}(n)+e_{B}(n,\beta/(4\lceil-\ln(a(1-\beta)+1)/\delta\rceil))\leq
a\frac{\beta}{2},$ (10)

then it is possible to find $\omega\in\\{\pm 1\\}^{n}$ using $2n$ invocations
to the oracle and satisfying

$\mathbf{A}(\omega)\geq a(1-\beta)\quad\text{ and
}\quad\left\lvert\mathbf{B}(\omega)\right\rvert\geq 1-\delta.$

###### Proof.

Set $k=\lceil-\ln(a(1-\beta)+1)/\delta\rceil$. Set
$\beta^{\prime}=\beta/(4k)$. Note that

${\mathbb{E}}\left[\mathbf{A}\mathbf{B}^{2k}\right]\geq
a\left(1-\frac{\beta}{4k}\right)^{2k}-e_{A}(n)-e_{B}(n,\beta^{\prime})\geq
a\left(1-\beta\right),$

where we use Eq. 10 in the last inequality. Do expectation maximization to
deterministically find $\omega\in\\{\pm 1\\}^{n}$, with $2\cdot n$ invocations
to the oracle of ${\mathbb{E}}\left[\mathbf{A}\mathbf{B}^{2k}\right]$, such
that

$\mathbf{A}(\omega)\mathbf{B}(\omega)^{2k}\geq a\left(1-\beta\right).$

Since $\mathbf{B}(\omega)^{2k}\leq 1$, we have $\mathbf{A}(\omega)\geq
a\left(1-\beta\right)$. Towards a contradiction suppose
$\left\lvert\mathbf{B}(\omega)\right\rvert\leq 1-\delta$. Using that
$\mathbf{A}(\omega)\leq 1$, we have

$e^{-2k\cdot\delta}\geq(1-\delta)^{2k}\geq\mathbf{A}(\omega)\mathbf{B}(\omega)^{2k}\geq
a(1-\beta).$ (11)

By our choice of $k$, we get

$e^{-2k\cdot\delta}<a(1-\beta),$

contradicting Eq. 11.

###  D.2 Implementing the Oracle

Now, we provide an efficient deterministic oracle for our setting. We take

$\mathbf{A}\coloneqq\left\langle\tilde{y},\operatorname{dsum}(z)\right\rangle\quad\text{
and }\quad\mathbf{B}\coloneqq\left\langle z^{\prime},z\right\rangle^{2},$

where $z^{\prime}_{i}=\operatorname*{\arg\\!\max}_{b\in\\{\pm
1\\}}\operatorname*{\mathbb{P}}[\mathbf{Z}_{i}=b]$. Note that

$\mathbf{A}\mathbf{B}^{2k}=\sum_{T\subset[n]\colon\left\lvert
T\right\rvert=O(1)}\alpha_{T}\prod_{i\in T}z_{i}.$

To compute ${\mathbb{E}}\left[\mathbf{A}\mathbf{B}^{2k}\right]$ under any
product distribution $\mu_{1}^{\prime}\times\cdots\times\mu_{n}^{\prime}$, use
linearity of expectation and sum at most $n^{O(1)}$ terms
$\alpha_{T}{\mathbb{E}}\left[\prod_{i\in T}z_{i}\right]$ where each can be
computed in $O(1)$ since restricted to $T$ we have a product distribution
taking values in $\\{\pm 1\\}^{T}$.