or $-z^{\prime}$ is within the unique decoding radius of $z$.

###### Proof.

Since $\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot
y^{\prime}_{\mathfrak{s}}]\rvert>2\cdot\varepsilon$ and the lifting is odd,
either

${\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot\operatorname{lift}(z^{\prime})_{\mathfrak{s}}]>2\cdot\varepsilon,$

or

${\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot\operatorname{lift}(-z^{\prime})_{\mathfrak{s}}]={\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}\left[-y_{\mathfrak{s}}\cdot\operatorname{lift}(z^{\prime})_{\mathfrak{s}}\right]>2\cdot\varepsilon.$

Then either $\Delta\lparen y,\operatorname{lift}(z^{\prime})\rparen\leq
1/2-\varepsilon$ or $\Delta\lparen
y,\operatorname{lift}(-z^{\prime})\rparen\leq 1/2-\varepsilon$. Using 6.31 we
conclude the proof.

#### Cover Purification

A $\delta$-bias cover $\mathcal{M}$ of $\mathcal{L}$ for small $\delta$ may
require further processing in order to actually retrieve $\mathcal{L}$.
Provided the lifting is sufficiently robust, trying to unique decode $z$ for
$(z,y)\in\mathcal{M}^{\pm}$, where $\mathcal{M}^{\pm}$ is the sign completion
as defined next, and then lifting the decoded word yields a new coupled list
that contains $\mathcal{L}$. This process is referred to as cover purification
and its formalization is the object of this section.

######  Definition 6.34 (Sign Completion).

Let $\mathcal{M}$ be coupled list. We say that $\mathcal{M}^{\pm}$ defined as

$\mathcal{M}^{\pm}\coloneqq\left\\{(z,\operatorname{lift}(z)),(-z,\operatorname{lift}(-z))~{}|~{}(z,y)\in\mathcal{M}\right\\},$

is the sign completion of $\mathcal{M}$.

The correctness of the cover purification process is established next.

######  Lemma 6.35 (Purification lemma).

Suppose $\operatorname{lift}$ is a
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust lifting from $\mathcal{C}_{1}$
to $\mathcal{C}_{k}$ which is either

  * -

linear and a $(1/2+\varepsilon_{0},2\cdot\varepsilon)$-parity sampler; or

  * -

$(1/4-\varepsilon_{0}/2)$-robust and odd.

Let $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ be $(1/2-\sqrt{\varepsilon})$-close to
$\mathcal{C}_{k}$ and $\mathcal{L}=\mathcal{L}(\tilde{y},\mathcal{C}_{k})$ be
its code list. If $\mathcal{M}=\\{(z^{(i)},y^{(i)})|i\in[h]\\}$ is a
$2\varepsilon$-bias cover of $\mathcal{L}$, then

$\mathcal{L}\subseteq\left\\{\operatorname{lift}(z)~{}|~{}z\in\textup{Dec}_{\mathcal{C}_{1}}\left(\bf{\textup{P}}_{1}\left(\mathcal{M}^{\pm}\right)\right)\right\\}\eqqcolon\mathcal{L}^{\prime},$

where $\bf{\textup{P}}_{1}$ is the projection on the first coordinate and
$\textup{Dec}_{\mathcal{C}_{1}}$ is a unique decoder for $\mathcal{C}_{1}$.
Furthermore, $\mathcal{L}^{\prime}$ can be computed in time
$O\left(\left|\mathcal{M}\right|\cdot f(n)\right)$ where $f(n)$ is the running
time of a unique decoding algorithm of $\mathcal{C}_{1}$.

###### Proof.

Let $y\in\mathcal{L}$. By the $2\varepsilon$-cover property, there exists a
coupled pair $(z^{\prime},y^{\prime})\in\mathcal{M}$ satisfying
$\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot
y^{\prime}_{\mathfrak{s}}]\rvert>2\cdot\varepsilon$. Combining this bound with
the appropriate robustness assumptions, 6.32 or 6.33 yields that either
$z^{\prime}$ or $-z^{\prime}$ can be uniquely decoded in $\mathcal{C}_{1}$.
Then

$y\in\left\\{\operatorname{lift}(z)~{}|~{}z\in\textup{Dec}_{\mathcal{C}_{1}}\left(\bf{\textup{P}}_{1}\left(\mathcal{M}^{\pm}\right)\right)\right\\}.$

Finally, observe that computing $\mathcal{L}^{\prime}$ with the claimed
running time is straightforward.

Algorithmically, cover purification works by running the unique decoding
algorithm of $\mathcal{C}_{1}$ on every element of the sign completion
$\mathcal{M}^{\pm}$, described below in 6.36.

######  Algorithm 6.36 (Cover Purification Algorithm).

Input A $2\varepsilon$-bias cover $\mathcal{M}$ for
$\mathcal{L}(\tilde{y},\mathcal{C}_{k})$. Output Coupled List
$\mathcal{L}^{\prime}$ s.t.
$\textup{P}_{2}(\mathcal{L}^{\prime})\supseteq\mathcal{L}(\tilde{y},\mathcal{C}_{k})$.
1. Let $\mathcal{L}^{\prime}=\emptyset$ 2. For
$(z^{\prime},y^{\prime})\in\mathcal{M}^{\pm}$ do 3. If $z^{\prime}$ is
uniquely decodable in $\mathcal{C}_{1}$ then 4. Let
$z=\textup{UniqueDecode}_{\mathcal{C}_{1}}(z^{\prime})$ 5. Let
$y=\operatorname{lift}(z)$ 6. Set
$\mathcal{L}^{\prime}=\mathcal{L}^{\prime}\cup\\{(z,y)\\}$ 7. Output
$\mathcal{L}^{\prime}$.

####  6.6.5 Correctness of the List Decoding Algorithm

The building blocks developed so far are assembled to form the final list
decoding algorithm (6.16), which is restated below for convenience.

######  Algorithm 6.37 (List Decoding Algorithm).

Input A word $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}=\operatorname{lift}(\mathcal{C}_{1})$ Output Coupled code
list $\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$. 1. Solve the
List Decoding Program with $\eta$-accuracy obtaining $\mathbf{Z}$ where
$\eta=\varepsilon^{8}/2^{22}$ 2. Let $\mathcal{M}$ be the output of the Cover
Retrieval 6.29 on $\mathbf{Z}$ 3. Let $\mathcal{L^{\prime}}$ be the output of
the Cover Purification 6.36 on $\mathcal{M}$ 4. Let
$\mathcal{L}^{\prime\prime}=\\{(z,y)\in\mathcal{L}^{\prime}~{}|~{}\Delta\lparen\tilde{y},y\rparen\leq
1/2-\sqrt{\varepsilon}\\}$ 5. Output $\mathcal{L}^{\prime\prime}$.

We are ready to prove the main theorem of the abstract list decoding framework
which follows easily from the properties developed so far.

######  Theorem 6.38 (List Decoding Theorem (Restatement of Theorem 6.17)).

Suppose that $\operatorname{lift}$ is a
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust
$(\varepsilon^{8}/2^{22},L)$-two-step tensorial lifting from $\mathcal{C}_{1}$
to $\mathcal{C}_{k}$ which is either

  * -

linear and a $(1/2+\varepsilon_{0},2\cdot\varepsilon)$-parity sampler; or

  * -

$(1/4-\varepsilon_{0},1/2-\varepsilon/2)$-robust and odd.

Let $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ be $(1/2-\sqrt{\varepsilon})$-close to
$\mathcal{C}_{k}$. Then w.v.h.p. the List Decoding 6.16 returns the coupled
code list $\mathcal{L}(\widetilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$.
Furthermore, the running time is

$n^{O(L+k)}\left({\mathrm{polylog}}(\varepsilon^{-1})+f(n)\right),$

where $n=|X(1)|$ and $f(n)$ is the running time of a unique decoding algorithm
of $\mathcal{C}_{1}$.

###### Proof.

Under the assumptions of the theorem, Lemma 6.30 establishes that the Cover
Retrieval 6.29 returns w.v.h.p. a $2\varepsilon$-bias cover. Then, Lemma 6.35
states that providing this $2\varepsilon$-bias cover as input to the Cover
Purification 6.36 yields a coupled list containing the code list
$\mathcal{L}(\widetilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$. Finally, the
last step in 6.16 ensures the output is precisely
$\mathcal{L}(\widetilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$.

##  7 Instantiation I: Direct Sum on HDXs

We instantiate the list decoding framework to the direct sum lifting on HDXs
obtaining Theorem 7.1, which is the main result in this section. For this
instantiation we need to establish that HDXs are two-step tensorial which will
be done in Section 7.1.

######  Theorem 7.1 (Direct Sum Lifting on HDX).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There exist universal constants $c,C>0$
such that for any $\gamma$-HDX $X(\leq d)$ on ground set $X(1)=[n]$ and
$\Pi_{1}$ uniform, if

$\gamma\leq(\log(1/\varepsilon))^{-C\cdot\log(1/\varepsilon)}\quad\text{ and
}\quad d\geq c\cdot\frac{(\log(1/\varepsilon))^{2}}{\varepsilon},$

then the following holds:

For every binary code $\mathcal{C}_{1}$ with $\Delta(\mathcal{C}_{1})\geq
1/2-\varepsilon_{0}$ on $X(1)=[n]$, there exists a binary lifted code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\varphi(\mathcal{C}_{1}))$ with
$\Delta(\mathcal{C}_{k})\geq 1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}$ on
$X(k)$ where $k=O\left(\log(1/\varepsilon)\right)$, $\varphi$ is an explicit
linear projection, and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time

$n^{\varepsilon^{-O\left(1\right)}}\cdot f(n),$

where $f(n)$ is the running time of a unique decoding algorithm for
$\mathcal{C}_{1}$.

  * -

[Rate] The rate $r_{k}$ of $\mathcal{C}_{k}$ satisfies
$r_{k}=r_{1}\cdot\left\lvert X(1)\right\rvert/\left\lvert X(k)\right\rvert$
where $r_{1}$ is the relative rate of $\mathcal{C}_{1}$.

  * -

[Linearity] If $\mathcal{C}_{1}$ is linear, then $\varphi$ is the identity and
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ is linear.

In particular, invoking Theorem 7.1 on HDXs extracted from Ramanujan complexes
(as in Lemma 4.5), we obtain Corollary 7.2.

######  Corollary 7.2.

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There is an infinite sequence of HDXs
$X_{1},X_{2},\dots$ on ground sets of size $n_{1},n_{2},\dots$ such that the
following holds:

For every sequence of binary codes $\mathcal{C}_{1}^{(i)}$ on $[n_{i}]$ with
rate and distance uniformly bounded by $r_{1}$ and $(1/2-\varepsilon_{0})$
respectively, there exists a sequence of binary lifted codes
$\mathcal{C}_{k}^{(i)}=\operatorname{dsum}_{X(k)}(\varphi(\mathcal{C}_{1}^{(i)}))$
on a collection $X_{i}(k)$ with $\Delta(\mathcal{C}_{k}^{(i)})\geq
1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}$ where $\varphi$ is an explicit
linear projection and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time $n^{\varepsilon^{-O\left(1\right)}}\cdot f(n)$, where $f(n)$ is
the running time of a unique decoding algorithm of $\mathcal{C}_{1}$.

  * -

[Explicit Construction] The collection $X_{i}(k)$ is part of an explicit
$\gamma$-HDX $X_{i}(\leq d)$ where $k=O\left(\log(1/\varepsilon)\right)$,
$d=O\left((\log(1/\varepsilon))^{2}/\varepsilon\right)$, and
$\gamma=(\log(1/\varepsilon))^{-O\left(\log(1/\varepsilon)\right)}$.

  * -

[Rate] The rate $r_{k}^{(i)}$ of $\mathcal{C}_{k}^{(i)}$ satisfies
$r_{k}^{(i)}\geq
r_{1}\cdot\exp\left(-(\log(1/\varepsilon))^{O\left(\log(1/\varepsilon)\right)}\right)$.

  * -

[Linearity] If $\mathcal{C}_{1}^{(i)}$ is linear, then $\varphi$ is the
identity and
$\mathcal{C}_{k}^{(i)}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1}^{(i)})$ is
linear.

###### Proof.

Efficient list decoding and linearity follow directly from Theorem 7.1, and
the parameters of the explicit construction match the requirements of the
theorem. The only thing left to do is to calculate the rate. Since the lifting
$\operatorname{dsum}_{X_{i}(k)}$ needs to be a
$(2\varepsilon_{0},2\varepsilon)$-parity sampler to achieve the promised
distance, by Lemma 4.11 the rate $r_{k}^{(i)}$ of $\mathcal{C}_{k}^{(i)}$
satisfies

$r_{k}^{(i)}\geq
r_{1}\cdot\gamma^{O((\log(1/\varepsilon))^{4}/(\varepsilon^{2}\gamma))}$

Since $\gamma=(\log(1/\varepsilon))^{-O(\log(1/\varepsilon))}$, this reduces
to

$r_{k}^{(i)}\geq
r_{1}\cdot(\log(1/\varepsilon))^{-O((\log(1/\varepsilon))^{5}/(\varepsilon^{2}\cdot\gamma))}=r_{1}\cdot\exp(1/\gamma^{O(1)})=r_{1}\cdot\exp\left(-(\log(1/\varepsilon))^{O\left(\log(1/\varepsilon)\right)}\right).$

###  7.1 HDXs are Two-Step Tensorial

Theorem 7.3 proven in [AJT19] establishes that HDXs of appropriate expansion
parameter are tensorial objects for constant $L=O_{k,q,\mu}(1)$.

######  Theorem 7.3 (HDXs are Tensorial).

There exist some universal constants $c^{\prime}\geq 0$ and $C^{\prime}\geq 0$
satisfying the following: If $L\geq c^{\prime}\cdot(q^{k}\cdot
k^{5}/\mu^{4})$, $\operatorname{Supp}(\mathbf{Z}_{j})\leq q$ for all
$j\in[n]$, and $X$ is a $\gamma$-HDX for $\gamma\leq
C^{\prime}\cdot\mu^{4}/(k^{8+k}\cdot 2^{6k}\cdot q^{2k})$ and size $\geq k$,
then $X(k)$ endowed with a distribution $\Pi_{k}$ is $(\mu,L)$-tensorial.

The next result shows that HDXs are also two-step tensorial objects with the
same parameters as above.

######  Lemma 7.4 (HDXs are two-step tensorial).

There exist some universal constants $c^{\prime}\geq 0$ and $C^{\prime}\geq 0$
satisfying the following: If $L\geq c^{\prime}\cdot(q^{k}\cdot
k^{5}/\mu^{4})$, $\operatorname{Supp}(\mathbf{Z}_{j})\leq q$ for all
$j\in[n]$, and $X$ is a $\gamma$-HDX for $\gamma\leq
C^{\prime}\cdot\mu^{4}/(k^{8+k}\cdot 2^{6k}\cdot q^{2k})$ and size $\geq k$,
then $X(k)$ is $(\mu,L)$-two-step tensorial.

###### Proof.

Under our assumptions the $(\mu,L)$-tensorial property follows from Theorem
7.3 (this is the only place where the assumption on $\gamma$ is used), so we
only need to show

$\operatorname*{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}{\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}^{\prime}\mathbf{Z}_{\mathfrak{t}}^{\prime}\\}-\left\\{\mathbf{Z}_{\mathfrak{s}}^{\prime}\right\\}\left\\{\mathbf{Z}_{\mathfrak{t}}^{\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_{k}^{m}}{\operatorname*{\mathbb{E}}_{\sigma\sim\\{\mathbf{Z}_{S}\\}}{\operatorname*{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}{\mathchoice{{\mathrm{Var}}\left[\mathbf{Z}_{\mathfrak{s}}\mid\mathbf{Z}_{S}=\sigma\right]}{{\mathrm{Var}}[\mathbf{Z}_{\mathfrak{s}}\mid\mathbf{Z}_{S}=\sigma]}{{\mathrm{Var}}[\mathbf{Z}_{\mathfrak{s}}\mid\mathbf{Z}_{S}=\sigma]}{{\mathrm{Var}}[\mathbf{Z}_{\mathfrak{s}}\mid\mathbf{Z}_{S}=\sigma]}}}},$
(10)

and consider the error term

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

where
$D(S,\sigma)\coloneqq\mathchoice{\underset{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}{\mathbb{E}}\left[\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}\right]}{{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}[\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}]}{{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}[\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}]}{{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}[\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}\mid\mathbf{Z}_{S}=\sigma\\}-\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{S}=\sigma\\}\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\\}\right\rVert_{1}]}$.
If $\mu_{m}\geq\mu/2$, then

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

Let $G=(V=X(k),E)$ be the weighted graph where
$E=\\{\\{\mathfrak{s},\mathfrak{t}\\}\mid\mathfrak{s},\mathfrak{t}\in X(k)\\}$
and each edge $\\{\mathfrak{s},\mathfrak{t}\\}$ receives weight
$\Pi_{k}(\mathfrak{s})\cdot\Pi_{k}(\mathfrak{t})$. Local correlation
(expectation over the edges) on this graph $G$ is the same as to global
correlation (expectation over two independent copies of vertices). Then, we
obtain 181818See [AJT19] or [BRS11] for the details.

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

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

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

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

###  7.2 Instantiation to Linear Base Codes

First, we instantiate the list decoding framework to the seemingly simpler
case of binary _linear_ base codes in Lemma 7.5. As we show later, with a
simple observation we can essentially use the proof of Lemma 7.5 to obtain
Theorem 7.1 for general codes.

######  Lemma 7.5 (Direct sum lifting of linear biased codes).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There exist universal constants $c,C>0$
such that for any $\gamma$-HDX $X(\leq d)$ on ground set $X(1)=[n]$ and
$\Pi_{1}$ uniform, if

$\gamma\leq\log(1/\varepsilon)^{-C\cdot(\log(1/\varepsilon))}\quad\text{ and
}\quad d\geq c\cdot\frac{(\log(1/\varepsilon))^{2}}{\varepsilon},$

then the following holds:

For every binary $2\varepsilon_{0}$-biased linear code $\mathcal{C}_{1}$ on
$X(1)=[n]$, there exists a $2\varepsilon$-biased binary lifted linear code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ on $X(k)$ where
$k=O\left(\log(1/\varepsilon)\right)$ and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time

$n^{\varepsilon^{-O\left(1\right)}}\cdot f(n),$

where $f(n)$ is the running time of a unique decoding algorithm for
$\mathcal{C}_{1}$.

  * -

[Rate] The rate 191919For the rate computation, we assume that $X(k)$ can be
expressed as a multi-set such that the uniform distribution on it coincides
with $\Pi_{k}$, which is true in the case that $\Pi_{k}$ is $D$-flat. $r_{k}$
of $\mathcal{C}_{k}$ satisfies $r_{k}=r_{1}\cdot\left\lvert
X(1)\right\rvert/\left\lvert X(k)\right\rvert$ where $r_{1}$ is the relative
rate of $\mathcal{C}_{1}$.

  * -

[Linear] The lifted code $\mathcal{C}_{k}$ is linear.

###### Proof.

We show that under our assumption on the $\gamma$-HDX $X(\leq d)$ we obtain
sufficient robustness and tensorial parameters to apply Theorem 6.17. In this
application, we will rely on parity sampling for robustness. If
$\operatorname{dsum}_{X(k)}$ is a $(2\varepsilon_{0},2\varepsilon)$-parity
sampler, using the linearity of $\mathcal{C}_{1}$ we obtain a lifted code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ which is linear
and has bias $2\varepsilon$; thus the lifting is indeed
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust. If we want to fully rely on
parity sampling in Theorem 6.17, the lifting must be a
$(\beta_{0}=1/2+\varepsilon_{0},\beta=2\varepsilon)$-parity sampler, which is
more stringent than the first parity sampling requirement. 202020Recall that
this strengthening is used in our list decoding framework. To invoke Lemma
4.10 and obtain this $(\beta_{0},\beta)$-parity sampler, we need to choose a
parameter $\theta$ (where $0<\theta<(1-\beta_{0})/\beta_{0}$) and

$\displaystyle k\geq\log_{(1+\theta)\beta_{0}}(\beta/3),$ $\displaystyle
d\geq\max\left(\frac{3\cdot
k^{2}}{\beta},\frac{6}{\theta^{2}\beta_{0}^{2}\beta}\right),\text{ and}$
$\displaystyle\gamma=O\left(\frac{1}{d^{2}}\right).$

To get a $(\mu,L)$-tensorial HDX, Theorem 7.3 requires

$L\geq\frac{c^{\prime}\cdot 2^{k}\cdot k^{5}}{\mu^{4}}\quad\text{ and
}\quad\gamma\leq\frac{C^{\prime}\cdot\mu^{4}}{k^{8+k}\cdot 2^{8k}}.$

where we used that our alphabet is binary (i.e., $q=2$) and
$c^{\prime},C^{\prime}>0$ are constants. Finally, Theorem 6.17 requires
$\mu\leq\varepsilon^{8}/2^{22}$. The conceptual part of the proof is
essentially complete and we are left to compute parameters. Set
$\zeta_{0}=3/4+\varepsilon_{0}-\varepsilon_{0}^{2}$. We choose
$\theta=1/2-\varepsilon_{0}$ which makes $(1+\theta)\beta_{0}$ equal to
$\zeta_{0}$ (provided $\varepsilon_{0}<1/2$ we have $\zeta_{0}<1$). This
choice results in

$k\geq\lceil\log_{\zeta_{0}}(2\varepsilon/3)\rceil\quad\text{ and }\quad
d=O\left(\max\left(\frac{\log_{\zeta_{0}}(2\varepsilon/3)}{\varepsilon},\frac{1}{(1/4-\varepsilon_{0}^{2})^{4}\cdot\varepsilon}\right)\right).$

Combining the parity sampling and tensorial requirements and after some
simplification, the expansion $\gamma$ is constrained as

$\gamma\leq
C^{\prime\prime}\cdot\min\left(\frac{\varepsilon^{32}}{k^{8+k}\cdot
2^{8k}},\frac{\varepsilon^{2}}{k^{4}},\left(1/4-\varepsilon_{0}^{2}\right)^{4}\cdot\varepsilon^{2}\right),$

where $C^{\prime\prime}>0$ is a constant. We deduce that taking $\gamma$ as

$\gamma\leq
C^{\prime\prime}\cdot\frac{\left(1/4-\varepsilon_{0}^{2}\right)^{4}\cdot\varepsilon^{32}}{k^{8+k}\cdot
2^{8k}},$

is sufficient. Further simplifying the above bound gives

$\gamma=O\left(\frac{\left(1/4-\varepsilon_{0}^{2}\right)^{4}\cdot\varepsilon^{32}}{\left(\log_{\zeta_{0}}(2\varepsilon/3)\right)^{8+\log_{\zeta_{0}}(2\varepsilon/3)}\cdot\left(2\varepsilon/3\right)^{8/\log(\zeta_{0})}}\right).$

Now, we turn to the SOS-related parameter $L$ which is constrained to be

$L\geq c^{\prime\prime}\cdot\frac{2^{k}\cdot k^{5}}{\varepsilon^{32}},$

where $c^{\prime\prime}>0$. Note that in this case the exponent $O(L+k)$
appearing in the running time of Theorem 6.17 becomes $O(L)$. Similarly,
further simplification leads to

$L=O\left(\frac{\left(\log_{\zeta_{0}}(2\varepsilon/3)\right)^{5}\cdot\left(3/2\varepsilon\right)^{-1/\log(\zeta_{0})}}{\varepsilon^{32}}\right).$

Taking $\varepsilon_{0}$ to be a constant and simplifying yields the claimed
parameters.

###  7.3 Instantiation to General Base Codes

We can extend Lemma 7.5 to an arbitrary (not necessarily linear) binary base
code $\mathcal{C}_{1}$ with the natural caveat of no longer obtaining linear
lifted code $\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$.
However, even if $\mathcal{C}_{1}$ has small bias, it might not be the case
that the difference of any two codewords will have small bias, which is
required for list decoding. To this end we modify the code $\mathcal{C}_{1}$
by employing a projection $\varphi$ which converts a condition on the distance
of the code to a condition on the bias of the difference of any two codewords.

######  Claim 7.6.

If $\mathcal{C}_{1}$ is binary code on $[n]$ with relative distance $\delta$
and rate $r$, then there exists an explicit linear projection
$\varphi\colon\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}^{n}$ such that the
code $\mathcal{C}_{1}^{\prime}=\varphi(\mathcal{C}_{1})$ has relative distance
at least $\delta/2$ and rate $r$. Furthermore, for every
$z,z^{\prime}\in\mathcal{C}_{1}^{\prime}$ we have

$\operatorname{bias}(z-z^{\prime})\leq 1-\frac{\delta}{2}.$

###### Proof.

Take $\varphi$ to be the projector onto
$\mathbb{F}_{2}^{n-s}\oplus\\{0\\}^{s}$ where $s=\lfloor\delta n/2\rfloor$.
Then

$\mathcal{C}_{1}^{\prime}\coloneqq\varphi(\mathcal{C}_{1})=\\{(z_{1},\dots,z_{n-s},\underbrace{0,\dots,0}_{s})~{}|~{}(z_{1},\dots,z_{n})\in\mathcal{C}_{1}\\},$

and the claim readily follows.

With this modification in mind, we can now restate and prove Theorem 7.1.

######  Theorem 7.7 (Direct Sum Lifting on HDX (Restatement of Theorem 7.1)).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There exist universal constants $c,C>0$
such that for any $\gamma$-HDX $X(\leq d)$ on ground set $X(1)=[n]$ and
$\Pi_{1}$ uniform, if

$\gamma\leq(\log(1/\varepsilon))^{-C\cdot\log(1/\varepsilon)}\quad\text{ and
}\quad d\geq c\cdot\frac{(\log(1/\varepsilon))^{2}}{\varepsilon},$

then the following holds:

For every binary code $\mathcal{C}_{1}$ with $\Delta(\mathcal{C}_{1})\geq
1/2-\varepsilon_{0}$ on $X(1)=[n]$, there exists a binary lifted code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\varphi(\mathcal{C}_{1}))$ with
$\Delta(\mathcal{C}_{k})\geq 1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}$ on
$X(k)$ where $k=O\left(\log(1/\varepsilon)\right)$, $\varphi$ is an explicit
linear projection, and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time

$n^{\varepsilon^{-O\left(1\right)}}\cdot f(n),$

where $f(n)$ is the running time of a unique decoding algorithm for
$\mathcal{C}_{1}$.

  * -

[Rate] The rate $r_{k}$ of $\mathcal{C}_{k}$ satisfies
$r_{k}=r_{1}\cdot\left\lvert X(1)\right\rvert/\left\lvert X(k)\right\rvert$
where $r_{1}$ is the relative rate of $\mathcal{C}_{1}$.

  * -

[Linearity] If $\mathcal{C}_{1}$ is linear, then $\varphi$ is the identity and
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ is linear.

###### Proof.

By virtue of Lemma 7.5, it is enough to consider when $\mathcal{C}_{1}$ is not
linear. Note that in the proof of Lemma 7.5 the only assumption about
linearity of $\mathcal{C}_{1}$ we used to obtain
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robustness was that the sum of two
codewords is in the code and hence it has small bias. For a general code
$\mathcal{C}_{1}$ of constant distance $1/2-\varepsilon_{0}$, applying 7.6 we
obtain a new code $\mathcal{C}_{1}^{\prime}$ with this guarantee at the
expense of a distance $1/2$ times the original one. Naturally, in the current
proof we no longer obtain a linear lifted code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1}^{\prime})$.
Excluding the two previous remarks the proof of Theorem 7.1 is now the same as
the proof of Lemma 7.5.

##  8 List Decoding Direct Product Codes

###  8.1 Direct Product Codes

Having developed a decoding algorithm for direct sum, a promising strategy for
list decoding other lifted codes on expanding objects is reducing them to
instances of direct sum list decoding. One such reduction involves the direct
product lifting, which was first studied in the context of samplers by Alon et
al. in [ABN+92]. The direct product lifting collects the entries of a code on
each subset of size $\ell$.

######  Definition 8.1 (Direct Product Lifting).

Let $\mathcal{C}_{1}\subseteq{\mathbb{F}}_{2}^{n}$ be a base code on
$X(1)=[n]$. The direct product lifting of a word $z\in{\mathbb{F}}_{2}^{n}$ on
a collection $X(\ell)$ is
$\operatorname{dprod}_{X(\ell)}(z)=(x_{\mathfrak{t}})_{\mathfrak{t}\in
X(\ell)}$, where $x_{\mathfrak{t}}=(z_{i})_{i\in\mathfrak{t}}$. The direct
product lifting of the entire code is
$\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})=\\{\operatorname{dprod}_{X(\ell)}(z)\mid
z\in\mathcal{C}_{1}\\}$, which is a code of length $|X(\ell)|$ over the
alphabet ${\mathbb{F}}_{2}^{\ell}$.

If $X$ is a HDX, its sampling properties ensure that the direct product
lifting has very high distance. It follows from the definition that if the
bipartite graph between $X(1)$ and $X(k)$ is an $(\eta,\delta)$-sampler and
the code $\mathcal{C}_{1}$ has minimum distance $\eta$, then the direct
product lifting $\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$ has minimum
distance at least $(1-\delta)$. Recalling from 4.8 that the bipartite graph
between two levels of a HDX can be a sampler with arbitrarily small parameters
if the expansion is good enough, we can reasonably hope to list decode the
direct product lifting on a HDX up to a distance close to 1. In fact, Dinur et
al. [DHK+19] provided a list decoding algorithm accomplishing exactly that. We
offer a very different approach to the same list decoding problem.

###  8.2 Direct Product List Decoding

We will reduce direct product decoding on $X(\ell)$ to direct sum decoding on
$X(k)$, where $k\approx\ell/2$. This requires converting a received word
$\tilde{x}\in({\mathbb{F}}_{2}^{\ell})^{X(\ell)}$ to a word
$\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ that we will decode using the direct sum
algorithm. If we knew that
$\tilde{x}=\operatorname{dprod}_{X(\ell)}(\tilde{z})$ for some
$\tilde{z}\in{\mathbb{F}}_{2}^{X(1)}$, we would do so by simply taking
$\tilde{y}_{\mathfrak{s}}=\sum_{i\in\mathfrak{s}}\tilde{z}_{i}$ to be the
direct sum lifting on each edge $\mathfrak{s}$; that is,
$\tilde{y}=\operatorname{dsum}_{X(k)}(\tilde{z})$.

Unfortunately, performing list decoding also involves dealing with words
$\tilde{x}$ that might not have arisen from the direct product lifting. To
construct a corrupted instance of direct sum $\tilde{y}$ from $\tilde{x}$, we
need to assign values to each face $\mathfrak{s}\in X(k)$ based only on the
information we have on the faces $X(\ell)$, as there is no word on the ground
set to refer to. Since different faces $\mathfrak{t},\mathfrak{t}^{\prime}\in
X(\ell)$ containing $\mathfrak{s}$ might not agree on $\mathfrak{s}$, there
could be ambiguity as to what value to assign for the sum on $\mathfrak{s}$.

This is where the $D$-flatness of the distribution $\Pi_{\ell}$ (which holds
for the $\gamma$-HDX construction described in Lemma 4.5) comes in. Recall
that to obtain codewords in $\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$
without weights on their entries, we duplicate each face $\mathfrak{t}\in
X(\ell)$ at most $D$ times to make the distribution $\Pi_{\ell}$ uniform. To
perform the same kind of duplication on $X(k)$ that makes $\Pi_{k}$ uniform,
note that each face $\mathfrak{s}\in X(k)$ has $\Pi_{k}(\mathfrak{s})$
proportional to $\left\lvert\\{\mathfrak{t}\in
X(\ell)\mid\mathfrak{t}\supset\mathfrak{s}\\}\right\rvert$ (where $X(\ell)$ is
thought of as a multiset), so we will create one copy of $\mathfrak{s}$ for
each $\mathfrak{t}$ containing it. Thus we can assign a unique
$\mathfrak{t}\supset\mathfrak{s}$ to each copy. By downward closure, the
distribution on $X(\ell)$ obtained by choosing $\mathfrak{s}$ uniformly from
the multiset $X(k)$ and then selecting its associated face $\mathfrak{t}$ will
be uniform, just like $\Pi_{\ell}$. With this careful duplication process, we
are ready to define the function $\rho_{k}$ that takes a corrupted direct
product word $\tilde{x}$ to a corrupted direct sum word $\tilde{y}$.

######  Definition 8.2 (Reduction Function).

Let $k<\ell$ and $X$ be a HDX where the distribution $\Pi_{\ell}$ is $D$-flat.
Duplicate faces in $X(k)$ so that $\Pi_{k}$ is uniform, and assign a face
$\mathfrak{t}_{\mathfrak{s}}\in X(\ell)$ to each $\mathfrak{s}\in X(k)$ (after
duplication) such that $\mathfrak{t}_{\mathfrak{s}}$ is distributed according
to $\Pi_{\ell}$ when $\mathfrak{s}$ is selected uniformly from $X(k)$. The
function
$\rho_{k}:({\mathbb{F}}_{2}^{\ell})^{X(\ell)}\rightarrow{\mathbb{F}}_{2}^{X(k)}$
is defined as

$(\rho_{k}(\tilde{x}))_{\mathfrak{s}}=\sum_{i\in\mathfrak{s}}(\tilde{x}_{\mathfrak{t}_{\mathfrak{s}}})_{i}.$

The reduction function $\rho_{k}$ resolves the ambiguity of which face
$\mathfrak{t}\supset\mathfrak{s}$ to sample the sum from by assigning a
different face to each copy of $\mathfrak{s}$ in a manner compatible with the
distribution $\Pi_{\ell}$. Observe that if
$\tilde{x}=\operatorname{dprod}_{X(\ell)}(\tilde{z})$ for some
$\tilde{z}\in{\mathbb{F}}_{2}^{X(1)}$, then
$\rho_{k}(\tilde{x})=\operatorname{dsum}_{X(k)}(\tilde{z})$.

The following lemma shows that performing this reduction from direct product
to direct sum maintains agreement between words. It essentially says that if a
received word $\tilde{x}$ exhibits some agreement with
$x\in\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$, then there is a $k$ for
which $\rho_{k}(\tilde{x})$ and $\rho_{k}(x)$ have agreement larger than 1/2.

######  Lemma 8.3 (Product-to-sum agreement).

Fix $\varepsilon>0$ and $C^{\prime}>2$. Let $z\in\mathcal{C}_{1}$,
$x=\operatorname{dprod}_{X(\ell)}(z)$, and
$\tilde{x}\in({\mathbb{F}}_{2}^{\ell})^{X(\ell)}$. If $\Delta(x,\tilde{x})\leq
1-\varepsilon$, then there exists a $k$ satisfying

$\left\lvert
k-\ell/2\right\rvert<\frac{1}{2}\sqrt{C^{\prime}\ell\log(1/\varepsilon)}$

such that

$\Delta(y,\tilde{y})\leq 1/2-\varepsilon/2+\varepsilon^{C^{\prime}/2},$

where $y=\rho_{k}(x)$ and $\tilde{y}=\rho_{k}(\tilde{x})$ are words in
${\mathbb{F}}_{2}^{X(k)}$.

###### Proof.

For $t\in X(\ell)$ and $\mathfrak{s}\subseteq\mathfrak{t}$, define the
function
$\chi_{\mathfrak{s},\mathfrak{t}}:{\mathbb{F}}_{2}^{\mathfrak{t}}\rightarrow\\{-1,1\\}$
by

$\chi_{\mathfrak{s},\mathfrak{t}}(w)=\prod_{i\in\mathfrak{s}}(-1)^{w_{i}}.$

For each face $\mathfrak{t}\in X(\ell)$, consider the expectation
${\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t}}[\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})]$,
where $\mathfrak{s}$ is a subset of $\mathfrak{t}$ of any size chosen
uniformly. If $x_{\mathfrak{t}}=\tilde{x}_{\mathfrak{t}}$, which happens for
at least $\varepsilon$ fraction of faces $\mathfrak{t}$, the expression in the
expectation is always 1. Otherwise, this expectation is zero, so taking the
expectation over the faces yields

${\mathbb{E}}_{\mathfrak{t}\sim\Pi_{\ell}}{\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t}}[\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})]=\operatorname*{\mathbb{P}}_{t\sim\Pi_{\ell}}[x_{\mathfrak{t}}=\tilde{x}_{\mathfrak{t}}]\geq\varepsilon.$

We would like to restrict to a fixed size of faces $\mathfrak{s}$ for which
this inequality holds; as this will be the size of the direct sum faces, we
need to make sure it’s large enough to give us the expansion required for
decoding later. Using a Chernoff bound (A.2 with
$a=\sqrt{C^{\prime}\ell\log(1/\varepsilon)}$), we see that the size of the
faces is highly concentrated around $\ell/2$:

$\operatorname*{\mathbb{P}}_{\mathfrak{s}\subseteq\mathfrak{t}}\left[\left\lvert\left\lvert\mathfrak{s}\right\rvert-\frac{\ell}{2}\right\rvert\geq\frac{1}{2}\sqrt{C^{\prime}\ell\log(1/\varepsilon)}\right]\leq
2e^{-C^{\prime}\log(1/\varepsilon)/2}\leq 2\varepsilon^{C^{\prime}/2}.$

Let $I$ be the interval

$I=\left(\frac{\ell}{2}-\frac{1}{2}\sqrt{C^{\prime}\ell\log(1/\varepsilon)},\frac{\ell}{2}+\frac{1}{2}\sqrt{C^{\prime}\ell\log(1/\varepsilon)}\right).$

The expectation inequality becomes

$\displaystyle\varepsilon$
$\displaystyle\leq{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{\ell}}[{\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t}}[\mathbb{1}_{\left\lvert\mathfrak{s}\right\rvert\in
I}\cdot\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})]+{\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t}}[\mathbb{1}_{\left\lvert\mathfrak{s}\right\rvert\notin
I}\cdot\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})]]$
$\displaystyle\leq{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{\ell}}{\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t},\left\lvert\mathfrak{s}\right\rvert\in
I}[\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})]+2\varepsilon^{C^{\prime}/2}.$

Thus there exists a $k\in I$ such that

$\varepsilon-2\varepsilon^{C^{\prime}/2}\leq{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{\ell}}{\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t},\left\lvert\mathfrak{s}\right\rvert=k}[\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})].$

Choosing a face $\mathfrak{t}$ and then a uniformly random
$\mathfrak{s}\subseteq\mathfrak{t}$ of size $k$ results in choosing
$\mathfrak{s}$ according to $\Pi_{k}$. Moreover, the edge
$\mathfrak{t}_{\mathfrak{s}}$ containing $\mathfrak{s}$ from Definition 8.2 is
distributed according to $\Pi_{\ell}$. Bearing in mind the definitions of
$y_{\mathfrak{s}}$ and $\tilde{y}_{\mathfrak{s}}$, we have

$\displaystyle\varepsilon-2\varepsilon^{C^{\prime}/2}$
$\displaystyle\leq{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{\ell}}{\mathbb{E}}_{\mathfrak{s}\subseteq\mathfrak{t},\left\lvert\mathfrak{s}\right\rvert=k}[\chi_{\mathfrak{s},\mathfrak{t}}(x_{\mathfrak{t}}-\tilde{x}_{\mathfrak{t}})]$
$\displaystyle={\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[\chi_{\mathfrak{s},\mathfrak{t}_{\mathfrak{s}}}(x_{\mathfrak{t}_{\mathfrak{s}}}-\tilde{x}_{\mathfrak{t}_{\mathfrak{s}}})]$
$\displaystyle={\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[(-1)^{(\rho_{k}(x))_{\mathfrak{s}}-(\rho_{k}(\tilde{x}))_{\mathfrak{s}}}]$
$\displaystyle=\operatorname{bias}(y-\tilde{y})$

which translates to a Hamming distance of $\Delta(y,\tilde{y})\leq
1/2-\varepsilon/2+\varepsilon^{C^{\prime}/2}$.

With Lemma 8.3 in hand to reduce a direct product list decoding instance to a
direct sum list decoding instance, we can decode by using a direct sum list
decoding algorithm as a black box.

######  Algorithm 8.4 (Direct Product List Decoding Algorithm).

Input A word $\tilde{x}\in({\mathbb{F}}_{2}^{\ell})^{X(\ell)}$ with distance
at most $(1-\varepsilon)$ from
$\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$ Output The list
$\mathcal{L}^{\prime}=\\{z\in{\mathbb{F}}_{2}^{n}\mid\Delta(\operatorname{dprod}_{X(\ell)}(z),\tilde{x})\leq
1-\varepsilon\\}$ 1. Let $I$ be the interval
$\left(\ell/2-\sqrt{C^{\prime}\ell\log(1/\varepsilon)}/2,\ell/2+\sqrt{C^{\prime}\ell\log(1/\varepsilon)}/2\right)$.
2. For each integer $k\in I$, run the direct sum list decoding algorithm on
the input $\tilde{y}=\rho_{k}(\tilde{x})\in{\mathbb{F}}_{2}^{X(k)}$ to obtain
a coupled list $\mathcal{L}_{k}$ of all pairs $(z,y)$ with
$\Delta(y,\tilde{y})\leq 1/2-\varepsilon/2+\varepsilon^{C^{\prime}/2}$. 3. Let
$\mathcal{L}=\cup_{k\in
I}\\{z\in\mathcal{C}_{1}\mid(z,y)\in\mathcal{L}_{k}\\}$. 4. Let
$\mathcal{L}^{\prime}=\\{z\in\mathcal{L}\mid\Delta(\operatorname{dprod}_{X(\ell)}(z),\tilde{x})\leq
1-\varepsilon\\}$. 5. Output $\mathcal{L}^{\prime}$.

######  Theorem 8.5 (Product-to-sum Reduction).

Let $\varepsilon>0$ and $C^{\prime}>2$. Let
$\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$ be the direct product
lifting of a base code $\mathcal{C}_{1}$ on a simplicial complex $X$. If the
direct sum lifting $\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ is list
decodable up to distance
$\left(1/2-\varepsilon/2+\varepsilon^{C^{\prime}/2}\right)$ in time
$\tilde{f}(n)$ for all $k$ satisfying $\left\lvert
k-\ell/2\right\rvert<\sqrt{C^{\prime}\ell\log(1/\varepsilon)}/2$, then 8.4
list decodes $\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$ up to distance
$(1-\varepsilon)$ in running time

$\sqrt{C^{\prime}\ell\log(1/\varepsilon)}\tilde{f}(n)+|X(\ell)||\mathcal{L}|.$

###### Proof.

Let $\tilde{x}\in({\mathbb{F}}_{2}^{\ell})^{X(\ell)}$ be a received word and
let $z\in\mathcal{C}_{1}$ satisfy
$\Delta(\operatorname{dprod}_{X(\ell)}(z),\tilde{x})\leq 1-\varepsilon$. By
Lemma 8.3, there exists a $k\in I$ such that $\Delta(y,\tilde{y})\leq
1/2-\varepsilon/2+\varepsilon^{C^{\prime}/2}$. Thanks to this distance
guarantee, the pair $(z,y)$ will appear on the list $\mathcal{L}_{k}$ when the
direct sum list decoding algorithm is run for this $k$. Then $z$ will be on
the combined list $\mathcal{L}$ and the trimmed list $\mathcal{L}^{\prime}$,
with the trimming ensuring that no elements of $\mathcal{C}_{1}$ appear on
this list beyond those with the promised distance. The set
$\\{\operatorname{dprod}_{X(\ell)}(z)\mid z\in\mathcal{L}^{\prime}\\}$ thus
contains all words in $\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$ with
distance at most $(1-\varepsilon)$ from $\tilde{x}$.

To obtain the promised the running time, note that 8.4 runs the direct sum
list decoding algorithm $\sqrt{C^{\prime}\ell\log(1/\varepsilon)}$ times and
then computes the direct product lifting of each element of $\mathcal{L}$ in
the trimming step.

Combining the parameters in the reduction with those required for our direct
sum list decoding algorithm, we obtain the following. Note that for very small
values of $\varepsilon$, we can choose the constant $C^{\prime}$ to be close
to 2, and we will be list decoding the direct sum code up to distance
$1/2-\sqrt{\beta}\approx 1/2-\varepsilon/4$.

######  Corollary 8.6 (Direct Product List Decoding).

Let $\varepsilon_{0}<1/2$ be a constant, and let $\varepsilon>0$,
$C^{\prime}\geq 2+4/\log(1/\varepsilon)$, and
$\beta=(\varepsilon/2-\varepsilon^{C^{\prime}/2})^{2}$. There exist universal
constants $c,C>0$ such that for any $\gamma$-HDX $X(\leq d)$ on ground set
$[n]$ and $\Pi_{1}$ uniform, if

$\gamma\leq\log(1/\beta)^{-C\log(1/\beta)}\quad\text{ and }\quad d\geq
c\cdot\frac{\log(1/\beta)^{2}}{\beta},$

then the following holds:

For every binary code $\mathcal{C}_{1}$ with $\Delta(\mathcal{C}_{1})\geq
1/2-\varepsilon_{0}$ on $X(1)=[n]$, there exists a lifted code
$\mathcal{C}_{\ell}=\operatorname{dprod}_{X(\ell)}(\varphi(\mathcal{C}_{1}))$
on $C_{\ell}$ where $\ell=O(\log(1/\beta))$, $\varphi$ is an explicit linear
projection, and

  * -

[Efficient List Decoding] If $\tilde{x}$ is $(1-\varepsilon)$-close to
$\mathcal{C}_{\ell}$, then we can compute the list of all codewords of
$\mathcal{C}_{\ell}$ that are $(1-\varepsilon)$-close to $\tilde{x}$ in time
$n^{\varepsilon^{-O(1)}}\cdot f(n)$, where $f(n)$ is the running time of the
unique decoding algorithm for $\mathcal{C}_{1}$.

  * -

[Rate] The rate $r_{\ell}$ of $\mathcal{C}_{\ell}$ satisfies
$r_{\ell}=r_{1}\cdot\left\lvert X(1)\right\rvert/(\ell\left\lvert
X(\ell)\right\rvert)$, where $r_{1}$ is the relative rate of
$\mathcal{C}_{1}$.

  * -

[Linearity] If $\mathcal{C}_{1}$ is linear, then $\varphi$ is the identity and
$\mathcal{C}_{\ell}$ is linear.

###### Proof.

Let $k=\ell/2-\sqrt{C^{\prime}\ell\log(1/\varepsilon)}/2$. The choice of
parameters ensures that $\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ is list
decodable up to distance
$1/2-\sqrt{\beta}=1/2-\varepsilon/2+\varepsilon^{C^{\prime}/2}$ in running
time $g(n)=n^{\beta^{-O(1)}}f(n)$ by Theorem 7.1 (noting that the bound on
$C^{\prime}$ implies $\beta\geq\varepsilon^{2}/16$). Since increasing $k$
increases the list decoding radius of the direct sum lifting, this holds for
any value of $k$ with $\left\lvert
k-\ell/2\right\rvert\leq\sqrt{C^{\prime}\ell\log(1/\varepsilon)}/2$. By
Theorem 8.5, the direct product lifting
$\operatorname{dprod}_{X(\ell)}(\mathcal{C}_{1})$ is list decodable up to
distance $(1-\varepsilon)$ in running time

$\sqrt{C^{\prime}\ell\log(1/\varepsilon)}n^{\beta^{-O(1)}}f(n)+\left\lvert
X(\ell)\right\rvert\left\lvert\mathcal{L}\right\rvert.$

The HDX has $\left\lvert
X(\ell)\right\rvert\leq\binom{n}{\ell}=n^{O(\log(1/\beta))}$, and the list
size $\left\lvert\mathcal{L}\right\rvert$ is bounded by the sum of the sizes
of the lists $\mathcal{L}_{k}$ obtained from each direct sum decoding. Each of
these lists has $\left\lvert\mathcal{L}_{k}\right\rvert\leq 1/(2\beta)$ by the
Johnson bound (see Remark 6.14) and the number of lists is constant with
respect to $n$, so the overall running time is dominated by the first term,
$n^{\beta^{-O(1)}}f(n)=n^{\varepsilon^{-O(1)}}f(n)$.

The rate and linearity guarantees follow in the same manner as they do in
Theorem 7.1, where the rate calculation requires a slight modification for
dealing with the increased alphabet size and $\varphi$ is the projection from
7.6.

Using Corollary 8.6 with HDXs obtained from Ramanujan complexes as in
Corollary 7.2, we can perform list decoding with an explicit construction up
to distance $(1-\varepsilon)$ with HDX parameters
$d=O(\log(1/\varepsilon)^{2}/\varepsilon^{2})$ and
$\gamma=(\log(1/\varepsilon))^{-O(\log(1/\varepsilon))}$. The direct product
list decoding algorithm of Dinur et al. [DHK+19] is based on a more general
expanding object known as a double sampler. As the only known double sampler
construction is based on a HDX, we can compare our parameters to their HDX
requirements of $d=O(\exp(1/\varepsilon))$ and
$\gamma=O(\exp(-1/\varepsilon))$.

##  9 Instantiation II: Direct Sum on Expander Walks

We instantiate the list decoding framework to the direct sum lifting where the
sum is taken over the collection $X(k)$ of length $k$ walks of a sufficiently
expanding graph $G$. To stress the different nature of this collection and its
dependence on $G$ we equivalently denote $X(k)$ by $W_{G}(k)$ and endow it
with a natural measure in Definition 9.1.

######  Definition 9.1 (Walk Collection).

Let $G=(V,E,w)$ be a weighted graph with weight distribution $w\colon
E\rightarrow[0,1]$. For $k\in\mathbb{N}^{+}$, we denote by $W_{G}(k)$ the
collection of all walks of length $k$ in $G$, i.e.,

$W_{G}(k)\coloneqq\\{w=(w_{1},\dots,w_{k})~{}|~{}w\textup{ is a walk of length
$k$ in $G$}\\}.$

We endow $W_{G}(k)$ with the distribution $\Pi_{k}$ arising from taking a
random vertex $w_{1}$ according to the stationary distribution on $V$ and then
taking $k-1$ steps according to the normalized random walk operator of $G$.

One simple difference with respect to the HDX case is that now we are working
with a collection of (ordered) tuples instead of subsets. The Propagation
Rounding 6.5 remains the same, but we need to establish the tensorial
properties of $W_{G}(k)$ which is done in Section 9.1.

The main result of this section follows.

######  Theorem 9.2 (Direct Sum Lifting on Expander Walks).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There exists a universal constant $C>0$
such that for any $d$-regular $\gamma$-two-sided expander graph $G$ on ground
set $W_{G}(1)=[n]$, if $\gamma\leq\varepsilon^{C}$, then the following holds:

For every binary code $\mathcal{C}_{1}$ with $\Delta(\mathcal{C}_{1})\geq
1/2-\varepsilon_{0}$ on $W_{G}(1)=[n]$, there exists a binary lifted code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\varphi(\mathcal{C}_{1}))$ with
$\Delta(\mathcal{C}_{k})\geq 1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}$ on
$W_{G}(k)$ where $k=O\left(\log(1/\varepsilon)\right)$, $\varphi$ is an
explicit linear projection, and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time

$n^{\varepsilon^{-O\left(1\right)}}\cdot f(n),$

where $f(n)$ is the running time of a unique decoding algorithm for
$\mathcal{C}_{1}$.

  * -

[Rate] The rate $r_{k}$ of $\mathcal{C}_{k}$ satisfies $r_{k}=r_{1}/d^{k-1}$
where $r_{1}$ is the relative rate of $\mathcal{C}_{1}$.

  * -

[Linearity] If $\mathcal{C}_{1}$ is linear, then $\varphi$ is the identity and
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ is linear.

In particular, we apply Theorem 9.2 to the explicit family of Ramanujan
expanders of Lubotzky et al. from Theorem 9.3.

######  Theorem 9.3 (Lubotzky-Phillips-Sarnak abridged [LPS88]).

Let $p\equiv 1\pmod{4}$ be a prime. Then there exists an explicit infinite
family of $(p+1)$-regular Ramanujan graphs $G_{1},G_{2},\dots$ on
$n_{1}<n_{2}<\cdots$ vertices, i.e., $\sigma_{2}(G_{i})\leq
2\cdot\sqrt{p}/(p+1)$.

In order to construct Ramanujan expanders with arbitrarily good expansion, we
will use the following lemma for finding primes.

######  Lemma 9.4 (From [TS17]).

For every $\alpha>0$ and sufficiently large $n$, there exists an algorithm
that given $a$ and $m$ relatively prime, runs in time ${\mathrm{poly}}(n)$ and
outputs a prime number $p$ with $p\equiv a\pmod{m}$ in the interval
$[(1-\alpha)n,n]$.

This results in Corollary 9.5.

######  Corollary 9.5.

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There is an infinite sequence of explict
Ramanujan expanders $G_{1},G_{2},\dots$ on ground sets of size
$n_{1}<n_{2}<\cdots$ such that the following holds:

For every sequence of binary codes $\mathcal{C}_{1}^{(i)}$ on $[n_{i}]$ with
rate and distance uniformly bounded by $r_{1}^{(i)}$ and
$(1/2-\varepsilon_{0})$ respectively, there exists a sequence of binary lifted
codes
$\mathcal{C}_{k}^{(i)}=\operatorname{dsum}_{X(k)}(\varphi(\mathcal{C}_{1}^{(i)}))$
on a collection $X_{i}(k)$ with distance
$\left(1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}\right)$ where $\varphi$
is an explicit linear projection and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time $n^{\varepsilon^{-O\left(1\right)}}\cdot f(n)$, where $f(n)$ is
the running time of a unique decoding algorithm of $\mathcal{C}_{1}$.

  * -

[Explicit Construction] The collection $W_{G_{i}}(k)$ is obtained from length
$k$ walks on a Ramanujan $d$-regular expander $G_{i}$ where
$k=O\left(\log(1/\varepsilon)\right)$, $d=8\cdot\varepsilon^{-O(1)}$ and
$\gamma=\varepsilon^{O(1)}$.

  * -

[Rate] The rate $r_{k}^{(i)}$ of $\mathcal{C}_{k}^{(i)}$ satisfies
$r_{k}^{(i)}\geq r_{1}^{(i)}\cdot\varepsilon^{O(\log(1/\varepsilon))}$.

  * -

[Linearity] If $\mathcal{C}_{1}^{(i)}$ is linear, then $\varphi$ is the
identity and
$\mathcal{C}_{k}^{(i)}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1}^{(i)})$ is
linear.

###### Proof.

Using Lemma 9.4 with $a=1$ and $m=4$, we see that given $n,\alpha$, a prime
$p$ such that $p\equiv 1\pmod{4}$ may be found in the interval
$[(1-\alpha)n,n]$ for large enough $n$. For Ramanujan expanders, the condition
that $\gamma\leq\varepsilon^{C}$ translates to $p\geq
4\cdot\varepsilon^{-2C}$. Choose $\alpha=1/2$ and $n>8\cdot\varepsilon^{-2C}$
so that we find a prime greater than $4\cdot\varepsilon^{-2C}$, but at most
$8\cdot\varepsilon^{-2C}$.

Based on this prime, we use the above Theorem 9.3 to get a family of Ramanujan
graphs $G_{1},G_{2},\dots$ with $n_{1}<n_{2}<\cdots$ vertices, such that the
degree is bounded by $8\varepsilon^{-2C}$. Using the parameters of this family
in Theorem 9.2, we obtain the desired claims.

###  9.1 Expander Walks are Two-Step Tensorial

To apply the list decoding framework we need to establish the tensorial
parameters of expander walks $W_{G}(k)$ for a $\gamma$-two-sided expander
graph $G$. Although the tensorial property is precisely what the abstract list
decoding framework uses, when faced with a concrete object such as $W_{G}(k)$
it will be easier to prove that it satisfies a splittable property defined in
[AJT19] for complexes which implies the tensorial property. In turn, this
splittable property is defined in terms of some natural operators denoted Swap
operators whose definition is recalled in Section 9.1.2 in a manner tailored
to the present case $X(k)=W_{G}(k)$. Then, in Section 9.1.3, we formally
define the splittable property and show that the expansion of the Swap
operator is controlled by the expansion parameter $\gamma$ of $G$ allowing us
to deduce the splittable parameters of $W_{G}(k)$. Finally, in Section 9.1.4,
we show how $W_{G}(k)$ being splittable gives the tensorial parameters. Some
results are quite similar to the hypergraph case in [AJT19] (which built on
[BRS11]). The key contribution in this new case of $W_{G}(k)$ is observing the
existence of these new Swap operators along with their expansion properties.

####  9.1.1 Emergence of Swap Operators

To motivate the study of Swap operators on $W_{G}(k)$, we show how they
naturally emerge from the study of $k$-CSPs. The treatment is quite similar to
the hypergraph case developed in [AJT19], but this will give us the
opportunity to formalize the details that are specific to $W_{G}(k)$. Suppose
that we solve a $k$-CSP instance as defined in Section 2.4 whose constraints
were placed on the tuples corresponding to walks in $W_{G}(k)$. The result is
a local PSD ensemble $\\{\mathbf{Z}\\}$ which can then be fed to the
Propagation Rounding 6.5. It is easy to show that the tensorial condition of
Eq. 12 (below) is sufficient to guarantee an approximation to this $k$-CSP on
$W_{G}(k)$ within $\mu$ additive error. The precise parameters are given in
Section 9.1.5. For now, we take this observation for granted and use it to
show how the Swap operators emerge in obtaining the inequality

$\operatorname*{\mathbb{E}}_{\Omega}\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\left\\{\mathbf{Z}^{\prime}_{w_{1}}\right\\}\cdots\left\\{\mathbf{Z}^{\prime}_{w_{k}}\right\\}\right\rVert_{1}}\leq\mu$
(12)

present in the definition of tensoriality.

The following piece of notation will be convenient when referring to sub-walks
of a given walk.

######  Definition 9.6 (Sub-Walk).

Given $1\leq i\leq j\leq k$ and $w=(w_{1},\dots,w_{k})\in W_{G}(k)$, we define
the sub-walk $w(i,j)$ from $w_{i}$ to $w_{j}$ as

$w(i,j)\coloneqq(w_{i},w_{i+1},\dots,w_{j}).$

We will need the following simple observation about marginal distributions of
$\Pi_{k}$ on sub-walks.

######  Claim 9.7 (Marginals of the walk distribution).

Let $k\in\mathbb{N}^{+}$ and $1\leq i\leq j\leq k$. Then sampling
$w\sim\Pi_{k}$ in $W_{G}(k)$ and taking $w(i,j)$ induces the distribution
$\Pi_{j-i+1}$ on $W_{G}(j-i+1)$.

###### Proof.

Let $w=(w_{1},\dots,w_{i},\dots,w_{j},\dots,w_{k})\sim\Pi_{k}$. Since
$w_{1}\sim\Pi_{1}$ where $\Pi_{1}$ is the stationary measure of $G$ and
$w_{2},\dots,w_{i}$ are obtained by $(i-1)$ successive steps of a random walk
on $G$, the marginal distribution on $w_{i}$ is again the stationary measure
$\Pi_{1}$. Then by taking $(j-i)$ successive random walk steps from $w_{i}$ on
$G$, we obtain a walk $(w_{i},\dots,w_{j})$ distributed according to
$\Pi_{j-i+1}$.

We also need the notion of a splitting tree as follows.

######  Definition 9.8 (Splitting Tree [AJT19]).

We say that a binary tree $\mathcal{T}$ is a $k$-splitting tree if it has
exactly $k$ leaves and

  * -

the root of $\mathcal{T}$ is labeled with $k$ and all other vertices are
labeled with positive integers,

  * -

the leaves are labeled with $1$, and

  * -

each non-leaf vertex satisfies the property that its label is the sum of the
labels of its two children.

The Swap operators arise naturally from the following triangle inequality
where the quantity $\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\prod_{i=1}^{k}\left\\{\mathbf{Z}^{\prime}_{w(i)}\right\\}\right\rVert_{1}}$
is upper bounded by a sum of terms of the form

$\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k_{1}+k_{2})}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\left\\{\mathbf{Z}^{\prime}_{w(1,k_{1})}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}\right\rVert_{1}}.$

We view the above expectation as taking place over the edges
$W_{G}(k_{1}+k_{2})$ of a bipartite graph on vertex bipartition
$(W_{G}(k_{1}),W_{G}(k_{2}))$. This graph gives rise to a Swap operator which
we formally define later in Section 9.1.2. The following claim shows how a
splitting tree defines all terms (and hence also their corresponding graphs
and operators) that can appear in this upper bound.

######  Claim 9.9 (Triangle inequality).

Let $k\in\mathbb{N}^{+}$ and $\mathcal{T}$ be a $k$-splitting tree. Then

$\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\prod_{i=1}^{k}\left\\{\mathbf{Z}^{\prime}_{w(i)}\right\\}\right\rVert_{1}}\leq\sum_{(k_{1},k_{2})}\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k_{1}+k_{2})}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\left\\{\mathbf{Z}^{\prime}_{w(1,k_{1})}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}\right\rVert_{1}},$

where the sum $\sum_{(k_{1},k_{2})}$ is taken over all pairs of labels of the
two children of each internal node of $\mathcal{T}$.

###### Proof.

We prove the claim by induction on $k$. Let $(k_{1},k_{2})$ be the labels of
the children of the root of the splitting tree $\mathcal{T}$. Suppose
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ are the corresponding splitting trees
rooted at these children with labels $k_{1}$ and $k_{2}$, respectively. By
this choice, we have $k=k_{1}+k_{2}$. Applying the triangle inequality yields

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\prod_{i=1}^{k}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\right\rVert_{1}}\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\left\\{\mathbf{Z}^{\prime}_{w(1,k_{1})}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}\right\rVert_{1}}+$
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\left\\{\mathbf{Z}^{\prime}_{w(1,k_{1})}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}-\prod_{i=1}^{k_{1}}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}\right\rVert_{1}}+$
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\prod_{i=1}^{k_{1}}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}-\prod_{i=1}^{k}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\right\rVert_{1}}.$

Using the marginalization given by 9.7 on the second and third terms and
simplifying, we get

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\prod_{i=1}^{k}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\right\rVert_{1}}\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\left\\{\mathbf{Z}^{\prime}_{w(1,k_{1})}\right\\}\left\\{\mathbf{Z}^{\prime}_{w(k_{1}+1,k_{2})}\right\\}\right\rVert_{1}}+$
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k_{1})}{\left\lVert\left\\{\mathbf{Z}^{\prime}_{w}\right\\}-\prod_{i=1}^{k_{1}}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\right\rVert_{1}}+\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k_{2})}{\left\lVert\left\\{\mathbf{Z}^{\prime}_{w}\right\\}-\prod_{i=1}^{k_{2}}\left\\{\mathbf{Z}^{\prime}_{w_{i}}\right\\}\right\rVert_{1}}.$

Applying the induction hypothesis to the second term with tree
$\mathcal{T}_{1}$ and to the third term with tree $\mathcal{T}_{2}$ finishes
the proof.

####  9.1.2 Swap Operators Arising from Expander Walks

We define the Swap operator associated to walks on a given graph $G$ as
follows.

######  Definition 9.10 (Graph Walk Swap Operator).

Let $G=(V,E,w)$ be a weighted graph. Let $k_{1},k_{2}\in\mathbb{N}^{+}$ be
such that $k=k_{1}+k_{2}$. We define the graph walk Swap operator

$\mathsf{S}_{k_{1},k_{2}}^{\circ}\colon\mathbb{R}^{W_{G}(k_{2})}\rightarrow\mathbb{R}^{W_{G}(k_{1})}$

such that for every $f\in\mathbb{R}^{W_{G}(k_{2})}$,

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

where $ww^{\prime}$ denotes the concatenation of the walks $w$ and
$w^{\prime}$. The operator $\mathsf{S}_{k_{1},k_{2}}^{\circ}$ can be defined
more concretely in matrix form such that for every $w\in W_{G}(k_{1})$ and
$w^{\prime}\in W_{G}(k_{2})$,

$\displaystyle\left(\mathsf{S}_{k_{1},k_{2}}^{\circ}\right)_{w,w^{\prime}}\coloneqq\frac{\Pi_{k}(ww^{\prime})}{\Pi_{k_{1}}(w)}.$

######  Remark 9.11.

Swap operators are Markov operators, so the largest singular value of a Swap
operator is bounded by $1$.

Unlike the Swap operators for HDXs described in [AJT19], which are defined
using unordered subsets of hyperedges, the Swap operators
$\mathsf{S}_{k_{1},k_{2}}^{\circ}$ use sub-walks and are thus directed
operators. Instead of analyzing such an operator directly, we will examine the
symmetrized version

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

and show that $\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$ is the
normalized random walk operator of an undirected graph. In particular,
$\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$ defines an undirected weighted
bipartite graph on the vertices $W_{G}(k_{1})\cup W_{G}(k_{2})$, where 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_{G}(k_{1})$ and the other is in $W_{G}(k_{2})$. This becomes clear when
taking a closer look at the adjoint operator
$(\mathsf{S}_{k_{1},k_{2}}^{\circ})^{{\dagger}}$.

######  Claim 9.12.

Let $k_{1},k_{2}\in{\mathbb{N}}$ and $k=k_{1}+k_{2}$. Define the operator
$\mathfrak{S}_{k_{1},k_{2}}\colon\mathbb{R}^{W_{G}(k_{1})}\rightarrow\mathbb{R}^{W_{G}(k_{2})}$
such that for every $f\in{\mathbb{R}}^{W_{G}(k_{1})}$,

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

for every $w^{\prime}\in W_{G}(k_{2})$. Then

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

###### Proof.

Let $f\in C^{W_{G}(k_{1})}$ and $g\in C^{W_{G}(k_{2})}$. We show that $\langle
f,\mathsf{S}_{k_{1},k_{2}}^{\circ}g\rangle=\langle\mathfrak{S}_{k_{1},k_{2}}f,g\rangle$.
On one hand we have

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

On the other hand we have

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

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

####  9.1.3 Swap Operators are Splittable

At a high level, the expansion of a certain collection of Swap walks
$\mathsf{S}_{k_{1},k_{2}}^{\circ}$ ensures that we can round the SOS solution
and this gives rise to the splittable notion, which we tailor to the
$W_{G}(k)$ case after recalling some notation.

######  Remark 9.13.

We establish the definitions in slightly greater generality than needed for
our coding application since this generality is useful for solving $k$-CSP
instances on $W_{G}(k)$ for more general graphs $G$ that are not necessarily
expanders (c.f. Section 9.1.5). Solving these kinds of $k$-CSPs might be of
independent interest. For the coding application, the threshold rank
(Definition 9.14) will be one, i.e., we will be working with expander graphs.

######  Definition 9.14 (Threshold Rank of Graphs (from [BRS11])).

Let $G=(V,E,w)$ be a weighted graph on $n$ vertices and $\mathsf{A}$ be its
normalized random walk matrix. Suppose the eigenvalues of $\mathsf{A}$ are
$1=\lambda_{1}\geq\cdots\geq\lambda_{n}$. Given a parameter $\tau\in(0,1)$, we
denote the threshold rank of $G$ by
$\operatorname{rank}_{\geq\tau}(\mathsf{A})$ (or
$\operatorname{rank}_{\geq\tau}(G)$) and define it as

$\operatorname{rank}_{\geq\tau}(\mathsf{A})\coloneqq\left|\\{i\mid\lambda_{i}\geq\tau\\}\right|.$

Let $\operatorname{Swap}(\mathcal{T},W_{G}(\leq k))$ be the set of all swap
graphs over $W_{G}(\leq k)$ finding representation in the splitting tree
$\mathcal{T}$, i.e., for each internal node with leaves labeled $k_{1}$ and
$k_{2}$ we associate the undirected Swap operator
$\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$.

Given a threshold parameter $\tau\leq 1$ and a set of normalized adjacency
matrices $\mathcal{A}=\\{\mathsf{A}_{1},\dots,\mathsf{A}_{s}\\}$, we define
the threshold rank $\operatorname{rank}_{\geq\tau}(\mathcal{A})$ of
$\mathcal{A}$ as

$\operatorname{rank}_{\geq\tau}(\mathcal{A})\coloneqq\max_{\mathsf{A}\in\mathcal{A}}~{}\operatorname{rank}_{\geq\tau}(\mathsf{A}),$

where $\operatorname{rank}_{\geq\tau}(\mathsf{A})$ denotes the usual threshold
rank of $\mathsf{A}$ as in Definition 9.14.

######  Definition 9.15 ($(\mathcal{T},\tau,r)$-splittability [AJT19]).

A collection $W_{G}(\leq k)$ is said to be $(\mathcal{T},\tau,r)$-splittable
if $\mathcal{T}$ is a $k$-splitting tree and

$\operatorname{rank}_{\geq\tau}(\operatorname{Swap}(\mathcal{T},W_{G}))\leq
r.$

If there exists some $k$-splitting tree $\mathcal{T}$ such that $W_{G}(\leq
k)$ is $(\mathcal{T},\tau,r)$-splittable, the instance $W_{G}(\leq k)$ will be
called a $(\tau,r)$-splittable instance.

We show that the expansion of $\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$
is inherited from the expansion of its defining graph $G$. To this end we will
have to overcome the hurdle that $W_{G}(k)\subseteq V^{k}$ is not necessarily
a natural product space, but it can be made so with the proper representation.

######  Lemma 9.16.

Let $G=(V=[n],E)$ be a $d$-regular graph with normalized random walk operator
$\mathsf{A}_{G}$. Then for every $k_{1},k_{2}\in\mathbb{N}^{+}$, there are
representations of $\mathsf{S}_{k_{1},k_{2}}^{\circ}$ and $\mathsf{A}_{G}$ as
matrices such that

$\mathsf{S}_{k_{1},k_{2}}^{\circ}=\mathsf{A}_{G}\otimes\mathsf{J}/d^{k_{2}-1},$

where $\mathsf{J}\in\mathbb{R}^{[d]^{k_{1}-1}\times[d]^{k_{2}-1}}$ is the all
ones matrix.

###### Proof.

Partition the set of walks $W_{G}(k_{1})$ into the sets $W_{1},\dots,W_{n}$,
where $w\in W_{i}$ if the last vertex of the walk is $w_{k_{1}}=i$. Similarly,
partition $W_{G}(k_{2})$ into the sets $W_{1}^{\prime},\dots,W_{n}^{\prime}$,
where $w^{\prime}\in W_{j}^{\prime}$ if the first vertex of the walk is
$w^{\prime}_{1}=j$. Note that $\left\lvert W_{i}\right\rvert=d^{k_{1}-1}$ for
all $i$ and $\left\lvert W_{j}^{\prime}\right\rvert=d^{k_{2}-1}$ for all $j$.

Now order the rows of the matrix $\mathsf{S}_{k_{1},k_{2}}^{\circ}$ so that
all of the rows corresponding to walks in $W_{1}$ appear first, followed by
those for walks in $W_{2}$, and so on, with an arbitrary order within each
set. Do a similar re-ordering of the columns for the sets
$W_{1}^{\prime},\dots,W_{n}^{\prime}$. Observe that

$\left(\mathsf{S}_{k_{1},k_{2}}^{\circ}\right)_{w,w^{\prime}}=\frac{\Pi_{k_{1}+k_{2}}(ww^{\prime})}{\Pi_{k_{1}}(w)}=\frac{\mathbf{1}\left[w_{k_{1}}\text{
is adjacent to }w^{\prime}_{1}\right]}{d^{k_{2}-1}},$

which only depends on the adjacency of the last vertex of $w$ and the first
vertex of $w^{\prime}$. If the vertices $i$ and $j$ are adjacent, then
$\left(\mathsf{S}_{k_{1},k_{2}}^{\circ}\right)_{w,w^{\prime}}=1/d^{k_{2}-1}$
for every $w\in W_{i}$ and $w^{\prime}\in W_{j}^{\prime}$; otherwise,
$\left(\mathsf{S}_{k_{1},k_{2}}^{\circ}\right)_{w,w^{\prime}}=0$. Since the
walks in the rows and columns are sorted according to their last and first
vertices, respectively, the matrix $\mathsf{S}_{k_{1},k_{2}}^{\circ}$ exactly
matches the tensor product $\mathsf{A}_{G}\otimes\mathsf{J}/d^{k_{2}-1}$,
where the rows and columns of $\mathsf{A}_{G}$ are sorted according to the
usual ordering on $[n]$.

######  Corollary 9.17.

Let $G=(V,E)$ be a $\gamma$-two-sided spectral expander with normalized random
walk operator $\mathsf{A}_{G}$. Then for every $k_{1},k_{2}\in\mathbb{N}^{+}$,

$\lambda_{2}(\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ}))\leq\gamma.$

###### Proof.

To make the presentation reasonably self-contained, we include the proof of
the well-known connection between the singular values of
$\mathsf{S}_{k_{1},k_{2}}^{\circ}$ and the eigenvalues of
$\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$. Using Lemma 9.16 and the fact
that
$\sigma_{i}(\mathsf{A}_{G}\otimes\mathsf{J}/d^{k_{2}-1})=\sigma_{i}(\mathsf{A}_{G})$,
we have
$\sigma_{i}(\mathsf{S}_{k_{1},k_{2}}^{\circ})=\sigma_{i}(\mathsf{A}_{G})$.
Since

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

the nonzero singular values of $\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$
are the same as the nonzero singular values of
$\mathsf{S}_{k_{1},k_{2}}^{\circ}$. As
$\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$ is the random walk operator of
a bipartite graph, the spectrum of
$\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ})$ is symmetric around $0$
implying that its nonzero eigenvalues are

$\pm\sigma_{1}(\mathsf{S}_{k_{1},k_{2}}^{\circ}),\pm\sigma_{2}(\mathsf{S}_{k_{1},k_{2}}^{\circ}),\ldots=\pm\sigma_{1}(\mathsf{A}_{G}),\pm\sigma_{2}(\mathsf{A}_{G}),\ldots$

Hence, the second-largest of these is
$\lambda_{2}(\mathcal{U}(\mathsf{S}_{k_{1},k_{2}}^{\circ}))=\sigma_{2}(\mathsf{A}_{G})\leq\gamma$.

Applying this spectral bound on $\mathcal{U}(\mathsf{S}_{k,k}^{\circ})$ to
each internal node of any splitting tree readily gives the splittability of
$W_{G}(k)$.

######  Corollary 9.18.

If $G$ is a $\gamma$-two-sided spectral expander, then for every
$k\in\mathbb{N}^{+}$ the collection $W_{G}(k)$ endowed with $\Pi_{k}$ is
$(\gamma,1)$-splittable (for all choices of splitting trees).

####  9.1.4 Splittable Implies Tensorial

By a simple adaptation of an argument in [AJT19] for hypergraphs which built
on [BRS11], we can use the splittable property to obtain tensorial properties
for $W_{G}(k)$. More precisely, we can deduce Theorem 9.19.

######  Theorem 9.19 (Adapted from [AJT19]).

Suppose $W_{G}(\leq k)$ with $W_{G}(1)=[n]$ and an $(L+2k)$-local PSD ensemble
$\mathbf{Z}=\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ are given. There exist
some universal constants $c_{4}\geq 0$ and $C^{\prime\prime}\geq 0$ satisfying
the following: If $L\geq C^{\prime\prime}\cdot(q^{4k}\cdot k^{7}\cdot
r/\mu^{5})$, $\operatorname{Supp}(\mathbf{Z}_{j})\leq q$ for all $j\in[n]$,
and $W_{G}(\leq k)$ is $(c_{4}\cdot(\mu/(4k\cdot q^{k}))^{2},r)$-splittable,
then

$\operatorname*{\mathbb{E}}_{\Omega}\operatorname*{\mathbb{E}}_{w\sim
W_{G}(k)}{\left\lVert\\{\mathbf{Z}^{\prime}_{w}\\}-\left\\{\mathbf{Z}^{\prime}_{w_{1}}\right\\}\cdots\left\\{\mathbf{Z}^{\prime}_{w_{k}}\right\\}\right\rVert_{1}}\leq\mu,$
(13)

where $\mathbf{Z}^{\prime}$ is as defined in 6.5 on the input of
$\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ and $\Pi_{k}$.

Using Theorem 9.19, we can establish conditions on a $\gamma$-two-sided
expander graph $G=(V,E,w)$ in order to ensure that $W_{G}(k)$ is
$(\mu,L)$-two-step tensorial.

######  Lemma 9.20 (Expander walks are two-step tensorial).

There exist some universal constants $c^{\prime}\geq 0$ and $C^{\prime}\geq 0$
satisfying the following: If $L\geq c^{\prime}\cdot(q^{4k}\cdot
k^{7}/\mu^{5})$, $\operatorname{Supp}(\mathbf{Z}_{j})\leq q$ for all
$j\in[n]$, and $G$ is a $\gamma$-two-sided expander for $\gamma\leq
C^{\prime}\cdot\mu^{2}/\left(k^{2}\cdot q^{2k}\right)$ and size $\geq k$, then
$W_{G}(k)$ is $(\mu,L)$-two-step tensorial.

###### Proof.

The proof is similar to the proof of Lemma 7.4 for HDXs, so we omit it.

####  9.1.5 Interlude: Approximating $k$-CSP on Walk Constraints

Now, we digress to show how using Theorem 9.19 it is possible to deduce
parameters for approximating $k$-CSPs on $W_{G}(k)$. We believe this result
might be of independent interest and note that it is not required in the list
decoding application.

######  Corollary 9.21.

Suppose $\mathfrak{I}$ is a $q$-ary $k$-CSP instance with constraints on
$W_{G}(k)$. There exist absolute constants $C^{\prime\prime}\geq 0$ and
$c_{4}\geq 0$ satisfying the following:

If $W_{G}(k)$ is $(c_{4}\cdot(\mu/(4k\cdot q^{k}))^{2},r)$-splittable, then
there is an algorithm that runs in time $n^{O\left\lparen q^{4k}\cdot
k^{7}\cdot r/\mu^{5}\right\rparen}$ based on $(C^{\prime\prime}\cdot
k^{5}\cdot q^{k}\cdot r/\mu^{4})$-levels of SOS-hierarchy and 6.5 that outputs
a random assignment $\xi:[n]\rightarrow[q]$ that in expectation ensures
$\mathsf{SAT}_{\mathfrak{I}}(\xi)=\mathsf{OPT}(\mathfrak{I})-\mu$.

###### Proof.

The algorithm will just run 6.5 on the local PSD-ensemble
$\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ given by the SDP relaxation of
$\mathfrak{I}$ strengthened by $L=(C^{\prime\prime}\cdot k^{5}\cdot
q^{2k}/\mu^{4})$-levels of SOS-hierarchy and $\Pi_{k}$, where
$C^{\prime\prime}\geq 0$ is the constant from Theorem 9.19. $\mathbf{Z}$
satisfies

$\mathsf{SDP}(\mathfrak{I})=\mathchoice{\underset{w\sim\Pi_{k}}{\mathbb{E}}\left[\mathchoice{\underset{\\{\mathbf{Z}_{w}\\}}{\mathbb{E}}\left[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]\right]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}\right]}{{\mathbb{E}}_{w\sim\Pi_{k}}[\mathchoice{\underset{\\{\mathbf{Z}_{w}\\}}{\mathbb{E}}\left[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]\right]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}]}{{\mathbb{E}}_{w\sim\Pi_{k}}[\mathchoice{\underset{\\{\mathbf{Z}_{w}\\}}{\mathbb{E}}\left[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]\right]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}]}{{\mathbb{E}}_{w\sim\Pi_{k}}[\mathchoice{\underset{\\{\mathbf{Z}_{w}\\}}{\mathbb{E}}\left[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]\right]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}[\mathbf{1}[\mathbf{Z}_{w}\in\mathcal{P}_{w}]]}]}\geq\mathsf{OPT}(\mathfrak{I}).$
(14)

Since the conditioning done on $\\{\mathbf{Z}^{\prime}\\}$ is consistent with
the local distribution, by law of total expectation and Eq. 14 we have

$\operatorname*{\mathbb{E}}_{\Omega}\operatorname*{\mathbb{E}}_{w\sim\Pi_{k}}{\mathbf{1}[\mathbf{Z}^{\prime}_{w}\in\mathcal{P}_{w}]}=\mathsf{SDP}(\mathfrak{I})\geq\mathsf{OPT}(\mathfrak{I}).$
(15)

By Theorem 9.19 we know that

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

Now, the fraction of constraints satisfied by the algorithm in expectation is

$\operatorname*{\mathbb{E}}_{\xi}[\mathsf{SAT}_{\mathfrak{I}}(\xi)]=\operatorname*{\mathbb{E}}_{\Omega}{\operatorname*{\mathbb{E}}_{w\sim\Pi_{k}}{\mathchoice{\underset{(\xi_{1},\ldots,\xi_{n})\sim\\{\mathbf{Z}_{1}^{\prime}\\}\cdots\\{\mathbf{Z}_{n}^{\prime}\\}}{\mathbb{E}}\left[\mathbf{1}[\xi|_{w}\in\mathcal{P}_{w}]\right]}{{\mathbb{E}}_{(\xi_{1},\ldots,\xi_{n})\sim\\{\mathbf{Z}_{1}^{\prime}\\}\cdots\\{\mathbf{Z}_{n}^{\prime}\\}}[\mathbf{1}[\xi|_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{(\xi_{1},\ldots,\xi_{n})\sim\\{\mathbf{Z}_{1}^{\prime}\\}\cdots\\{\mathbf{Z}_{n}^{\prime}\\}}[\mathbf{1}[\xi|_{w}\in\mathcal{P}_{w}]]}{{\mathbb{E}}_{(\xi_{1},\ldots,\xi_{n})\sim\\{\mathbf{Z}_{1}^{\prime}\\}\cdots\\{\mathbf{Z}_{n}^{\prime}\\}}[\mathbf{1}[\xi|_{w}\in\mathcal{P}_{w}]]}}}.$

By using Eq. 16, we can obtain

$\operatorname*{\mathbb{E}}_{\xi}[\mathsf{SAT}_{\mathfrak{I}}(\xi)]\geq\mathchoice{\underset{\Omega}{\mathbb{E}}\left[\operatorname*{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}{\mathbf{1}[\mathbf{Z}^{\prime}_{w}\textrm{
satisfies the constraint on
}w]}\right]}{{\mathbb{E}}_{\Omega}[\operatorname*{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}{\mathbf{1}[\mathbf{Z}^{\prime}_{w}\textrm{
satisfies the constraint on
}w]}]}{{\mathbb{E}}_{\Omega}[\operatorname*{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}{\mathbf{1}[\mathbf{Z}^{\prime}_{w}\textrm{
satisfies the constraint on
}w]}]}{{\mathbb{E}}_{\Omega}[\operatorname*{\mathbb{E}}_{\\{\mathbf{Z}_{w}\\}}{\mathbf{1}[\mathbf{Z}^{\prime}_{w}\textrm{
satisfies the constraint on }w]}]}-\mu.$

Using Eq. 15, we conclude

$\operatorname*{\mathbb{E}}_{\xi}[\mathsf{SAT}_{\mathfrak{I}}(\xi)]\geq\mathsf{SDP}(\mathfrak{I})-\mu=\mathsf{OPT}(\mathfrak{I})-\mu.$

###  9.2 Instantiation to Linear Base Codes

We instantiate the list decoding framework to the direct sum lifting given by
the collection $W_{G}(k)$ of length $k$ walks on a sufficiently expanding
graph $G=(V,E,w)$. For parity sampling of expander walks, we will rely on the
following fact.

######  Theorem 9.22 (Walks on Expanders are Parity Samplers [TS17]
(Restatement of Theorem 4.1)).

Suppose $G$ is a graph with second-largest eigenvalue in absolute value at
most $\lambda$, and let $X(k)$ be the set of all walks of length $k$ on $G$.
Then $X(k)$ is a $(\beta_{0},(\beta_{0}+2\lambda)^{\lfloor
k/2\rfloor})$-parity sampler. In particular, for any $\beta>0$, if
$\beta_{0}+2\lambda<1$ and $k$ is sufficiently large, then $X(k)$ is a
$(\beta_{0},\beta)$-parity sampler.

First, we instantiate the framework to linear codes which already encompasses
most of the ideas need for general binary codes.

######  Lemma 9.23 (Direct sum lifting of linear biased codes II).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. There exists a universal constant $C>0$
such that for any $d$-regular $\gamma$-two-sided expander graph $G$ on ground
set $W_{G}(1)=[n]$, if $\gamma\leq\varepsilon^{C}$, then the following holds:

For every binary $2\varepsilon_{0}$-biased linear code $\mathcal{C}_{1}$ on
$W_{G}(1)=[n]$, there exists a $2\varepsilon$-biased binary lifted linear code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ on $W_{G}(k)$
where $k=O\left(\log(1/\varepsilon)\right)$ and

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close
to $\mathcal{C}_{k}$, then we can compute the list
$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ (c.f. Definition
6.15) in time

$n^{\varepsilon^{-O\left(1\right)}}\cdot f(n),$

where $f(n)$ is the running time of a unique decoding algorithm for
$\mathcal{C}_{1}$.

  * -

[Rate] The rate $r_{k}$ of $\mathcal{C}_{k}$ satisfies $r_{k}=r_{1}/d^{k-1}$
where $r_{1}$ is the relative rate of $\mathcal{C}_{1}$.

  * -

[Linear] The lifted code $\mathcal{C}_{k}$ is linear.

###### Proof.

The proof is analogous to the one given in Lemma 7.5. We want to define
parameters for a $\gamma$-two-sided expander $G=(V,E,w)$ so that $W_{G}(k)$
satisfies strong enough robust and tensorial assumptions and we can apply
Theorem 6.17. In this application, we will rely on parity sampling for
robustness. If $\operatorname{dsum}_{W_{G}(k)}$ is a
$(2\varepsilon_{0},2\varepsilon)$-parity sampler, using the linearity of
$\mathcal{C}_{1}$, we obtain a lifted code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ which is linear
and has bias $2\varepsilon$; thus the lifting is indeed
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust. If we want to fully rely on
parity sampling in Theorem 6.17, the lifting must be a
$(\beta_{0}=1/2+\varepsilon_{0},\beta=2\varepsilon)$-parity sampler, which is
more stringent than the first parity sampling requirement. 212121Recall that
this strengthening is used in our list decoding framework. To invoke Theorem
9.22 and obtain this $(\beta_{0},\beta)$-parity sampler, we need to choose a
parameter $\theta$ (where $0<\theta<(1-\beta_{0})/\beta_{0}$) such that

$\displaystyle k\geq 2\cdot\log_{(1+\theta)\beta_{0}}(\beta)+2\text{ and}$
$\displaystyle\gamma\leq\frac{\theta\cdot\beta_{0}}{2},$

which will ensure that

$(\beta_{0}+2\gamma)^{\lfloor k/2\rfloor}\leq((1+\theta)\beta_{0})^{\lfloor
k/2\rfloor}\leq\beta.$

To get a $(\mu,L)$-tensorial collection of walks, Lemma 9.20 requires

$L\geq\frac{c^{\prime}\cdot 2^{4k}\cdot k^{7}}{\mu^{5}}\quad\text{ and
}\quad\gamma\leq\frac{C^{\prime}\cdot\mu^{2}}{k^{2}\cdot 2^{2k}}.$

where we used that our alphabet is binary (i.e., $q=2$) and
$c^{\prime},C^{\prime}>0$ are constants. Finally, Theorem 6.17 requires
$\mu\leq\varepsilon^{8}/2^{22}$. The conceptual part of the proof is
essentially complete and we are left to compute parameters. We choose
$\theta=1/2-\varepsilon_{0}$, so that provided $\varepsilon_{0}<1/2$ we have
$(1+\theta)\beta_{0}=3/4+\varepsilon_{0}-\varepsilon_{0}^{2}<1$. Combining the
parity sampling and tensorial requirements and after some simplification, the
expansion $\gamma$ is constrained as

$\gamma\leq C^{\prime\prime}\cdot\min\left(\frac{\varepsilon^{16}}{k^{2}\cdot
2^{2k}},\left(1/4-\varepsilon_{0}^{2}\right)\right),$

where $C^{\prime\prime}>0$ is a constant. We deduce that taking $\gamma$ as

$\gamma\leq
C^{\prime\prime}\cdot\frac{\left(1/4-\varepsilon_{0}^{2}\right)\cdot\varepsilon^{16}}{k^{2}\cdot
2^{2k}}$

is sufficient. Further simplifying the above bound gives $\gamma$ as in the
statement of the theorem. Now, we turn to the SOS related parameter $L$ which
is constrained to be

$L\geq c^{\prime\prime}\cdot\frac{2^{4k}\cdot k^{7}}{\varepsilon^{40}},$

where $c^{\prime\prime}>0$. Note that in this case the exponent $O(L+k)$
appearing in the running time of Theorem 6.17 becomes $O(L)$. Further
simplification of the bound on $L$ leads to a running time of
$n^{\varepsilon^{-O(1)}}\cdot f(n)$ as in the statement of the theorem.

###  9.3 Instantiation to General Base Codes

The proof of Theorem 9.2 follows from Lemma 9.23 in the same way that Theorem
7.7 follows from Lemma 7.5 in the case of HDXs.

## 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.
  * [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.
  * [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.
  * [BHK+16] B. Barak, S. B. Hopkins, J. Kelner, P. Kothari, A. Moitra, and A. Potechin.  A nearly tight sum-of-squares lower bound for the planted clique problem, 2016.
  * [BKS17] Boaz Barak, Pravesh K. Kothari, and David Steurer.  Quantum entanglement, sum of squares, and the log rank conjecture.  In Proceedings of the 49th ACM Symposium on Theory of Computing, pages 975–988. ACM, 2017.
  * [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.
  * [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.
  * [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.
  * [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.
  * [GM12] Bernd Gärtner and Jiri Matousek.  Approximation Algorithms and Semidefinite Programming.  Applications of Mathematics. Springer-Verlag Berlin Heidelberg, 2012.
  * [GNW95] O. Goldreich, N. Nisan, and A. Wigderson.  On Yao’s XOR lemma.  Technical Report TR95-50, Electronic Colloquium on Computational Complexity, 1995.
  * [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\.
  * [Gur01] Venkatesan Guruswami.  List Decoding of Error-Correcting Codes.  PhD thesis, MIT, 2001.
  * [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson.  Expander graphs and their applications.  Bull. Amer. Math. Soc., 43(04):439–562, August 2006.
  * [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.
  * [KKK19] Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari.  List-decodable linear regression.  In NeurIPS, 2019.
  * [KMOW17] Pravesh Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer.  Sum of squares lower bounds for refuting any CSP.  In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017.
  * [LPS88] Alexander Lubotzky, R. Phillips, and Peter Sarnak.  Ramanujan graphs.  Combinatorica, 8:261–277, 1988.
  * [LSV05a] Alexander Lubotzky, Beth Samuels, and Uzi Vishne.  Explicit constructions of ramanujan complexes of type ad.  Eur. J. Comb., 26(6):965–993, August 2005.
  * [LSV05b] Alexander Lubotzky, Beth Samuels, and Uzi Vishne.  Ramanujan complexes of typeãd.  Israel Journal of Mathematics, 149(1):267–299, Dec 2005.
  * [Lub18] Alexander Lubotzky.  High dimensional expanders.  In ICM, 2018.
  * [MU17] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis.  Cambridge University Press, 2017.
  * [RW17] Prasad Raghavendra and Benjamin Weitz.  On the bit complexity of sum-of-squares proofs.  In Proceedings of the 44th International Colloquium on Automata, Languages and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [RY20] Prasad Raghavendra and Morris Yau.  List decodable learning via sum of squares.  In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, 2020.
  * [STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan.  Pseudorandom generators without the XOR lemma.  Journal of Computer and System Sciences, 62(2):236–266, 2001.
  * [Sud00] Madhu Sudan.  List decoding: Algorithms and applications.  In Proceedings of the International Conference IFIP on Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, TCS ’00, pages 25–41, Berlin, Heidelberg, 2000. Springer-Verlag.
  * [Tre04] Luca Trevisan.  Some applications of coding theory in computational complexity.  Quaderni di Matematica, 13:347–424, 2004.  arXiv:cs.CC/0409044.
  * [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.

##  Appendix A Auxiliary Basic Facts of Probability

In this section, we collect some basic facts of probability used in the text.

######  Fact A.1 (First Moment Bound).

Let $\mathbf{R}$ be a random variable in $[0,1]$ with
${\mathbb{E}}\left[\mathbf{R}\right]=\alpha$. Let $\beta\in(0,1)$ be an
arbitrary approximation parameter. Then

$\operatorname*{\mathbb{P}}\left[\mathbf{R}\geq(1-\beta)\cdot\alpha\right]\geq\beta\cdot\alpha.$

In particular,

$\operatorname*{\mathbb{P}}\left[\mathbf{R}\geq\frac{\alpha}{2}\right]\geq\frac{\alpha}{2}.$

######  Fact A.2 (Chernoff Bound [MU17]).

Let $\mathbf{R}_{1},\dots,\mathbf{R}_{n}$ be independent and identically
distributed random variables where $\mathbf{R}_{i}$ is uniformly distributed
on $\\{\pm 1\\}$. For every $a>0$,

$\operatorname*{\mathbb{P}}\left[\left\lvert\sum_{i=1}^{n}\mathbf{R}_{i}\right\rvert\geq
a\right]\leq 2\cdot\exp\left(-\frac{a^{2}}{2n}\right).$

######  Fact A.3 (Hoeffding Bound [MU17]).

Let $\mathbf{R}_{1},\dots,\mathbf{R}_{n}$ be independent random variables such
that ${\mathbb{E}}\left[\mathbf{R}_{i}\right]=\mu$ and
$\operatorname*{\mathbb{P}}\left[a\leq\mathbf{R}_{i}\leq b\right]=1$ for
$i\in[n]$. For every $\beta>0$,

$\operatorname*{\mathbb{P}}\left[\left\lvert\frac{1}{n}\sum_{i=1}^{n}\mathbf{R}_{i}-\mu\right\rvert\geq\beta\right]\leq
2\cdot\exp\left(-\frac{2\cdot\beta^{2}\cdot n}{(a-b)^{2}}\right).$

##  Appendix B Further Properties of Liftings

We show that a uniformly random odd function $g\colon\\{\pm
1\\}^{k}\rightarrow\\{\pm 1\\}$ yields a parity lifting w.v.h.p. in $k$. Thus,
parity liftings abound and we are not restricted to $k$-XOR in the framework.
In fact, SOS abstracts the specific combinatorial properties of the lifting
function being able to handle them in a unified way.

######  Lemma B.1.

Let $k\in\mathbb{N}^{+}$ be odd. For every $p,\beta,\theta>0$ satisfying
$\theta\geq\sqrt{\log(2/\beta)}/\sqrt{pk}$,

$\operatorname*{\mathbb{P}}_{g}\left[\left\lvert{\mathbb{E}}_{x\sim\textup{Bern}(p)^{\otimes
k}}\left[g(\chi^{\otimes k}(x))\right]\right\rvert\geq\beta\right]\leq 2\cdot
k\cdot\exp\left(-\beta^{2}\cdot\binom{k}{\lfloor(1-\theta)pk\rfloor}/8\right),$

where $g\colon\\{\pm 1\\}^{k}\rightarrow\\{\pm 1\\}$ is a uniformly random odd
function and $\chi\colon(\mathbb{F}_{2},+)\rightarrow(\\{\pm 1\\},\cdot)$ is
the non-trivial character.

###### Proof.

It is enough to consider $p\in(0,1/2]$ since the case $p\in[1/2,1)$ can be
reduced to the current case by taking the complement of the bit strings
appearing in this analysis. Applying the Hoeffding bound A.3 yields

$\displaystyle{\mathbb{E}}_{x\sim\textup{Bern}(p)^{\otimes
k}}\left[g(x)\right]$
$\displaystyle={\mathbb{E}}_{w\sim\textup{Binom}(k,p)}\left[g(\chi^{\otimes
k}(x))\mathbf{1}_{w\in[pk\pm C\cdot pk]}\right]\pm 2\cdot\exp(-C^{2})$
$\displaystyle={\mathbb{E}}_{w\sim\textup{Binom}(k,p)}\left[g(\chi^{\otimes
k}(x))\mathbf{1}_{w\in[pk\pm C\cdot pk]}\right]\pm\frac{\beta}{2},$

where the last equality follows from choosing $C=\theta\sqrt{pk}$ and the
assumption that $\theta\geq\sqrt{\log(2/\beta)}/\sqrt{pk}$.

Since $p\leq 1/2$, $\ell=\binom{k}{\lfloor(1-\theta)\cdot p\cdot k\rfloor}$ is
a lower bound on the number of binary strings of the Boolean $k$-hypercube in
a single layer of Hamming weight in the interval $[pk\pm C\cdot pk]$. A second
application of the Hoeffding bound A.3 gives that the bias within this layer
is

$\operatorname*{\mathbb{P}}_{g}\left[\left\lvert{\mathbb{E}}_{x\in\mathbb{F}_{2}^{k}\colon\left\lVert
x\right\rVert=\ell}\left[g(\chi^{\otimes
k}(x))\right]\right\rvert\geq\beta/2\right]\leq
2\cdot\exp\left(\beta^{2}\cdot\ell/8\right).$

By union bound over the layers the result follows.

##  Appendix C Derandomization

We show how to derandomize the list decoding framework (which amounts to
derandomize 6.29) when the lifting function is a parity sampler and it
satisfies a bounded degree condition (cf Eq. 17). We observe that this is the
setting of our two concrete instantiations, namely, for HDXs and expander
walks. In the former case, we work with $D$-flat distributions and in the
latter case with walk length and graph degree that are both functions of
$\varepsilon$. Roughly speaking, we show that replacing a random sample by the
majority works as long as parity sampling is sufficiently strong.

######  Lemma C.1 (Majority Word).

Let $z^{*}\in\\{\pm 1\\}^{X(1)}$ where $X(1)=[n]$. Suppose that
$y^{*}=\operatorname{lift}_{X(k)}(z^{*})$ satisfy

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left|{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}^{*}\cdot\operatorname{lift}(z)_{\mathfrak{s}}\right|\right]\geq
3\cdot\varepsilon,$

and

$\operatorname*{\mathbb{P}}_{\mathfrak{s}\sim\Pi_{k}}\left[\mathfrak{s}\ni
i\right]\leq\frac{g(\varepsilon)}{n}.$ (17)

If also $\operatorname{lift}_{X(k)}$ is a $(1-\xi,2\varepsilon)$-parity
sampler for some $\xi\in(0,1)$, $\xi\geq
2\exp{\left(-C\cdot\varepsilon^{2}\cdot g(\varepsilon)^{2}\cdot
n\right)}=o_{n}(1)$ where $C>0$ is an universal constant and $\xi\geq
1/(n(1-\xi-o_{n}(1)))$, then

$\left\lvert{\mathbb{E}}_{i\in[n]}z^{*}_{i}\cdot
z_{i}^{\prime}\right\rvert\geq 1-7\sqrt{\xi},$

where $z^{\prime}\in\\{\pm 1\\}^{n}$ is the majority defined as
$z_{i}^{\prime}=\operatorname*{\arg\\!\max}_{b\in\\{\pm
1\\}}\Pr_{\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}[\mathbf{Z}_{i}=b]$.

###### Proof.

Define
$f(z)\coloneqq\left\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}^{*}\cdot\operatorname{lift}(z)_{\mathfrak{s}}\right\rvert$.
Then, using Eq. 17 we claim that $f(z)$ is $O(g(\varepsilon)/n)$-Lipschitz
with respect to $\ell_{1}$ since

$\left\lvert f(z)-f(\tilde{z})\right\rvert\leq\sum_{i\in
X(1)}2\cdot\operatorname*{\mathbb{P}}_{\mathfrak{s}\sim\Pi_{k}}\left[\mathfrak{s}\ni
i\right]\cdot\left\lvert z_{i}-\tilde{z}_{i}\right\rvert\leq
O\left(\frac{g(\varepsilon)}{n}\right)\cdot\left\lVert
z-\tilde{z}\right\rVert_{1}.$

Since the underlying distribution of
$\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}$ is a product distribution on
$\\{\pm 1\\}^{n}$ and $f$ is $O(g(\varepsilon)/n)$-Lipschitz, applying
Hoeffding’s inequality yields

$\operatorname*{\mathbb{P}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[f(z)\leq\varepsilon\right]\leq\operatorname*{\mathbb{P}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left|f(z)-{\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}f(z)\right|\geq\varepsilon\right]\leq\exp{\left(-\Theta(g^{\prime}(\varepsilon)\cdot
n)\right)},$

where $g^{\prime}(\varepsilon)=\varepsilon^{2}\cdot g(\varepsilon)^{2}$.

Using the assumption that $\operatorname{lift}$ is a
$(1-\xi,2\varepsilon)$-parity sampler, we obtain

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\lvert\langle
z^{*},z\rangle\right\rvert\right]\geq
1-\xi-2\exp{\left(-\Theta(g^{\prime}(\varepsilon)\cdot n)\right)}.$

By Jensen’s inequality,

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\langle
z^{*},z\rangle^{2}\right]\geq\left({\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left\lvert\langle
z^{*},z\rangle\right\rvert\right]\right)^{2}\geq(1-\xi-2\exp{\left(-\Theta(g^{\prime}(\varepsilon)\cdot
n)\right)})^{2}.$

Using indepdence, we get

${\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[{\mathbb{E}}_{i,j\in[n]}z^{*}_{i}z_{i}z_{j}z_{j}^{*}\right]\leq{\mathbb{E}}_{i,j\in[n]}z^{*}_{i}{\mathbb{E}}\left[z_{i}\right]{\mathbb{E}}\left[z_{j}\right]z_{j}^{*}+\frac{1}{n}=\left({\mathbb{E}}_{i\in[n]}z^{*}_{i}{\mathbb{E}}\left[z_{i}\right]\right)^{2}+\frac{1}{n}.$

Thus, in particular
$\left\lvert{\mathbb{E}}_{i\in[n]}z^{*}_{i}{\mathbb{E}}\left[z_{i}\right]\right\rvert\geq(1-\xi-
o_{n}(1))-1/((1-\xi-o_{n}(1))n)\geq 1-3\xi$ which implies

$\displaystyle 1-3\xi$
$\displaystyle\leq\left\lvert{\mathbb{E}}_{i\in[n]}z^{*}_{i}\left(\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=1]-\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=-1]\right)\right\rvert$
$\displaystyle\leq{\mathbb{E}}_{i\in[n]}\left\lvert\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=1]-\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=-1]\right\rvert.$

Since

${\mathbb{E}}_{i\in[n]}1-\left\lvert\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=1]-\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=-1]\right\rvert\leq
3\xi,$

Markov’s inequality yields

$\operatorname*{\mathbb{P}}_{i\in[n]}\left[1-\sqrt{\xi}\geq\left\lvert\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=1]-\Pr_{|_{(S,\sigma)}}[\mathbf{Z}_{i}=-1]\right\rvert\right]\leq
3\sqrt{\xi}.$

Now, let $z^{\prime}\in\\{\pm 1\\}^{n}$ be as in the statement of the lemma.
Then,

$1-3\xi-4\sqrt{\xi}\leq\left\lvert{\mathbb{E}}_{i\in[n]}z^{*}_{i}\cdot
z_{i}^{\prime}\right\rvert.$

Hence, we conclude that $\left\lvert{\mathbb{E}}_{i\in[n]}z^{*}_{i}\cdot
z_{i}^{\prime}\right\rvert\geq 1-7\sqrt{\xi}$.

######  Remark C.2.

The parity sampling requierment might be slightly stronger with this
derandomized version but it does not change the asymptotic nature of our
results. More precisely, we are only asking for $(1-\xi,2\varepsilon)$-parity
sampler for a different constant value $\xi>0$.