# List Decoding of Direct Sum Codes

Vedat Levi Alev  Supported by NSERC Discovery Grant 2950-120715, NSERC
Accelerator Supplement 2950-120719, and partially supported by NSF awards
CCF-1254044 and CCF-1718820. University of Waterloo<EMAIL_ADDRESS>Fernando Granha Jeronimo Supported in part by NSF grants CCF-1254044 and
CCF-1816372. University of Chicago<EMAIL_ADDRESS> Dylan Quintana
University of<EMAIL_ADDRESS>Shashank Srivastava
<EMAIL_ADDRESS>Madhur Tulsiani Supported by NSF grants CCF-1254044
and CCF-1816372. TTIC<EMAIL_ADDRESS>
We consider families of codes obtained by "lifting" a base code $\mathcal{C}$
through operations such as $k$-XOR applied to "local views" of codewords of
$\mathcal{C}$, according to a suitable $k$-uniform hypergraph. The $k$-XOR
operation yields the direct sum encoding used in works of [Ta-Shma, STOC 2017]
and [Dinur and Kaufman, FOCS 2017].

We give a general framework for list decoding such lifted codes, as long as
the base code admits a unique decoding algorithm, and the hypergraph used for
lifting satisfies certain expansion properties. We show that these properties
are indeed satisfied by the collection of length $k$ walks on a sufficiently
strong expanding graph, and by hypergraphs corresponding to high-dimensional
expanders. Instantiating our framework, we obtain list decoding algorithms for
direct sum liftings corresponding to the above hypergraph families. Using
known connections between direct sum and direct product, we also recover (and
strengthen) the recent results of Dinur et al. [SODA 2019] on list decoding
for direct product liftings.

Our framework relies on relaxations given by the Sum-of-Squares (SOS) SDP
hierarchy for solving various constraint satisfaction problems (CSPs). We view
the problem of recovering the closest codeword to a given (possibly corrupted)
word, as finding the optimal solution to an instance of a CSP. Constraints in
the instance correspond to edges of the lifting hypergraph, and the solutions
are restricted to lie in the base code $\mathcal{C}$. We show that recent
algorithms for (approximately) solving CSPs on certain expanding hypergraphs
by some of the authors also yield a decoding algorithm for such lifted codes.

We extend the framework to list decoding, by requiring the SOS solution to
minimize a convex proxy for negative entropy. We show that this ensures a
covering property for the SOS solution, and the "condition and round" approach
used in several SOS algorithms can then be used to recover the required list
of codewords.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Simplicial Complexes
    2. 2.2 Codes and Lifts
    3. 2.3 Constraint Satisfaction Problems (CSPs)
    4. 2.4 Sum-of-Squares Relaxations and $t$-local PSD Ensembles
  3. 3 Proof Strategy and Organization
  4. 4 Pseudorandom Hypergraphs and Robustness of Direct Sum
    1. 4.1 Expander Walks and Parity Sampling
    2. 4.2 High-dimensional Expanders
    3. 4.3 HDXs are Parity Samplers
    4. 4.4 Rate of the Direct Sum Lifting
  5. 5 Unique Decoding
    1. 5.1 Unique Decoding on Parity Samplers
    2. 5.2 Concrete Instantiations
  6. 6 Abstract List Decoding Framework
    1. 6.1 Entropic Proxy
    2. 6.2 SOS Program for List Decoding
    3. 6.3 Properties of the Entropic Proxy
    4. 6.4 Propagation Rounding
    5. 6.5 Tensorial Structures
    6. 6.6 Further Building Blocks and Analysis
      1. 6.6.1 SOS Rounding and Recoverability
      2. 6.6.2 Coupled Pairs, Coupled Lists, and Covers
      3. 6.6.3 Cover Retrieval
      4. 6.6.4 Cover Purification and Robustness
      5. 6.6.5 Correctness of the List Decoding Algorithm
  7. 7 Instantiation I: Direct Sum on HDXs
    1. 7.1 HDXs are Two-Step Tensorial
    2. 7.2 Instantiation to Linear Base Codes
    3. 7.3 Instantiation to General Base Codes
  8. 8 List Decoding Direct Product Codes
    1. 8.1 Direct Product Codes
    2. 8.2 Direct Product List Decoding
  9. 9 Instantiation II: Direct Sum on Expander Walks
    1. 9.1 Expander Walks are Two-Step Tensorial
      1. 9.1.1 Emergence of Swap Operators
      2. 9.1.2 Swap Operators Arising from Expander Walks
      3. 9.1.3 Swap Operators are Splittable
      4. 9.1.4 Splittable Implies Tensorial
      5. 9.1.5 Interlude: Approximating $k$-CSP on Walk Constraints
    2. 9.2 Instantiation to Linear Base Codes
    3. 9.3 Instantiation to General Base Codes
  10. A Auxiliary Basic Facts of Probability
  11. B Further Properties of Liftings
  12. C Derandomization

##  1 Introduction

We consider the problem of list decoding binary codes obtained by starting
with a binary base code $\mathcal{C}$ and amplifying its distance by “lifting”
$\mathcal{C}$ to a new code $\mathcal{C}^{\prime}$ using an expanding or
pseudorandom structure. Examples of such constructions include _direct
products_ where one lifts (say) $\mathcal{C}\subseteq{\mathbb{F}}_{2}^{n}$ to
$\mathcal{C}^{\prime}\subseteq({\mathbb{F}}_{2}^{k})^{n^{k}}$ with each
position in $y\in\mathcal{C}^{\prime}$ being a $k$-tuple of bits from $k$
positions in $z\in\mathcal{C}$. Another example is _direct sum_ codes where
$\mathcal{C}^{\prime}\subseteq{\mathbb{F}}_{2}^{n^{k}}$ and each position in
$y$ is the parity of a $k$-tuple of bits in $z\in\mathcal{C}$. Of course, for
many applications, it is interesting to consider a small “pseudorandom” set of
$k$-tuples, instead of considering the complete set of size $n^{k}$.

This kind of distance amplification is well known in coding theory [ABN+92,
IW97, GI01, TS17] and it can draw on the vast repertoire of random and
pseudorandom expanding objects [HLW06, Lub18]. Such constructions are also
known to have several applications to the theory of Probabilitically Checkable
Proofs (PCPs) [IKW09, DS14, DDG+15, Cha16, Aro02]. However, despite having
several useful properties, it might not always be clear how to _decode_ the
codes resulting from such constructions, especially when constructed using
sparse pseudorandom structures. An important example of this phenomenon is Ta-
Shma’s explicit construction of binary codes of arbitrarily large distance
near the (non-constructive) Gilbert-Varshamov bound [TS17]. Although the
construction is explicit, efficient decoding is not known. Going beyond
unique-decoding algorithms, it is also useful to have efficient list-decoding
algorithms for complexity-theoretic applications [Sud00, Gur01, STV01, Tre04].

The question of list decoding such pseudorandom constructions of direct-
product codes was considered by Dinur et al. [DHK+19], extending a unique-
decoding result of Alon et al. [ABN+92]. While Alon et al. proved that the
code is unique-decodable when the lifting hypergraph (collection of
$k$-tuples) is a good “sampler”, Dinur et al. showed that when the hypergraph
has additional structure (which they called being a “double sampler”) then the
code is also list decodable. They also posed the question of understanding
structural properties of the hypergraph that might yield even unique decoding
algorithms for the _direct sum_ based liftings.

We develop a generic framework to understand properties of the hypergraphs
under which the lifted code $\mathcal{C}^{\prime}$ admits efficient list
decoding algorithms, assuming only efficient unique decoding algorithms for
the base code $\mathcal{C}$. Formally, let $X$ be a downward-closed hypergraph
(simplicial complex) defined by taking the downward closure of a $k$-uniform
hypergraph, and let $g:{\mathbb{F}}_{2}^{k}\rightarrow{\mathbb{F}}_{2}$ be any
boolean function. $X(i)$ denotes the collection of sets of size $i$ in $X$ and
$X(\leq d)$ the collection of sets of size at most $d$. We consider the lift
$\mathcal{C}^{\prime}=\operatorname{lift}_{X(k)}^{g}(\mathcal{C})$, where
$\mathcal{C}\subseteq{\mathbb{F}}_{2}^{X(1)}$ and
$\mathcal{C}^{\prime}\subseteq{\mathbb{F}}_{2}^{X(k)}$, and each bit of
$y\in\mathcal{C}^{\prime}$ is obtained by applying the function $g$ to the
corresponding $k$ bits of $z\in\mathcal{C}$. We study properties of $g$ and
$X$ under which this lifting admits an efficient list decoding algorithm.

We consider two properties of this lifting, _robustness_ and _tensoriality_ ,
formally defined later, which are sufficient to yield decoding algorithms. The
first property (robustness) essentially requires that for any two words in
${\mathbb{F}}_{2}^{X(1)}$ at a moderate distance, the lifting amplifies the
distance between them. While the second property is of a more technical nature
and is inspired by the Sum-of-Squares (SOS) SDP hierarchy used for our
decoding algorithms, it is implied by some simpler combinatorial properties.
Roughly speaking, this combinatorial property, which we refer to as
_splittability_ , requires that the graph on (say) $X(k/2)$ defined by
connecting $\mathfrak{s},\mathfrak{t}\in X(k/2)$ if
$\mathfrak{s}\cap\mathfrak{t}=\emptyset$ and $\mathfrak{s}\cup\mathfrak{t}\in
X(k)$, is a sufficiently good expander (and similarly for graphs on $X(k/4)$,
$X(k/8)$, and so on). Splittability requires that the $k$-tuples can be
(recursively) split into disjoint pieces such that at each step the graph
obtained between the pairs of pieces is a good expander.

Expanding Structures. We instantiate the above framework with two specific
structures: the collection of $k$-sized hyperedges of a high-dimensional
expander (HDX) and the collection of length $k$ walks 111Actually, we will be
working with length $k-1$ walks which can be represented as $k$-tuples, though
this is an unimportant technicality. The reason is to be consistent in the
number of vertices (allowing repetitions) with $k$-sized hyperedges. on an
expander graph. HDXs are downward-closed hypergraphs satisfying certain
expansion properties. We will quantify this expansion using Dinur and
Kaufman’s notion of a $\gamma$-HDX [DK17].

HDXs were proved to be splittable by some of the authors [AJT19]. For the
expander walk instantiation, we consider a variant of splittability where a
walk of length $k$ is split into two halves, which are walks of length $k/2$
(thus we do _not_ consider all $k/2$ size subsets of the walk). The spectrum
of the graphs obtained by this splitting can easily be related to that of the
underlying expander graph. In both cases, we take the function $g$ to be
$k$-XOR which corresponds to the direct sum lifting. We also obtain results
for direct product codes via a simple (and standard) reduction to the direct
sum case.

Our Results. Now we provide a quantitative version of our main result. For
this, we split the main result into two cases (due to their difference in
parameters): HDXs and length $k$ walks on expander graphs. We start with the
former expanding object.

######  Theorem 1.1 (Direct Sum Lifting on HDX (Informal)).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. Suppose $X(\leq d)$ is a $\gamma$-HDX on
$n$ vertices with $\gamma\leq(\log(1/\varepsilon))^{-O(\log(1/\varepsilon))}$
and $d=\Omega\left((\log(1/\varepsilon))^{2}/\varepsilon^{2}\right)$.

For every linear code $\mathcal{C}_{1}\subset\mathbb{F}_{2}^{n}$ with relative
distance $\geq 1/2-\varepsilon_{0}$, there exists a direct sum lifting
$\mathcal{C}_{k}\subset\mathbb{F}_{2}^{X(k)}$ with
$k=O\left(\log(1/\varepsilon)\right)$ and relative distance $\geq
1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}$ satisfying the following:

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\varepsilon)$-close to
$\mathcal{C}_{k}$, then we can compute the list of all the codewords of
$\mathcal{C}_{k}$ that are $(1/2-\varepsilon)$-close to $\tilde{y}$ 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 222In the rate computation, $X(k)$ is viewed as a multi-set
where each $\mathfrak{s}\in X(k)$ is repeated a certain number of times for
technical reasons. $r_{k}$ of $\mathcal{C}_{k}$ is
$r_{k}=r_{1}\cdot\left\lvert X(1)\right\rvert/\left\lvert X(k)\right\rvert$,
where $r_{1}$ is the rate of $\mathcal{C}_{1}$.

A consequence of this result is a method of decoding the direct product
lifting on a HDX via a reduction to the direct sum case.

######  Corollary 1.2 (Direct Product Lifting on HDX (Informal)).

Let $\varepsilon_{0}<1/2$ be a constant and $\varepsilon>0$. Suppose $X(\leq
d)$ is a $\gamma$-HDX on $n$ vertices with
$\gamma\leq(\log(1/\varepsilon))^{-O(\log(1/\varepsilon))}$ and
$d=\Omega((\log(1/\varepsilon))^{2}/\varepsilon^{2})$.

For every linear code $\mathcal{C}_{1}\subset{\mathbb{F}}_{2}^{n}$ with
relative distance $\geq 1/2-\varepsilon_{0}$, there exists a direct product
encoding $\mathcal{C}_{\ell}\subset({\mathbb{F}}_{2}^{\ell})^{X(\ell)}$ with
$\ell=O(\log(1/\varepsilon))$ that can be efficiently list decoded up to
distance $(1-\varepsilon)$.

######  Remark 1.3.

List decoding the direct product lifting was first established by Dinur et al.
in [DHK+19] using their notion of double samplers. Since constructions of
double samplers are only known using HDXs, we can compare some parameters. In
our setting, we obtain $d=O(\log(1/\varepsilon)^{2}/\varepsilon^{2})$ and
$\gamma=(\log(1/\varepsilon))^{-O(\log(1/\varepsilon))}$ whereas in [DHK+19]
$d=O(\exp(1/\varepsilon))$ and $\gamma=O(\exp(-1/\varepsilon))$.

Given a graph $G$, we denote by $W_{G}(k)$ the collection of all length $k-1$
walks of $G$, which plays the role of the local views $X(k)$. If $G$ is
sufficiently expanding, we have the following result.

######  Theorem 1.4 (Direct Sum Lifting on Expander Walks (Informal)).

Let $\varepsilon_{0}<1/2$ be a constant and
$\varepsilon\in(0,\varepsilon_{0})$. Suppose $G$ is a $d$-regular
$\gamma$-two-sided spectral expander graph on $n$ vertices with
$\gamma\leq\varepsilon^{O(1)}$.

For every linear code $\mathcal{C}_{1}\subset\mathbb{F}_{2}^{n}$ with relative
distance $\geq 1/2-\varepsilon_{0}$, there exists a direct sum encoding
$\mathcal{C}_{k}\subset\mathbb{F}_{2}^{W_{G}(k)}$ with
$k=O\left(\log(1/\varepsilon)\right)$ and relative distance $\geq
1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}$ satisfying the following:

  * -

[Efficient List Decoding] If $\tilde{y}$ is $(1/2-\varepsilon)$-close to
$\mathcal{C}_{k}$, then we can compute the list of all the codewords of
$\mathcal{C}_{k}$ that are $(1/2-\varepsilon)$-close to $\tilde{y}$ 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}$ is $r_{k}=r_{1}/d^{k-1}$, where
$r_{1}$ is the rate of $\mathcal{C}_{1}$.

The results in Theorem 1.1, Corollary 1.2, and Theorem 1.4 can all be extended
(using a simple technical argument) to nonlinear base codes $\mathcal{C}_{1}$
with similar parameters. We also note that applying Theorem 1.1 to explicit
objects derived from Ramanujan complexes [LSV05b, LSV05a] and applying Theorem
1.4 to Ramanujan graphs [LPS88] yield explicit constructions of codes with
constant relative distance and rate, starting from a base code with constant
relative distance and rate. With these constructions, the rate of the lifted
code satisfies $r_{k}\geq
r_{1}\cdot\exp\left(-(\log(1/\varepsilon))^{O(\log(1/\varepsilon))}\right)$ in
the HDX case and $r_{k}\geq r_{1}\cdot\varepsilon^{O(\log(1/\varepsilon))}$
for expander walks. The precise parameters of these applications are given in
Corollary 7.2 of Section 7 and in Corollary 9.5 of Section 9, respectively.

Our techniques. We connect the question of decoding lifted codes to finding
good solutions for instances of Constraint Satisfaction Problems (CSPs) which
we then solve using the Sum-of-Squares (SOS) hierarchy. Consider the case of
direct sum lifting, where for the lifting $y$ of a codeword $z$, each bit of
$y$ is an XOR of $k$ bits from $z$. If an adversary corrupts some bits of $y$
to give $\tilde{y}$, then finding the closest codeword to $\tilde{y}$
corresponds to finding $z^{\prime}\in\mathcal{C}$ such that appropriate
$k$-bit XORs of $z^{\prime}$ agree with as many bits of $\tilde{y}$ as
possible. If the corruption is small, the distance properties of the code
ensure that the unique choice for $z^{\prime}$ is $z$. Moreover, the distance
amplification (robustness) properties of the lifting can be used to show that
it suffices to find _any_ $z^{\prime}$ (not necessarily in $\mathcal{C}$)
satisfying sufficiently many constraints. We then use results by a subset of
the authors [AJT19] showing that splittability (or the tensorial nature) of
the hypergraphs used for lifting can be used to yield algorithms for
approximately solving the related CSPs. Of course, the above argument does not
rely on the lifting being direct sum and works for any lifting function $g$.

For list decoding, we solve just a single SOS program whose solution is rich
enough to “cover” the list of codewords we intend to retrieve. In particular,
the solutions to the CSP are obtained by “conditioning” the SDP solution on a
small number of variables, and we try to ensure that in the list decoding
case, conditioning the SOS solution on different variables yields solutions
close to different elements of the list. To achieve this covering property we
consider a convex proxy $\Psi$ for negative entropy measuring how concentrated
(on a few codewords) the SOS solution is. Then we minimize $\Psi$ while
solving the SOS program. A similar technique was also independently used by
Karmalkar, Klivans, and Kothari [KKK19] and Raghavendra–Yau [RY20] in the
context of learning regression. Unfortunately, this SOS cover comes with only
some weak guarantees which are, a priori, not sufficient for list decoding.
However, again using the robustness property of the lifting, we are able to
convert weak covering guarantees for the lifted code $\mathcal{C}^{\prime}$ to
strong guarantees for the base code $\mathcal{C}$, and then appeal to the
unique decoding algorithm. We regard the interplay between these two
properties leading to the final list decoding application as our main
technical contribution. A more thorough overview is given in Section 3 after
introducing some objects and notation in Section 2. In Section 3, we also give
further details about the organization of the document.

Related work. The closest result to ours is the list decoding framework of
Dinur et al. [DHK+19] for the direct product encoding, where the lifted code
is not binary but rather over the alphabet ${\mathbb{F}}_{2}^{k}$. Our
framework instantiated for the direct sum encoding on HDXs (c.f. Theorem 1.1)
captures and strengthens some of their parameters in Corollary 1.2. While
Dinur et al. also obtain list decoding by solving an SDP for a specific CSP
(Unique Games), the reduction to CSPs in their case uses the combinatorial
nature of the double sampler instances and is also specific to the direct
product encoding. They recover the list by iteratively solving many CSP
instances, where each newly found solution is pruned from the instance by
reducing the alphabet size by one each time. On the other hand, the reduction
to CSPs is somewhat generic in our framework and the recovery of the list is
facilitated by including an entropic proxy in the convex relation. As
mentioned earlier, a similar entropic proxy was also (independently) used by
Karmalkar et al. [KKK19] and Raghavendra–Yau [RY20] in the context of list
decoding for linear regression and mean estimation. Direct products on
expanders were also used as a building block by Guruswami and Indyk [GI03] who
used these to construct _linear time_ list decodable codes over large
alphabets. They gave an algorithm for recovering the list based on spectral
partitioning techniques.

##  2 Preliminaries

###  2.1 Simplicial Complexes

It will be convenient to work with hypergraphs satisfying a certain downward-
closed property (which is straightforward to obtain).

######  Definition 2.1.

A simplicial complex $X$ with ground set $[n]$ is a downward-closed collection
of subsets of $[n]$, i.e., for all sets $\mathfrak{s}\in X$ and
$\mathfrak{t}\subseteq\mathfrak{s}$, we also have $\mathfrak{t}\in X$. The
sets in $X$ are referred to as faces of $X$. We use the notation $X(i)$ for
the set of all faces of a simplicial complex $X$ with cardinality $i$ and
$X(\leq d)$ for the set of all faces of cardinality at most $d$. 333Note that
it is more common to associate a geometric representation to simplicial
complexes, with faces of cardinality $i$ being referred to as faces of
_dimension_ $i-1$ (and the collection being denoted by $X(i-1)$ instead of
$X(i)$). However, we prefer to index faces by their cardinality to improve
readability of related expressions. By convention, we take
$X(0):=\\{\varnothing\\}$.

A simplicial complex $X(\leq d)$ is said to be a pure simplicial complex if
every face of $X$ is contained in some face of size $d$. Note that in a pure
simplicial complex $X(\leq d)$, the top slice $X(d)$ completely determines the
complex.

Simplicial complexes are equipped with the following probability measures on
their sets of faces.

######  Definition 2.2 (Probability measures $(\Pi_{1},\ldots,\Pi_{d})$).

Let $X(\leq d)$ be a pure simplicial complex and let $\Pi_{d}$ be an arbitrary
probability measure on $X(d)$. We define a coupled array of random variables
$(\mathfrak{s}^{(d)},\ldots,\mathfrak{s}^{(1)})$ as follows: sample
$\mathfrak{s}^{(d)}\sim\Pi_{d}$ and (recursively) for each $i\in[d]$, take
$\mathfrak{s}^{(i-1)}$ to be a uniformly random subset of $\mathfrak{s}^{(i)}$
of size $i-1$. The distributions $\Pi_{d-1},\ldots,\Pi_{1}$ are then defined
to be the marginal distributions of the random variables
$\mathfrak{s}^{(d-1)},\ldots,\mathfrak{s}^{(1)}$. We also define the joint
distribution of $(\mathfrak{s}^{(d)},\ldots,\mathfrak{s}^{(1)})$ as $\Pi$.
Note that the choice of $\Pi_{d}$ determines each other distribution $\Pi_{i}$
on $X(i)$.

In order to work with the HDX and expander walk instantiations in a unified
manner, we will use also use the notation $X(k)$ to indicate the set of all
length $k-1$ walks on a graph $G$. In this case, $X(k)$ is a set of $k$-tuples
rather than subsets of size $k$. This distinction will be largely irrelevant,
but we will use $W_{G}(k)$ when referring specifically to walks rather than
subsets. The set of walks $W_{G}(k)$ has a corresponding distribution
$\Pi_{k}$ as well (see Definition 9.1).

###  2.2 Codes and Lifts

#### Codes

We briefly recall some standard code terminology. Let $\Sigma$ be a finite
alphabet with $q\in\mathbb{N}$ symbols. We will be mostly concerned with the
case $\Sigma=\mathbb{F}_{2}$. Given $z,z^{\prime}\in\Sigma^{n}$, recall that
the relative Hamming distance between $z$ and $z^{\prime}$ is
$\Delta(z,z^{\prime})\coloneqq\left\lvert\\{i\mid z_{i}\neq
z_{i}^{\prime}\\}\right\rvert/n$. Any set $\mathcal{C}\subset\Sigma^{n}$ gives
rise to a $q$-ary code. The distance of $\mathcal{C}$ is defined as
$\Delta(\mathcal{C})\coloneqq\min_{z\neq z^{\prime}}\Delta(z,z^{\prime})$
where $z,z^{\prime}\in\mathcal{C}$. We say that $\mathcal{C}$ is a linear code
444In this case, $q$ is required to be a prime power. if
$\Sigma=\mathbb{F}_{q}$ and $\mathcal{C}$ is a linear subspace of
$\mathbb{F}_{q}^{n}$. The rate of $\mathcal{C}$ is
$\log_{q}(\left\lvert\mathcal{C}\right\rvert)/n$.

Instead of discussing the distance of a binary code, it will often be more
natural to phrase results in terms of its bias.

######  Definition 2.3 (Bias).

The bias of a word 555Equivalently, the bias of $z\in\\{\pm 1\\}^{n}$ is
$\operatorname{bias}(z)\coloneqq\left\lvert{\mathbb{E}}_{i\in[n]}z_{i}\right\rvert$.
$z\in{\mathbb{F}}_{2}^{n}$ is
$\operatorname{bias}(z)\coloneqq\left\lvert{\mathbb{E}}_{i\in[n]}(-1)^{z_{i}}\right\rvert$.
The bias of a code $\mathcal{C}$ is the maximum bias of any non-zero codeword
in $\mathcal{C}$.

#### Lifts

Starting from a code $\mathcal{C}_{1}\subset\Sigma^{X(1)}_{1}$, we amplify its
distance by considering a lifting operation defined as follows.

######  Definition 2.4 (Lifting Function).

Let $g:\Sigma_{1}^{k}\rightarrow\Sigma_{k}$ and $X(k)$ be a collection of
$k$-uniform hyperedges or walks of length $k-1$ on the set $X(1)$. For
$z\in\Sigma_{1}^{X(1)}$, we define $\operatorname{lift}_{X(k)}^{g}(z)=y$ such
that $y_{\mathfrak{s}}=g(z|_{\mathfrak{s}})$ for all $\mathfrak{s}\in X(k)$,
where $z|_{\mathfrak{s}}$ is the restriction of $z$ to the indices in
$\mathfrak{s}$.

The lifting of a code $\mathcal{C}_{1}\subseteq\Sigma_{1}^{X(1)}$ is

$\operatorname{lift}_{X(k)}^{g}(\mathcal{C}_{1})=\\{\operatorname{lift}_{X(k)}^{g}(z)\mid
z\in\mathcal{C}_{1}\\},$

which we will also denote $\mathcal{C}_{k}$. We will omit $g$ and $X(k)$ from
the notation for lifts when they are clear from context.

We will call liftings that amplify the distance of a code _robust_.

######  Definition 2.5 (Robust Lifting).

We say that $\operatorname{lift}_{X(k)}^{g}$ is $(\delta_{0},\delta)$-robust
if for every $z,z^{\prime}\in\Sigma_{1}^{X(1)}$ we have

$\Delta(z,z^{\prime})\geq\delta_{0}\Rightarrow\Delta(\operatorname{lift}(z),\operatorname{lift}(z^{\prime}))\geq\delta.$

For us the most important example of lifting is when the function $g$ is
$k$-XOR and $\Sigma_{1}=\Sigma_{k}=\mathbb{F}_{2}$, which has been extensively
studied in connection with codes and otherwise [TS17, STV01, GNW95, ABN+92].
In our language of liftings, $k$-XOR corresponds to the _direct sum lifting_.

######  Definition 2.6 (Direct Sum Lifting).

Let $\mathcal{C}_{1}\subseteq{\mathbb{F}}_{2}^{n}$ be a base code on
$X(1)=[n]$. The direct sum lifting of a word $z\in{\mathbb{F}}_{2}^{n}$ on a
collection $X(k)$ is $\operatorname{dsum}_{X(k)}(z)=y$ such that
$y_{\mathfrak{s}}=\sum_{i\in\mathfrak{s}}z_{i}$ for all $\mathfrak{s}\in
X(k)$.

We will be interested in cases where the direct sum lifting reduces the bias
of the base code; in [TS17], structures with such a property are called
_parity samplers_ , as they emulate the reduction in bias that occurs by
taking the parity of random samples.

######  Definition 2.7 (Parity Sampler).

Let $g\colon\mathbb{F}_{2}^{k}\rightarrow\mathbb{F}_{2}$. We say that
$\operatorname{lift}_{X(k)}^{g}$ is an $(\beta_{0},\beta)$-parity sampler if
for all $z\in{\mathbb{F}}_{2}^{X(1)}$ with
$\operatorname{bias}(z)\leq\beta_{0}$, we have
$\operatorname{bias}(\operatorname{lift}(z))\leq\beta$.

###  2.3 Constraint Satisfaction Problems (CSPs)

A $k$-CSP instance $\mathfrak{I}(H,\mathcal{P},w)$ with alphabet size $q$
consists of a $k$-uniform hypergraph $H$, a set of constraints

$\mathcal{P}=\left\\{\mathcal{P}_{\mathfrak{a}}\subseteq[q]^{\mathfrak{a}}:\mathfrak{a}\in
H\right\\},$

and a non-negative weight function $w\in\mathbb{R}_{+}^{H}$ on the constraints
satisfying $\sum_{\mathfrak{a}\in H}w(a)=1$.

We will think of the constraints as predicates that are satisfied by an
assignment $\sigma$ if we have
$\sigma|_{\mathfrak{a}}\in\mathcal{P}_{\mathfrak{a}}$, i.e., the restriction
of $\sigma$ on $\mathfrak{a}$ is contained in $\mathcal{P}_{\mathfrak{a}}$. We
write $\mathsf{SAT}_{\mathfrak{I}}(\sigma)$ for the (weighted) fraction of the
constraints satisfied by the assignment $\sigma$, i.e.,

$\mathsf{SAT}_{\mathfrak{I}}(\sigma)~{}=~{}\sum_{\mathfrak{a}\in
H}w(\mathfrak{a})\cdot\mathbf{1}[\sigma|_{\mathfrak{a}}\in\mathcal{P}_{\mathfrak{a}}]~{}=~{}\mathchoice{\underset{\mathfrak{a}\sim
w}{\mathbb{E}}\left[\mathbf{1}[\sigma|_{\mathfrak{a}}\in\mathcal{P}_{\mathfrak{a}}]\right]}{{\mathbb{E}}_{\mathfrak{a}\sim
w}[\mathbf{1}[\sigma|_{\mathfrak{a}}\in\mathcal{P}_{\mathfrak{a}}]]}{{\mathbb{E}}_{\mathfrak{a}\sim
w}[\mathbf{1}[\sigma|_{\mathfrak{a}}\in\mathcal{P}_{\mathfrak{a}}]]}{{\mathbb{E}}_{\mathfrak{a}\sim
w}[\mathbf{1}[\sigma|_{\mathfrak{a}}\in\mathcal{P}_{\mathfrak{a}}]]}\,.$

We denote by $\mathsf{OPT}(\mathfrak{I})$ the maximum of
$\mathsf{SAT}_{\mathfrak{I}}(\sigma)$ over all $\sigma\in[q]^{V(H)}$.

A particularly important class of $k$-CSPs for our work will be $k$-XOR: here
the input consists of a $k$-uniform hypergraph $H$ with weighting $w$, and a
(right-hand side) vector $r\in{\mathbb{F}}_{2}^{H}$. The constraint for each
$\mathfrak{a}\in H$ requires

$\sum_{i\in\mathfrak{a}}\sigma(i)=r_{\mathfrak{a}}\pmod{2}.$

In this case we will use the notation $\mathfrak{I}(H,r,w)$ to refer to the
$k$-XOR instance. When the weighting $w$ is implicitly clear, we will omit it
and just write $\mathfrak{I}(H,r)$.

Any $k$-uniform hypergraph $H$ can be associated with a pure simplicial
complex in a canonical way by setting
$X_{\mathfrak{I}}=\left\\{\mathfrak{b}:\exists\ \mathfrak{a}\in
H~{}\text{with}~{}\mathfrak{a}\supseteq\mathfrak{b}\right\\}$; notice that
$X_{\mathfrak{I}}(k)=H$. We will refer to this complex as the _constraint
complex_ of the instance $\mathfrak{I}$. The probability distribution
$\Pi_{k}$ on $X_{\mathfrak{I}}(k)$ will be derived from the weight function
$w$ of the constraint:

$\Pi_{k}(\mathfrak{a})=w(\mathfrak{a})\quad\forall\mathfrak{a}\in
X_{\mathfrak{I}}(k)=H.$

###  2.4 Sum-of-Squares Relaxations and $t$-local PSD Ensembles

The Sum-of-Squares (SOS) hierarchy gives a sequence of increasingly tight
semidefinite programming relaxations for several optimization problems,
including CSPs. Since we will use relatively few facts about the SOS
hierarchy, already developed in the analysis of Barak, Raghavendra, and
Steurer [BRS11], we will adapt their notation of _$t$ -local distributions_ to
describe the relaxations. For a $k$-CSP instance
$\mathfrak{I}=(H,\mathcal{P},w)$ on $n$ variables, we consider the following
semidefinite relaxation given by $t$-levels of the SOS hierarchy, with vectors
${v}_{(S,\alpha)}$ for all $S\subseteq[n]$ with $\left\lvert S\right\rvert\leq
t$, and all $\alpha\in[q]^{S}$. Here, for $\alpha_{1}\in[q]^{S_{1}}$ and
$\alpha_{2}\in[q]^{S_{2}}$, $\alpha_{1}\circ\alpha_{2}\in[q]^{S_{1}\cup
S_{2}}$ denotes the partial assignment obtained by concatenating $\alpha_{1}$
and $\alpha_{2}$.

$\displaystyle\mbox{maximize}\quad~{}~{}\mathchoice{\underset{\mathfrak{a}\sim
w}{\mathbb{E}}\left[\sum_{\alpha\in\mathcal{P}_{\mathfrak{a}}}\lVert{v}_{(\mathfrak{a},\alpha)}\rVert^{2}\right]}{{\mathbb{E}}_{\mathfrak{a}\sim
w}[\sum_{\alpha\in\mathcal{P}_{\mathfrak{a}}}\lVert{v}_{(\mathfrak{a},\alpha)}\rVert^{2}]}{{\mathbb{E}}_{\mathfrak{a}\sim
w}[\sum_{\alpha\in\mathcal{P}_{\mathfrak{a}}}\lVert{v}_{(\mathfrak{a},\alpha)}\rVert^{2}]}{{\mathbb{E}}_{\mathfrak{a}\sim
w}[\sum_{\alpha\in\mathcal{P}_{\mathfrak{a}}}\lVert{v}_{(\mathfrak{a},\alpha)}\rVert^{2}]}$
$\displaystyle~{}=:~{}\mathsf{SDP}(\mathfrak{I})$ $\displaystyle\mbox{subject
to}\quad\quad~{}\left\langle{v}_{(S_{1},\alpha_{1})},{v}_{(S_{2},\alpha_{2})}\right\rangle$
$\displaystyle~{}=~{}0$ $\displaystyle\forall~{}\alpha_{1}|_{S_{1}\cap
S_{2}}\neq\alpha_{2}|_{S_{1}\cap S_{2}}$
$\displaystyle\left\langle{v}_{(S_{1},\alpha_{1})},{v}_{(S_{2},\alpha_{2})}\right\rangle$
$\displaystyle~{}=~{}\left\langle{v}_{(S_{3},\alpha_{3})},{v}_{(S_{4},\alpha_{4})}\right\rangle$
$\displaystyle\forall~{}S_{1}\cup S_{2}=S_{3}\cup
S_{4},~{}\alpha_{1}\circ\alpha_{2}=\alpha_{3}\circ\alpha_{4}$
$\displaystyle\sum_{j\in[q]}\lVert{v}_{(\\{i\\},j)}\rVert^{2}$
$\displaystyle~{}=~{}1$ $\displaystyle\forall i\in[n]$
$\displaystyle\lVert{v}_{(\emptyset,\emptyset)}\rVert^{2}$
$\displaystyle~{}=~{}1$

For any set $S$ with $|S|\leq t$, the vectors ${v}_{(S,\alpha)}$ induce a
probability distribution $\mu_{S}$ over $[q]^{S}$ such that the assignment
$\alpha\in[q]^{S}$ appears with probability
$\lVert{v}_{(S,\alpha)}\rVert^{2}$. Moreover, these distributions are
consistent on intersections: for $T\subseteq S\subseteq[n]$, we have
$\mu_{S|T}=\mu_{T}$, where $\mu_{S|T}$ denotes the restriction of the
distribution $\mu_{S}$ to the set $T$. We use these distributions to define a
collection of random variables $\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}$ taking
values in $[q]$, such that for any set $S$ with $\left\lvert S\right\rvert\leq
t$, the collection of variables $\left\\{\mathbf{Z}_{i}\right\\}_{i\in S}$ has
a joint distribution $\mu_{S}$. Note that the entire collection
$(\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n})$ _may not_ have a joint distribution:
this property is only true for sub-collections of size $t$. We will refer to
the collection $(\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n})$ as a _$t$ -local
ensemble_ of random variables.

We also have that that for any $T\subseteq[n]$ with $\left\lvert
T\right\rvert\leq t-2$, and any $\xi\in[q]^{T}$, we can define a
$(t-\left\lvert T\right\rvert)$-local ensemble
$(\mathbf{Z}_{1}^{\prime},\ldots,\mathbf{Z}_{n}^{\prime})$ by “conditioning”
the local distributions on the event $\mathbf{Z}_{T}=\xi$, where
$\mathbf{Z}_{T}$ is shorthand for the collection
$\left\\{\mathbf{Z}_{i}\right\\}_{i\in T}$. For any $S$ with $\left\lvert
S\right\rvert\leq t-\left\lvert T\right\rvert$, we define the distribution of
$\mathbf{Z}_{S}^{\prime}$ as $\mu_{S}^{\prime}:=\mu_{S\cup
T}|\\{\mathbf{Z}_{T}=\xi\\}$. Finally, the semidefinite program also ensures
that for any such conditioning, the conditional covariance matrix

$\mathsf{M}_{(S_{1},\alpha_{1})(S_{2},\alpha_{2})}~{}=~{}\operatorname{\operatorname{Cov}}\left(\mathbf{1}[\mathbf{Z}_{S_{1}}^{\prime}=\alpha_{1}],\mathbf{1}[\mathbf{Z}_{S_{2}}^{\prime}=\alpha_{2}]\right)$

is positive semidefinite, where $\left\lvert S_{1}\right\rvert,\left\lvert
S_{2}\right\rvert\leq(t-\left\lvert T\right\rvert)/2$. Here, for each pair
$S_{1},S_{2}$ the covariance is computed using the joint distribution
$\mu_{S_{1}\cup S_{2}}^{\prime}$. In this paper, we will only consider
$t$-local ensembles such that for every conditioning on a set of size at most
$t-2$, the conditional covariance matrix is PSD. We will refer to these as
_$t$ -local PSD ensembles_. We will also need a simple corollary of the above
definitions.

######  Fact 2.8.

Let $(\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n})$ be a $t$-local PSD ensemble, and
let $X$ be any collection with $X(1)=[n]$. Then, for all $s\leq t/2$, the
collection $\left\\{\mathbf{Z}_{\mathfrak{a}}\right\\}_{\mathfrak{a}\in X(\leq
s)}$ is a $(t/s)$-local PSD ensemble, where $X(\leq s)=\bigcup_{i=1}^{s}X(i)$.

For random variables $\mathbf{Z}_{S}$ in a $t$-local PSD ensemble, we use the
notation $\left\\{\mathbf{Z}_{S}\right\\}$ to denote the distribution of
$\mathbf{Z}_{S}$ (which exists when $\left\lvert S\right\rvert\leq t$). We
also define
$\mathchoice{{\mathrm{Var}}\left[\mathbf{Z}_{S}\right]}{{\mathrm{Var}}[\mathbf{Z}_{S}]}{{\mathrm{Var}}[\mathbf{Z}_{S}]}{{\mathrm{Var}}[\mathbf{Z}_{S}]}$
as

$\mathchoice{{\mathrm{Var}}\left[\mathbf{Z}_{S}\right]}{{\mathrm{Var}}[\mathbf{Z}_{S}]}{{\mathrm{Var}}[\mathbf{Z}_{S}]}{{\mathrm{Var}}[\mathbf{Z}_{S}]}\coloneqq\sum_{\alpha\in{[q]^{S}}}\mathchoice{{\mathrm{Var}}\left[\mathbf{1}\left[\mathbf{Z}_{S}=\alpha\right]\right]}{{\mathrm{Var}}[\mathbf{1}\left[\mathbf{Z}_{S}=\alpha\right]]}{{\mathrm{Var}}[\mathbf{1}\left[\mathbf{Z}_{S}=\alpha\right]]}{{\mathrm{Var}}[\mathbf{1}\left[\mathbf{Z}_{S}=\alpha\right]]}.$

#### Pseudo-expectation Formulation

An equivalent way of expressing this local PSD ensemble is through the use of
a pseudo-expectation operator, which is also a language commonly used in the
SOS literature (e.g., [BHK+16, BKS17]). The exposition of some of our results
is cleaner in this equivalent language. Each variable $\mathbf{Z}_{i}$ with
$i\in[n]$ is modeled by a collection of indicator local random variables
666Note that $\\{\mathbf{Z}_{i,a}\\}_{i\in[n],a\in[q]}$ are formal variables
in the SOS formulation. $\\{\mathbf{Z}_{i,a}\\}_{a\in[q]}$ with the intent
that $\mathbf{Z}_{i,a}=1$ iff $\mathbf{Z}_{i}=a$. To ensure they behave
similarly to indicators we add the following restrictions to the SOS
formulation:

$\displaystyle\mathbf{Z}_{i,a}^{2}$ $\displaystyle=\mathbf{Z}_{i,a}$
$\displaystyle\forall i\in[n],a\in[q]$
$\displaystyle\sum_{a\in[q]}\mathbf{Z}_{i,a}$ $\displaystyle=1$
$\displaystyle\forall i\in[n]$

Let $\mathcal{R}=\mathbb{R}[\mathbf{Z}_{1,1},\dots,\mathbf{Z}_{n,q}]$ be the
ring of polynomials on $\\{\mathbf{Z}_{i,a}\\}_{i\in[n],a\in[q]}$. We will
write $\mathcal{R}^{\leq d}$ for the restriction of $\mathcal{R}$ to
polynomials of degree at most $d$. A feasible solution at the $(2t)$-th level
of the SOS hierarchy is a linear operator
$\widetilde{\mathbb{E}}:\mathcal{R}^{\leq 2t}\rightarrow\mathbb{R}$ called the
pseudo-expectation operator. This operator satisfies the following problem-
independent constraints: (i) $\widetilde{\mathbb{E}}[1]=1$ (normalization) and
(ii) $\widetilde{\mathbb{E}}[P^{2}]\geq 0$ for every $P\in\mathcal{R}^{\leq
t}$ (non-negative on Sum-of-Squares) 777From condition (ii), we can recover
the PSD properties from the local PSD ensemble definition.. It also satisfies
the problem-dependent constraints

$\widetilde{\mathbb{E}}\left[\mathbf{Z}_{i,a}^{2}\cdot
P\right]=\widetilde{\mathbb{E}}\left[\mathbf{Z}_{i,a}\cdot
P\right]\qquad\text{and}\qquad\widetilde{\mathbb{E}}\left[\left(\sum_{a\in[q]}\mathbf{Z}_{i,a}\right)\cdot
Q\right]=\widetilde{\mathbb{E}}\left[Q\right],$

for every $i\in[n]$, $a\in[q]$, $P\in\mathcal{R}^{\leq 2t-2}$, and
$Q\in\mathcal{R}^{\leq 2t-1}$. Note that for any collection of local random
variables $\mathbf{Z}_{i_{1}},\dots,\mathbf{Z}_{i_{j}}$ with $j\leq 2t$ we
have the joint distribution

$\operatorname*{\mathbb{P}}(\mathbf{Z}_{i_{1}}=a_{1},\dots,\mathbf{Z}_{i_{j}}=a_{j})=\widetilde{\mathbb{E}}\left[\mathbf{Z}_{i_{1},a_{1}}\dots\mathbf{Z}_{i_{j},a_{j}}\right].$

Even though we may not have a global distribution we can implement a form of
pseudo-expectation conditioning on a random variable $\mathbf{Z}_{i}$ taking a
given value $a\in[q]$ as long as
$\operatorname*{\mathbb{P}}\left[\mathbf{Z}_{i}=a\right]=\widetilde{\mathbb{E}}[\mathbf{Z}_{i,a}]>0$.
This can be done by considering the new operator
$\widetilde{\mathbb{E}}_{|Z_{i}=a}\colon\mathcal{R}^{\leq
2t-2}\rightarrow\mathbb{R}$ defined as
$\widetilde{\mathbb{E}}_{|\mathbf{Z}_{i}=a}[\cdot]=\widetilde{\mathbb{E}}[\mathbf{Z}_{i,a}^{2}\cdot]/\widetilde{\mathbb{E}}[\mathbf{Z}_{i,a}^{2}]$,
which is a valid pseudo-expectation operator at the $(2t-2)$-th level. This
conditioning can be naturally generalized to a set of variables
$S\subseteq[n]$ with $\left\lvert S\right\rvert\leq t$ satisfying
$\mathbf{Z}_{S}=\alpha$ for some $\alpha\in[q]^{{S}}$.

### Notation

We make some systematic choices for our parameters in order to syntactically
stress their qualitative behavior.

  * -

$1/2-\varepsilon_{0}$ is a lower bound on the distance of the base code
$\mathcal{C}_{1}$.

  * -

$1/2-\varepsilon$ is a lower bound on the distance of the lifted code
$\mathcal{C}_{k}$.

  * -

$\kappa$ is a parameter that will control the list-decodability of the lifted
code $\mathcal{C}_{k}$.

  * -

$\mu,\theta,\eta$ are parameters that can be made arbitrarily small by
increasing the SOS degree and/or the quality of expansion.

  * -

$\beta,\delta$ are arbitrary error parameters.

  * -

$\lambda_{1}\geq\lambda_{2}\geq\cdots$ are the eigenvalues of a graph’s
adjacency matrix (in $[-1,1]$).

  * -

$\sigma_{1}\geq\sigma_{2}\geq\cdots$ are the singular values of a graph’s
adjacency matrix (in $[0,1]$).

SOS is an analytic tool so we will identify 888For this, we can use any
bijection from ${\mathbb{F}}_{2}\rightarrow\\{\pm 1\\}$. words over
${\mathbb{F}}_{2}$ with words over $\\{\pm 1\\}$. We also make some choices
for words and local variables to distinguish the ground space
${\mathbb{F}}_{2}^{X(1)}$ or $\\{\pm 1\\}^{X(1)}$ form the lifted space
${\mathbb{F}}_{2}^{X(k)}$ or $\\{\pm 1\\}^{X(k)}$.

  * -

$z,z^{\prime},z^{\prime\prime},\dots$ are words in the ground space
${\mathbb{F}}_{2}^{X(1)}$ or $\\{\pm 1\\}^{X(1)}$.

  * -

$y,y^{\prime},y^{\prime\prime},\dots$ are words in the lifted space
${\mathbb{F}}_{2}^{X(k)}$ or $\\{\pm 1\\}^{X(k)}$

  * -

$\mathbf{Z}\coloneqq\\{\mathbf{Z}_{1},\dots,\mathbf{Z}_{n}\\}$ is a local PSD
ensemble on the ground set $X(1)$.

  * -

$\mathbf{Y}\coloneqq\\{\mathbf{Y}_{\mathfrak{s}}\coloneqq\left(\operatorname{lift}(\mathbf{Z})\right)_{\mathfrak{s}}~{}|~{}\mathfrak{s}\in
X(k)\\}$ is a local ensemble on $X(k)$.

##  3 Proof Strategy and Organization

As discussed earlier, we view the problem of finding the closest codeword(s)
as that of finding suitable solution(s) to an instance of a CSP (which is
$k$-XOR in the case of direct sum). We now discuss some of the technical
ingredients required in the decoding procedure.

##### Unique Decoding.

Given $\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ with the
lifting function as $k$-XOR, we can view the problem of finding the closest
codeword to a given $\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ as that of finding
the unique $z\in\mathcal{C}_{1}$ satisfying the maximum number of equations of
the form $\sum_{i\in\mathfrak{s}}z_{i}=\tilde{y}_{\mathfrak{s}}\pmod{2}$, with
one equation for each $\mathfrak{s}\in X(k)$. By this property,
$y=\operatorname{dsum}(z)$ is the unique codeword of $\mathcal{C}_{k}$ closest
to $\tilde{y}$. Using the results of [AJT19], it is indeed possible to find
$z^{\prime}\in{\mathbb{F}}_{2}^{n}$ such that
$\Delta(\operatorname{dsum}(z^{\prime}),\tilde{y})\leq\Delta(\operatorname{dsum}(z),\tilde{y})+\beta$
for any $\beta>0$. We then argue that $z^{\prime}$ or its complement
$\overline{z^{\prime}}$ must be close to $z\in\mathcal{C}_{1}$, which can then
be recovered by unique decoding.

If this is not the case, then $z-z^{\prime}$ must have bias bounded away from
1, which would imply by robustness (parity sampling property of the
hypergraph) that $\operatorname{dsum}(z-z^{\prime})$ has bias close to zero,
i.e., $\Delta(\operatorname{dsum}(z),\operatorname{dsum}(z^{\prime}))\approx
1/2$. However, if $\Delta(\tilde{y},\mathcal{C}_{k})\leq\eta$, then we must
have

$\Delta(\operatorname{dsum}(z),\operatorname{dsum}(z^{\prime}))~{}\leq~{}\Delta(\operatorname{dsum}(z),\tilde{y})+\Delta(\operatorname{dsum}(z^{\prime}),\tilde{y})~{}\leq~{}2\eta+\beta\,,$

which leads to a contradiction if $\eta$ is significantly below $1/4$ and
$\beta$ is sufficiently small.

##### List Decoding.

We start by describing an abstract list decoding framework which only assumes
two general properties of a lifting $\operatorname{lift}_{X(k)}^{g}$: (i) it
is distance amplifying (robust) and (ii) it is amenable to SOS rounding
(tensorial).

Suppose $\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ is a word promised to be
$(1/2-\sqrt{\varepsilon})$-close to a lifted code
$\mathcal{C}_{k}=\operatorname{lift}(\mathcal{C}_{1})$ where $\mathcal{C}_{k}$
has distance at least $1/2-\varepsilon$ and $\mathcal{C}_{1}$ has distance at
least $1/2-\varepsilon_{0}$. By list decoding $\tilde{y}$, we mean finding a
list $\mathcal{L}\subseteq\mathcal{C}_{k}$ of all codewords
$(1/2-\sqrt{\varepsilon})$-close to $\tilde{y}$.

Our framework for list decoding $\tilde{y}$ consists of three stages. In the
first stage, we set up and solve a natural SOS program which we treat
abstractly in this discussion 999The precise SOS program used is given in
Section 6.2.. One issue with using a rounding algorithm for this relaxation to
do list decoding is that this natural SOS program may return a solution that
is “concentrated”, e.g., a SOS solution corresponding to single codeword in
$\mathcal{L}$. Such a solution will of course not have enough information to
recover the entire list. To address this issue we now ask not only for
feasibility in our SOS program but also to minimize a convex function $\Psi$
measuring how concentrated the SOS solution is. Specifically, if $\mathbf{Z}$
is the PSD ensemble corresponding to the solution of the SOS program and if
$\mathbf{Y}$ is the lifted ensemble, then we minimize
$\Psi~{}:=~{}{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\in
X(k)}\left[\left\lparen\operatorname{\widetilde{\mathbb{E}}}[{\mathbf{Y}}_{\mathfrak{s}}{\mathbf{Y}}_{\mathfrak{t}}]\right\rparen^{2}\right]$.

The key property of the function $\Psi$ is that if the SOS solution “misses”
any element in the list $\mathcal{L}$ then it is possible to decrease it.
Since our solution is a minimizer 101010Actually an approximate minimizer is
enough in our application. of $\Psi$, this is impossible. Therefore, our
solution does “cover” the list $\mathcal{L}$. Even with this SOS cover of
$\mathcal{L}$, the list decoding task is not complete. So far we have not
talked about rounding, which is necessary to extract codewords out of the
(fractional) solution. For now, we will simply assume that rounding is viable
(this is handled by the second stage of the framework) and resume the
discussion.

Unfortunately, the covering guarantee is somewhat weak, namely, for
$y\in\mathcal{L}$ we are only able to obtain a word
$y^{\prime}\in{\mathbb{F}}_{2}^{X(k)}$ with weak agreement $\left\lvert\langle
y^{\prime},y\rangle\right\rvert\geq 2\cdot\varepsilon$. Converting a word
$y^{\prime}$ from the cover into an actual codeword $y$ is the goal of the
third and final stage of the list decoding framework, dubbed Cover
Purification. At this point we resort to the robustness properties of the
lifting and the fact that we actually have “coupled” pairs
$(z,y=\operatorname{lift}(z))$ and
$(z^{\prime},y^{\prime}=\operatorname{lift}(z^{\prime}))$ for some
$z,z^{\prime}\in{\mathbb{F}}_{2}^{X(1)}$. Due to this robustness (and up to
some minor technicalities) even a weak agreement between $y$ and $y^{\prime}$
in the lifted space translates into a much stronger agreement between $z$ and
$z^{\prime}$ in the ground space. Provided the latter agreement is
sufficiently strong, $z^{\prime}$ will lie in the unique decoding ball
centered at $z$ in $\mathcal{C}_{1}$. In this case, we can uniquely recover
$z$ and thus also $y=\operatorname{lift}(z)$. Furthermore, if
$\mathcal{C}_{1}$ admits an efficient unique decoder, we can show that this
step in list decoding $\tilde{y}$ can be done efficiently.

Now we go back to fill in the rounding step, which constitutes the second
stage of the framework, called Cover Retrieval. We view the SOS solution as
composed of several “slices” from which the weak pairs
$(z^{\prime},y^{\prime})$ are to be extracted. Note that the framework
handles, in particular, $k$-XOR liftings where it provides not just a single
solution but a list of them. Hence, some structural assumption about $X(k)$ is
necessary to ensure SOS tractability. Recall that random $k$-XOR instances are
hard for SOS [Gri01, KMOW17]. For this reason, we impose a sufficient
tractability condition on $X(k)$ which we denote the two-step tensorial
property. This notion is a slight strengthening of a tensorial property which
was (implicitly) first investigated by Barak et al. [BRS11] when $k=2$ and
later generalized for arbitrary $k\geq 2$ in [AJT19]. Roughly speaking, if
$X(k)$ is tensorial then the SOS local random variables in a typical slice of
the solution behave approximately as product variables from the perspective of
the local views $\mathfrak{s}\in X(k)$. A two-step tensorial structure is a
tensorial structure in which the local random variables between pairs of local
views $\mathfrak{s},\mathfrak{t}\in X(k)$ are also close to product variables,
which is an extra property required to perform rounding in this framework.
With the two-step tensorial assumption, we are able to round the SOS solution
to obtain a list of pairs $(z^{\prime},y^{\prime})$ weakly agreeing with
elements of the code list that will be refined during cover purification.

To recapitulate, the three stages of the abstract list decoding framework are
summarized in Fig. 1 along with the required assumptions on the lifting.

SOS minimizing $\Psi$Cover RetrievalCover PurificationSOS solutioncode
coverTensorial AssumptionRobustness AssumptionCode List Figure 1: List
decoding framework with the assumptions required in each stage.

##### Finding suitable hypergraphs.

Fortunately, objects satisfying the necessary tensorial and robustness
assumptions do exist. HDXs were shown to be tensorial in [AJT19], and here we
strengthen this result to two-step tensorial as well as prove that HDXs
possess the particular robustness property of parity sampling. Walks on
expander graphs are already known to be robust [TS17], and we use a modified
version of the methods in [AJT19] to show they are also two-step tensorial.
For both HDXs and expander walks, we describe how to use known constructions
of these objects to get explicit direct sum encodings that can be decoded
using our abstract framework.

##### Reduction from direct product to direct sum.

Finally, we describe how to use list decoding results for direct sum codes to
obtain results for direct product codes. Given a direct product lifting
$\mathcal{C}_{k}$ on the hypergraph $X(k)$, if $\Delta(\tilde{y},y)\leq
1-\varepsilon$ for $y\in\mathcal{C}_{k}$, then we must have that

$\Pr_{\mathfrak{s}\in
X(k)}\left[y_{\mathfrak{s}}=\tilde{y}_{\mathfrak{s}}\right]~{}=~{}\mathchoice{\underset{\mathfrak{s}\in
X(k)}{\mathbb{E}}\left[\mathchoice{\underset{\mathfrak{t}\subseteq\mathfrak{s}}{\mathbb{E}}\left[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})\right]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}\right]}{{\mathbb{E}}_{\mathfrak{s}\in
X(k)}[\mathchoice{\underset{\mathfrak{t}\subseteq\mathfrak{s}}{\mathbb{E}}\left[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})\right]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}]}{{\mathbb{E}}_{\mathfrak{s}\in
X(k)}[\mathchoice{\underset{\mathfrak{t}\subseteq\mathfrak{s}}{\mathbb{E}}\left[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})\right]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}]}{{\mathbb{E}}_{\mathfrak{s}\in
X(k)}[\mathchoice{\underset{\mathfrak{t}\subseteq\mathfrak{s}}{\mathbb{E}}\left[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})\right]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}{{\mathbb{E}}_{\mathfrak{t}\subseteq\mathfrak{s}}[\chi_{\mathfrak{t}}(y_{\mathfrak{s}}+\tilde{y}_{\mathfrak{s}})]}]}~{}\geq~{}\varepsilon\,.$

Since $\chi_{\mathfrak{t}}(y_{\mathfrak{s}})$ can be viewed as part of a
direct sum lifting, we get by grouping subsets $\mathfrak{t}$ by size that
there must exist a size $i$ such that the direct sum lifting using $X(i)$ has
correlation at least $\varepsilon$ with the word $y^{\prime}$ defined as
$y^{\prime}_{\mathfrak{t}}=\chi_{t}(\tilde{y}_{\mathfrak{s}})$ for all
$\mathfrak{t}\in X(i)$. We can then apply the list decoding algorithm for
direct sum codes on $X(i)$. A standard concentration argument can also be used
to control the size $i$ to be approximately $k/2$.

### Organization of Results

In Section 4, we show how the direct sum lifting on HDXs can be used to reduce
bias, establishing that HDXs are parity samplers. This will give a very
concrete running example of a lifting that can be used in our framework.
Before addressing list decoding, we remark in Section 5 how this lifting can
be used in the simpler regime of unique decoding using a $k$-CSP algorithm on
expanding instances [AJT19]. The abstract list decoding framework is given in
Section 6. Next, we instantiate the framework with the direct sum lifting on
HDXs in Section 7. As an interlude between the first and second instantiation,
Section 8 describes how the first concrete instantiation of Section 7 captures
the direct product lifting on HDXs via a reduction to the direct sum lifting.
Finally, in Section 9, we show how to instantiate the framework with the
direct sum lifting on the collection of length $k-1$ walks of an expander
graph.

##  4 Pseudorandom Hypergraphs and Robustness of Direct Sum

The main robustness property we will consider is parity sampling applied to
the case of the direct sum lifting. As this section focuses on this specific
instance of a lifting, here we will say that a collection $X(k)$ is a parity
sampler if its associated direct sum lifting $\operatorname{dsum}_{X(k)}$ is a
parity sampler. Recall that for such a parity sampler, the direct sum lifting
brings the bias of a code close to zero, which means it boosts the distance
almost to 1/2.

###  4.1 Expander Walks and Parity Sampling

A known example of a parity sampler is the set $X(k)$ of all walks of length
$k$ in a sufficiently expanding graph, as shown by Ta-Shma.

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

Suppose $G$ is a graph with second largest singular 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.

Our goal in this section is to prove a similar result for high-dimensional
expanders, where $X(k)$ is the set of $k$-sized faces.

###  4.2 High-dimensional Expanders

A high-dimensional expander (HDX) is a particular kind of simplicial complex
satisfying an expansion requirement. We recall the notion of high-dimensional
expansion considered in [DK17]. For a complex $X(\leq d)$ and $\mathfrak{s}\in
X(i)$ for some $i\in[d]$, we denote by $X_{\mathfrak{s}}$ the _link complex_

$X_{\mathfrak{s}}~{}:=~{}\left\\{\mathfrak{t}\backslash\mathfrak{s}\mid\mathfrak{s}\subseteq\mathfrak{t}\in
X\right\\}\,.$

When $\left\lvert\mathfrak{s}\right\rvert\leq d-2$, we also associate a
natural weighted graph $G(X_{\mathfrak{s}})$ to a link $X_{\mathfrak{s}}$,
with vertex set $X_{\mathfrak{s}}(1)$ and edge set $X_{\mathfrak{s}}(2)$. The
edge weights are taken to be proportional to the measure $\Pi_{2}$ on the
complex $X_{\mathfrak{s}}$, which is in turn proportional to the measure
$\Pi_{\left\lvert\mathfrak{s}\right\rvert+2}$ on $X$. The graph
$G(X_{\mathfrak{s}})$ is referred to as the _skeleton_ of $X_{\mathfrak{s}}$.

Dinur and Kaufman [DK17] define high-dimensional expansion in terms of
spectral expansion of the skeletons of the links.

######  Definition 4.2 ($\gamma$-HDX from [DK17]).

A simplicial complex $X(\leq d)$ is said to be $\gamma$-High Dimensional
Expander ($\gamma$-HDX) if for every $0\leq i\leq d-2$ and for every
$\mathfrak{s}\in X(i)$, the graph $G(X_{\mathfrak{s}})$ satisfies
$\sigma_{2}(G(X_{\mathfrak{s}}))\leq\gamma$.

We will need the following theorem relating $\gamma$ to the spectral
properties of the graph between two layers of an HDX.

######  Theorem 4.3 (Adapted from [DK17]).

Let $X$ be a $\gamma$-HDX and let $M_{1,d}$ be the weighted bipartite
containment graph between $X(1)$ and $X(d)$, where each edge
$(\\{i\\},\mathfrak{s})$ has weight $(1/d)\Pi_{d}(\mathfrak{s})$. Then the
second largest singular value $\sigma_{2}$ of $M_{1,d}$ satisfies

$\sigma_{2}^{2}\leq\frac{1}{d}+O(d\gamma).$

We will be defining codes using HDXs by associating each face in some $X(i)$
with a position in the code. The distance between two codewords does not take
into account any weights on their entries, which will be problematic when
decoding since the distributions $\Pi_{i}$ are not necessarily uniform. To
deal with this issue, we will work with HDXs where the distributions $\Pi_{i}$
satisfy a property only slightly weaker than uniformity.

######  Definition 4.4 (Flatness (from [DHK+19])).

We say that a distribution $\Pi$ on a finite probability space $\Omega$ is
$D$-flat if there exits $N$ such that each singleton $\omega\in\Omega$ has
probability in $\\{1/N,\dots,D/N\\}$.

Using the algebraically deep construction of Ramanujan complexes by Lubotzky,
Samuels, and Vishne [LSV05b, LSV05a], Dinur and Kaufman [DK17] showed that
sparse $\gamma$-HDXs do exist, with flat distributions on their sets of faces.
The following lemma from [DHK+19] is a refinement of [DK17].

######  Lemma 4.5 (Extracted from [DHK+19]).

For every $\gamma>0$ and every $d\in\mathbb{N}$ there exists an explicit
infinite family of bounded degree $d$-sized complexes which are $\gamma$-HDXs.
Furthermore, there exists a $D\leq(1/\gamma)^{O(d^{2}/\gamma^{2})}$ such that

$\frac{|X(d)|}{|X(1)|}~{}\leq~{}D,$

the distribution $\Pi_{1}$ is uniform, and the other distributions
$\Pi_{d},\dots,\Pi_{2}$ are $D$-flat.

For a $D$-flat distribution $\Pi_{i}$, we can duplicate each face in $X(i)$ at
most $D$ times to make $\Pi_{i}$ the same as a uniform distribution on this
multiset. We will always perform such a duplication implicitly when defining
codes on $X(i)$.

###  4.3 HDXs are Parity Samplers

To prove that sufficiently expanding HDXs are parity samplers, we establish
some properties of the complete complex and then explore the fact that HDXs
are locally complete 111111This a recurring theme in the study of HDXs
[DK17].. We first show that the expectation over $k$-sized faces of a complete
complex $X$ on $t$ vertices approximately splits into a product of $k$
expectations over $X(1)$ provided $t\gg k^{2}$.

######  Claim 4.6 (Complete complex and near independence).

Suppose $X$ is the complete complex of dimension at least $k$ with $\Pi_{k}$
uniform over $X(k)$ and $\Pi_{1}$ uniform over $X(1)=[t]$. For a function
$f:X(1)\rightarrow{\mathbb{R}}$, let

$\mu_{k}={\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}\left[\prod_{i\in\mathfrak{s}}f(i)\right]\qquad\text{and}\qquad\mu_{1}={\mathbb{E}}_{i\sim\Pi_{1}}\left[f(i)\right].$

Then

$\left\lvert\mu_{k}-\mu_{1}^{k}\right\rvert\leq\frac{k^{2}}{t}\left\lVert
f\right\rVert_{\infty}^{k}.$

###### Proof.

Let $\mathcal{E}=\\{(i_{1},\dots,i_{k})\in X(1)^{k}\mid
i_{1},\dots,i_{k}\text{ are distinct}\\}$,
$\delta=\operatorname*{\mathbb{P}}_{i_{1},\dots,i_{k}\sim\Pi_{1}}[(i_{1},\dots,i_{k})\notin\mathcal{E}]$,
and $\eta={\mathbb{E}}_{(i_{1},\dots,i_{k})\in
X(1)^{k}\setminus\mathcal{E}}[f(i_{1})\cdots f(i_{k})]$. Then

$\displaystyle\mu_{1}^{k}$
$\displaystyle={\mathbb{E}}_{i_{1},\dots,i_{k}\sim\Pi_{1}}[f(i_{1})\cdots
f(i_{k})]$
$\displaystyle=(1-\delta)\cdot{\mathbb{E}}_{(i_{1},\dots,i_{k})\in\mathcal{E}}[f(i_{1})\cdots
f(i_{k})]+\delta\cdot{\mathbb{E}}_{(i_{1},\dots,i_{k})\in
X(1)^{k}\setminus\mathcal{E}}[f(i_{1})\cdots f(i_{k})]$
$\displaystyle=(1-\delta)\cdot\mu_{k}+\delta\cdot\eta,$

where the last equality follows since $\Pi_{k}$ is uniform and the product in
the expectation is symmetric. As $i_{1},\dots,i_{k}$ are sampled independently
from $\Pi_{1}$, which is uniform over $X(1)$,

$\delta=1-\prod_{j<k}\left(1-\frac{j}{t}\right)\leq\sum_{j<k}\frac{j}{t}=\frac{k(k-1)}{2t},$

so we have

$\left\lvert\mu_{k}-\mu_{1}^{k}\right\rvert=\delta\left\lvert\mu_{k}-\eta\right\rvert\leq\frac{k^{2}}{2t}\left(2\left\lVert
f\right\rVert_{\infty}^{k}\right).$

We will derive parity sampling for HDXs from their behavior as samplers. A
sampler is a structure in which the average of any function on a typical local
view is close to its overall average. More precisely, we have the following
definition.

######  Definition 4.7 (Sampler).

Let $G=(U,V,E)$ be a bipartite graph with a probability distribution $\Pi_{U}$
on $U$. Let $\Pi_{V}$ be the distribution on $V$ obtained by choosing $u\in U$
according to $\Pi_{U}$, then a uniformly random neighbor $v$ of $u$. We say
that $G$ is an $(\eta,\delta)$-sampler if for every function $f\colon
V\rightarrow[0,1]$ with $\mu={\mathbb{E}}_{v\sim\Pi_{V}}f(v)$,

$\operatorname*{\mathbb{P}}_{u\sim\Pi_{U}}\left[\left|{\mathbb{E}}_{v\sim
u}[f(v)]-\mu\right|\geq\eta\right]~{}\leq~{}\delta.$

To relate parity sampling to spectral expansion, we use the following fact
establishing that samplers of arbitrarily good parameters $(\eta,\delta)$ can
be obtained from sufficiently expanding bipartite graphs. This result is
essentially a corollary of the expander mixing lemma.

######  Fact 4.8 (From Dinur et al. [DHK+19]).

A weighted bipartite graph with second singular value $\sigma_{2}$ is an
$(\eta,\sigma_{2}^{2}/\eta^{2})$-sampler.

Using 4.6, we show that the graph between $X(1)$ and $X(k)$ obtained from a
HDX is a parity sampler, with parameters determined by its sampling
properties.

######  Claim 4.9 (Sampler bias amplification).

Let $X(\leq d)$ be a HDX such that the weighted bipartite graph $M_{1,d}$
between $X(1)=[n]$ and $X(d)$ is an $(\eta,\delta)$-sampler. For any $1\leq
k\leq d$, if $z\in{\mathbb{F}}_{2}^{n}$ has bias at most $\beta_{0}$, then

$\operatorname{bias}(\operatorname{dsum}_{X(k)}(z))\leq(\beta_{0}+\eta)^{k}+\frac{k^{2}}{d}+\delta.$

###### Proof.

By downward closure, the subcomplex $X|_{\mathfrak{t}}$ obtained by
restricting to edges contained within some $\mathfrak{t}\in X(d)$ is a
complete complex on the ground set $\mathfrak{t}$. Since $M_{1,d}$ is an
$(\eta,\delta)$-sampler, the bias of $z|_{\mathfrak{t}}$ must be within $\eta$
of $\operatorname{bias}(z)$ on all but $\delta$ fraction of the edges
$\mathfrak{t}$. Hence

$\displaystyle\operatorname{bias}(\operatorname{dsum}_{X(k)}(z))$
$\displaystyle=\left\lvert{\mathbb{E}}_{\\{i_{1},\dots,i_{k}\\}\sim\Pi_{k}}(-1)^{z_{i_{1}}+\dots+z_{i_{k}}}\right\rvert$
$\displaystyle=\left\lvert{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{d}}{\mathbb{E}}_{\\{i_{1},\dots,i_{k}\\}\in
X|_{\mathfrak{t}}(k)}(-1)^{z_{i_{1}}+\dots+z_{i_{k}}}\right\rvert$
$\displaystyle\leq\left\lvert{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{d}}{\mathbb{E}}_{\\{i_{1},\dots,i_{k}\\}\in
X|_{\mathfrak{t}}(k)}(-1)^{z_{i_{1}}+\dots+z_{i_{k}}}\mathbb{1}_{[\operatorname{bias}(z|_{\mathfrak{t}})\leq\beta_{0}+\eta]}\right\rvert$
$\displaystyle\qquad+\operatorname*{\mathbb{P}}_{t\sim\Pi_{d}}[\operatorname{bias}(z|_{\mathfrak{t}})>\beta_{0}+\eta]$
$\displaystyle\leq{\mathbb{E}}_{\mathfrak{t}\sim\Pi_{d}}\mathbb{1}_{[\operatorname{bias}(z|_{\mathfrak{t}})\leq\beta_{0}+\eta]}\left\lvert{\mathbb{E}}_{\\{i_{1},\dots,i_{k}\\}\in
X|_{\mathfrak{t}}(k)}(-1)^{z_{i_{1}}+\dots+z_{i_{k}}}\right\rvert+\delta.$

By 4.6, the magnitude of the expectation of $(-1)^{z_{i}}$ over the edges of
size $k$ in the complete complex $X|_{\mathfrak{t}}$ is close to
$\left\lvert{\mathbb{E}}_{i\sim
X|_{\mathfrak{t}}(1)}(-1)^{z_{i}}\right\rvert$, which is just the bias of
$z|_{\mathfrak{t}}$. Then

$\displaystyle\operatorname{bias}(\operatorname{dsum}_{X(k)}(z))$
$\displaystyle\leq{\mathbb{E}}_{\mathfrak{t}\sim
X(d)}\mathbb{1}_{[\operatorname{bias}(z|_{\mathfrak{t}})\leq\beta_{0}+\eta]}\operatorname{bias}(z|_{\mathfrak{t}})^{k}+\frac{k^{2}}{d}+\delta$
$\displaystyle\leq\left(\beta_{0}+\eta\right)^{k}+\frac{k^{2}}{d}+\delta$

Now we can compute the parameters necessary for a HDX to be an
$(\beta_{0},\beta)$-parity sampler for arbitrarily small $\beta$.

######  Lemma 4.10 (HDXs are parity samplers).

Let $0<\beta\leq\beta_{0}<1$, $0<\theta<(1/\beta_{0})-1$, and
$k\geq\log_{(1+\theta)\beta_{0}}(\beta/3)$. If $X(\leq d)$ is a $\gamma$-HDX
with $d\geq\max\\{3k^{2}/\beta,6/(\theta^{2}\beta_{0}^{2}\beta)\\}$ and
$\gamma=O\left(1/d^{2}\right)$, then $X(k)$ is a $(\beta_{0},\beta)$-parity
sampler.

###### Proof.

Suppose the graph $M_{1,d}$ between $X(1)$ and $X(d)$ is an
$(\eta,\delta)$-sampler. We will choose $d$ and $\gamma$ so that
$\eta=\theta\beta_{0}$ and $\delta=\beta/3$. Using 4.8 to obtain a sampler
with these parameters, we need the second singular value $\sigma_{2}$ of
$M_{1,d}$ to be bounded as

$\sigma_{2}\leq\theta\beta_{0}\sqrt{\frac{\beta}{3}}.$

By the upper bound on $\sigma_{2}^{2}$ from Theorem 4.3, it suffices to have

$\frac{1}{d}+O\left(d\gamma\right)\leq\frac{\theta^{2}\beta_{0}^{2}\beta}{3},$

which is satisfied by taking $d\geq
6/\left(\theta^{2}\beta_{0}^{2}\beta\right)$ and
$\gamma=O\left(1/d^{2}\right)$.

By 4.9, $X(k)$ is a $(\beta_{0},(\beta_{0}+\eta)^{k}+k^{2}/d+\delta)$-parity
sampler. The first term in the bias is
$(\beta_{0}+\eta)^{k}=((1+\theta)\beta_{0})^{k}$, so we require
$(1+\theta)\beta_{0}<1$ to amplify the bias by making $k$ large. To make this
term smaller than $\beta/3$, $k$ must be at least
$\log_{(1+\theta)\beta_{0}}{\left(\beta/3\right)}$. We already chose
$\delta=\beta/3$, so ensuring $d\geq 3k^{2}/\beta$ gives us a
$(\beta_{0},\beta)$-parity sampler.

###  4.4 Rate of the Direct Sum Lifting

By applying the direct sum lifting on a HDX to a base code $\mathcal{C}_{1}$
with bias $\beta_{0}$, parity sampling allows us to obtain a code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ with arbitrarily
small bias $\beta$ at the cost of increasing the length of the codewords. The
following lemma gives a lower bound on the rate of the lifted code
$\mathcal{C}_{k}$.

######  Lemma 4.11 (Rate of direct sum lifting for a HDX).

Let $\beta_{0}\in(0,1)$ and $\theta\in(0,(1/\beta_{0})-1)$ be constants, and
let $\mathcal{C}_{1}$ be an $\beta_{0}$-biased binary linear code with
relative rate $r_{1}$. For $\beta\in(0,\beta_{0}]$, suppose $k$, $d$, and
$\gamma$ satisfy the hypotheses of Lemma 4.10, with $k$ and $d$ taking the
smallest values that satisfy the lemma. The relative rate $r_{k}$ of the code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ with bias
$\beta$ constructed on a HDX with these parameters satisfies

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

If $\gamma=C/d^{2}$ for some constant $C$, then this becomes

$r_{k}\geq
r_{1}\cdot\left(\frac{\beta^{2}}{(\log(1/\beta))^{4}}\right)^{O((\log(1/\beta))^{12}/\beta^{6})}.$

###### Proof.

Performing the lifting from $\mathcal{C}_{1}$ to $\mathcal{C}_{k}$ does not
change the dimension of the code, but it does increase the length of the
codewords from $n$ to $|X(k)|$, where $|X(k)|$ is the size of the multiset of
edges of size $k$ after each edge has been copied a number of times
proportional to its weight. Using the bound and flatness guarantee from Lemma
4.5, we can compute

$r_{k}=\frac{r_{1}n}{|X(k)|}\geq\frac{r_{1}}{D^{2}},$

where $D\leq(1/\gamma)^{O(d^{2}/\gamma^{2})}$. Treating $\beta_{0}$ and
$\theta$ as constants, the values of $k$ and $d$ necessary to satisfy Lemma
4.10 are

$k=\log_{(1+\theta)\beta_{0}}(\beta/3)=O(\log(1/\beta))$

and

$d=\max\left\\{\frac{3k^{2}}{\beta},\frac{6}{\theta^{2}\beta_{0}^{2}\beta}\right\\}=O\left(\frac{(\log(1/\beta))^{2}}{\beta}\right).$

Putting this expression for $d$ into the inequality for $D$ yields

$D\leq(1/\gamma)^{O((\log(1/\beta))^{4}/(\beta^{2}\gamma^{2}))},$

from which the bounds in the lemma statement follow.

From Lemma 4.11, we see that if $\mathcal{C}_{1}$ has constant rate, then
$\mathcal{C}_{k}$ has a rate which is constant with respect to $n$. However,
the dependence of the rate on the bias $\beta$ is quite poor. This is
especially striking in comparison to the rate achievable using Ta-Shma’s
expander walk construction described in Section 4.1.

######  Lemma 4.12 (Rate of direct sum lifting for expander walks [TS17]).

Let $\beta_{0}\in(0,1)$ be a constant and $\mathcal{C}_{1}$ be an
$\beta_{0}$-biased binary linear code with relative rate $r_{1}$. Fix
$\beta\in(0,\beta_{0}]$. Suppose $G$ is a graph with second largest singular
value $\lambda=\beta_{0}/2$ and degree $d\leq 4/\lambda^{2}$. Let
$k=2\log_{2\beta_{0}}(\beta)+1$ and $X(k)$ be the set of all walks of length
$k$ on $G$. Then the direct sum lifting
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ has bias $\beta$
and rate $r_{k}\geq r_{1}\cdot\beta^{O(1)}$.

###### Proof.

From Theorem 4.1 with this choice of $\lambda$ and $k$, the direct sum lifting
$\mathcal{C}_{k}$ has bias $\beta$. For the rate, observe that the lifting
increases the length of the codewords from $n$ to the number of walks of
length $k$ on $G$, which is $nd^{k}$. Thus the rate of $\mathcal{C}_{k}$ is

$r_{k}=\frac{r_{1}n}{nd^{k}}=\frac{r_{1}}{d^{k}}$

As $d\leq 16/\beta_{0}$, which is a constant, and $k=O(\log(1/\beta))$, the
rate satisfies $r_{k}\geq r_{1}\cdot\beta^{O(1)}$.

##  5 Unique Decoding

In this section, we will show how parity sampling and the ability to solve
$k$-XOR instances with $X(k)$ as their constraint complex allow us to decode
the direct sum lifting
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ of a linear base
code $\mathcal{C}_{1}\in{\mathbb{F}}_{2}^{n}$. With a more technical argument,
we can also handle different kinds of liftings and non-linear codes, but for
clarity of exposition we restrict our attention to the preceding setting.

###  5.1 Unique Decoding on Parity Samplers

Our approach to unique decoding for $\mathcal{C}_{k}$ is as follows. Suppose a
received word $\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ is close to
$y^{\star}\in\mathcal{C}_{k}$, which is the direct sum lifting of some
$z^{\star}\in\mathcal{C}_{1}$ on $X(k)$. We first find an approximate solution
$z\in{\mathbb{F}}_{2}^{n}$ to the $k$-XOR instance
$\mathfrak{I}(X(k),\tilde{y})$ with predicates

$\sum_{i\in\mathfrak{s}}z_{i}={\tilde{y}}_{\mathfrak{s}}\pmod{2}$

for every $\mathfrak{s}\in X(k)$. Note that $z$ being an approximate solution
to $\mathfrak{I}(X(k),\tilde{y})$ is equivalent to its lifting
$\operatorname{dsum}_{X(k)}(z)$ being close to $\tilde{y}$. In Lemma 5.1, we
show that if $\operatorname{dsum}_{X(k)}$ is a sufficiently strong parity
sampler, either $z$ or its complement $\overline{z}$ will be close to
$z^{\star}$. Running the unique decoding algorithm for $\mathcal{C}_{1}$ on
$z$ and $\overline{z}$ will recover $z^{\star}$, from which we can obtain
$y^{\star}$ by applying the direct sum lifting.

######  Lemma 5.1.

Let $0<\varepsilon<1/2$ and $0<\beta<1/4-\varepsilon/2$. Suppose
$\mathcal{C}_{1}$ is a linear code that is efficiently uniquely decodable
within radius $1/4-\mu_{0}$ for some $\mu_{0}>0$, and
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ where
$\operatorname{dsum}_{X(k)}$ is a $(1/2+2\mu_{0},2\varepsilon)$-parity
sampler. Let $\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ be a word that has distance
strictly less than $(1/4-\varepsilon/2-\beta)$ from $\mathcal{C}_{k}$, and let
$y^{\star}=\operatorname{dsum}_{X(k)}(z^{\star})\in\mathcal{C}_{k}$ be the
word closest to $\tilde{y}$.

Then, for any $z\in{\mathbb{F}}_{2}^{n}$ satisfying

$\Delta(\operatorname{dsum}_{X(k)}(z),\tilde{y})<\frac{1}{4}-\frac{\varepsilon}{2},$

we have either

$\Delta(z^{\star},z)\leq\frac{1}{4}-\mu_{0}~{}~{}\textrm{ or
}~{}~{}\Delta(z^{\star},\overline{z})\leq\frac{1}{4}-\mu_{0}.$

In particular, either $z$ or $\overline{z}$ can be efficiently decoded in
$\mathcal{C}_{1}$ to obtain $z^{\star}\in\mathcal{C}_{1}$.

######  Remark 5.2.

Since $\operatorname{dsum}_{X(k)}$ is a $(1/2+2\mu_{0},2\varepsilon)$-parity
sampler, the code $\mathcal{C}_{k}$ has distance $\Delta(\mathcal{C}_{k})\geq
1/2-\varepsilon$. This implies that $z^{\star}\in\mathcal{C}_{1}$ is unique,
since its direct sum lifting $y^{\star}$ is within distance
$\Delta(\mathcal{C}_{k})/2$ of $\tilde{y}$.

###### Proof.

Let $y=\operatorname{dsum}_{X(k)}(z)$. We have

$\Delta(y^{\star},y)\leq\Delta(y^{\star},\tilde{y})+\Delta(y,\tilde{y})<\frac{1}{2}-\varepsilon.$

By linearity of $\operatorname{dsum}_{X(k)}$,
$\Delta(\operatorname{dsum}_{X_{k}}(z^{\star}-z),0)<1/2-\varepsilon$, so
$\operatorname{bias}(\operatorname{dsum}_{k}(z^{\star}-z))>2\varepsilon$. From
the $(1/2+2\mu_{0},2\varepsilon)$-parity sampling assumption,
$\operatorname{bias}(z^{\star}-z)>1/2+2\mu_{0}$. Translating back to distance,
either $\Delta(z^{\star},z)<1/4-\mu_{0}$ or $\Delta(z^{\star},z)>3/4+\mu_{0}$,
the latter being equivalent to $\Delta(z^{\star},\overline{z})<1/4-\mu_{0}$.

To complete the unique decoding algorithm, we need only describe how a good
enough approximate solution $z\in\mathbb{F}_{2}^{n}$ to a $k$-XOR instance
$\mathfrak{I}(X(k),\tilde{y})$ allows us to recover
$z^{\star}\in\mathcal{C}_{1}$ provided $\tilde{y}$ is sufficiently close to
$\mathcal{C}_{k}$.

######  Corollary 5.3.

Suppose $\mathcal{C}_{1}$, $X(k)$, $z^{\star}$, $y^{\star}$ and $\tilde{y}$
are as in the assumptions of Lemma 5.1. If $z\in\mathbb{F}_{2}^{n}$ is such
that

$\mathsf{SAT}_{\mathfrak{I}(X(k),\tilde{y})}(z)\geq\mathsf{OPT}_{\mathfrak{I}(X(k),\tilde{y})}-\beta,$

then unique decoding either $z$ or $\overline{z}$ gives
$z^{\star}\in\mathcal{C}_{1}$. Furthermore, if such a $z$ can be found
efficiently, so can $z^{\star}$.

###### Proof.

By the assumption on $z$, we have

$\displaystyle 1-\Delta(\operatorname{dsum}_{X(k)}(z),\tilde{y})$
$\displaystyle=\mathsf{SAT}_{\mathfrak{I}(X(k),\tilde{y})}(z)$
$\displaystyle\geq\mathsf{OPT}_{\mathfrak{I}(X(k),\tilde{y})}-\beta$
$\displaystyle\geq\mathsf{SAT}_{\mathfrak{I}(X(k),\tilde{y})}(z^{\star})-\beta$
$\displaystyle=1-\Delta(y^{\star},\tilde{y})-\beta,$

implying
$\Delta(\operatorname{dsum}_{X(k)}(z),\tilde{y})\leq\Delta(y^{\star},\tilde{y})+\beta$.
Using the assumption that $\tilde{y}$ has distance strictly less than
$(1/4-\varepsilon/2-\beta)$ from $\mathcal{C}_{k}$, we get that
$\Delta(\operatorname{dsum}_{X(k)}(z),\tilde{y})<1/4-\varepsilon/2$, in which
case we satisfy all of the conditions required for Lemma 5.1.

###  5.2 Concrete Instantiations

#### High Dimensional Expanders

If $X(k)$ is the collection of $k$-faces of a sufficiently expanding
$\gamma$-HDX, we can use the following algorithm to approximately solve the
$k$-XOR instance $\mathfrak{I}(X(k),\tilde{y})$ and obtain
$z\in{\mathbb{F}}_{2}^{n}$.

######  Theorem 5.4 ([AJT19]).

Let $\mathfrak{I}$ be an instance of MAX k-CSP on $n$ variables taking values
over an alphabet of size $q$, and let $\beta>0$. Let the simplicial complex
$X_{\mathfrak{I}}$ be a $\gamma$-HDX with
$\gamma=\beta^{O(1)}\cdot(1/(kq))^{O(k)}$.

There is an algorithm based on $(k/\beta)^{O(1)}\cdot q^{O(k)}$ levels of the
Sum-of-Squares hierarchy which produces an assignment satisfying at least an
$(\mathsf{OPT}_{\mathfrak{I}}-\beta)$ fraction of the constraints in time
$n^{(k/\beta)^{O(1)}\cdot q^{O(k)}}$.

If $X$ is a HDX with the parameters necessary to both satisfy this theorem and
be a $(1/2+2\mu_{0},2\varepsilon)$ parity sampler, we can combine this with
Corollary 5.3 to achieve efficient unique decodability of
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$.

######  Corollary 5.5.

Let $X(\leq d)$ be a $d$-dimensional $\gamma$-HDX satisfying the premises of
Lemma 4.10 that would guarantee that $X(k)$ is a
$(1/2+2\mu_{0},2\varepsilon)$-parity sampler, and let
$\mathcal{C}_{1}\subseteq{\mathbb{F}}_{2}^{n}$ be a linear code which is
efficiently unique decodable within radius $1/4-\mu_{0}$ for some $\mu_{0}>0$.
Then the code $\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$
can be unique decoded within distance $1/4-\varepsilon/2-\beta$ in time
$n^{(k/\beta)^{O(1)}\cdot 2^{O(k)}},$121212Here we are assuming that uniquely
decoding $\mathcal{C}_{1}$ within radius $1/4-\mu_{0}$ takes time less than
this. where we have

$\beta=(\gamma\cdot(2k)^{O(k)})^{\frac{1}{O(1)}}.$

###### Proof.

By Lemma 4.10, we can achieve $(1/2+2\mu_{0},2\varepsilon)$-parity sampling by
taking $0<\theta<\frac{2}{1+4\mu_{0}}-1$,
$k\geq\log_{(1+\theta)\cdot(\frac{1}{2}+2\mu_{0})}(2\varepsilon/3)$,
$d\geq\max\left\\{\frac{3k^{2}}{2\varepsilon},\frac{3}{\theta^{2}(1/2+2\mu_{0})^{2}\varepsilon}\right\\}$,
and $\gamma=O(1/d^{2})$. Let $\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ be a
received word with distance less than $(1/4-\varepsilon/2-\beta)$ from
$\mathcal{C}_{k}$. Applying Theorem 5.4 to $\mathfrak{I}(X(k),\tilde{y})$ with
$q=2$ and the given value of $\beta$, we obtain a $z\in{\mathbb{F}}_{2}^{n}$
with
$\mathsf{SAT}_{\mathfrak{I}(X(k),\tilde{y})}(z)\geq\mathsf{OPT}_{\mathfrak{I}(X(k),\tilde{y})}-\beta$.
This $z$ can be used in Corollary 5.3 to find $z^{*}$ and uniquely decode
$\tilde{y}$ as $y^{*}=\operatorname{dsum}_{X(k)}(z^{*})$.

#### Expander Walks

In Section 9, we will show that the algorithmic results of [AJT19] can be
modified to work when $X(k)$ is a set of tuples of size $k$ which is
sufficiently splittable (Corollary 9.21), which occurs when $X(k)$ is a set of
walks on on a suitably strong expander (Corollary 9.18). In particular, we
have the following.

######  Theorem 5.6.

Let $G=(V,E)$ be a graph with $\sigma_{2}(G)=\lambda$ and $k$ be a given
parameter. Let $\mathfrak{I}$ be a $k$-CSP instance over an alphabet of size
$q$ whose constraint graph is the set of walks on $G$ of length $k$. Let
$\beta>0$ be such that $\lambda=O(\beta^{2}/(k^{2}\cdot q^{2k}))$.

There exists an algorithm based on
$O\left\lparen\frac{q^{4k}k^{7}}{\beta^{5}}\right\rparen$ levels of the Sum-
of-Squares hierarchy which produces an assignment satisfying at least an
$(\mathsf{OPT}_{\mathfrak{I}}-\beta)$ fraction of the constraints in time
$n^{O(q^{4k}\cdot k^{7}/\beta^{5})}$.

Using this result, one can efficiently unique decode
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ when $X(k)$ is
the set of walks of length $k$ on an expander strong enough to achieve the
necessary parity sampling property.

######  Corollary 5.7.

Let $X(k)$ be the set of walks on a graph $G$ with $\sigma_{2}(G)=\lambda$
such that $\operatorname{dsum}_{X(k)}$ is a $(1/2+2\mu_{0},2\varepsilon)$
parity sampler, and let $\mathcal{C}_{1}\subseteq{\mathbb{F}}_{2}^{n}$ be a
linear code which is efficiently unique decodable within radius $1/4-\mu_{0}$
for some $\mu_{0}>0$. Then the code
$\mathcal{C}_{k}=\operatorname{dsum}_{X(k)}(\mathcal{C}_{1})$ can be unique
decoded within radius $1/4-\varepsilon/2-\beta$ in time $n^{O(2^{4k}\cdot
k^{7}/\beta^{5})}$, where we have

$\beta=O(\lambda\cdot k^{2}\cdot 2^{k}).$

###### Proof.

By Theorem 4.1, we can obtain a $(1/2+2\mu_{0},2\varepsilon)$-parity sampler
by ensuring $1/2+\mu_{0}+2\lambda<1$ and $k\geq
2\log_{1/2+\mu_{0}+2\lambda}(2\varepsilon)+1$. Let
$\tilde{y}\in{\mathbb{F}}_{2}^{X(k)}$ be a received word with distance less
than $(1/4-\varepsilon/2-\beta)$ from $\mathcal{C}_{k}$. Applying Theorem 5.6
to $\mathfrak{I}(X(k),\tilde{y})$ with $q=2$ and the given value of $\beta$,
we obtain a $z\in{\mathbb{F}}_{2}^{n}$ with
$\mathsf{SAT}_{\mathfrak{I}(X(k),\tilde{y})}(z)\geq\mathsf{OPT}_{\mathfrak{I}(X(k),\tilde{y})}-\beta$.
This $z$ can be used in Corollary 5.3 to find $z^{*}$ and uniquely decode
$\tilde{y}$ as $y^{*}=\operatorname{dsum}_{X(k)}(z^{*})$.

######  Remark 5.8.

In both Corollary 5.5 and Corollary 5.7, when $\mu_{0}$ and $\varepsilon$ are
constants, $k$ can be constant, which means we can decode $\mathcal{C}_{k}$
from a radius arbitrarily close to $1/4-\varepsilon/2$ if we have strong
enough guarantees on the quality of the expansion of the high-dimensional
expander or the graph, respectively.

Notice, however, that the unique decodability radius of the code
$\mathcal{C}_{k}$ is potentially larger than $1/4-\varepsilon/2$. Our choice
of $(1/2+2\mu_{0},2\varepsilon)$-parity sampling is needed to ensure that the
approximate $k$-CSP solutions lie within the unique decoding radius of
$\mathcal{C}_{1}$. Since the bias of the code $\mathcal{C}_{1}$ will generally
be smaller than the parity sampling requirement of $1/2+2\mu_{0}$, the bias of
the code $\mathcal{C}_{k}$ will be smaller than $2\varepsilon$. In this case,
the maximum distance at which our unique decoding algorithm works will be
smaller than $\Delta(\mathcal{C}_{k})/2$.

##  6 Abstract List Decoding Framework

In this section, we present the abstract list decoding framework with its
requirements and prove its guarantees. We introduce the entropic proxy $\Psi$
in Section 6.1 and use it to define the SOS program for list decoding in
Section 6.2. In Section 6.3, we establish key properties of $\Psi$ capturing
its importance as a list decoding tool. We recall the Propagation Rounding
algorithm in Section 6.4 and formalize the notion of a slice as a set of
assignments to variables in the algorithm. Then, considerations of SOS
tractability of the lifting related to tensorial properties are dealt with in
Section 6.5. Now, assuming we have a fractional SOS solution to our program,
the analysis of its covering properties and the precise definition and
correctness of the two later stages of the framework are given in Section 6.6.
This abstract framework will be instantiated using the direct sum lifting: on
HDXs in Section 7 and on expander walks in Section 9.

###  6.1 Entropic Proxy

In our list decoding framework via SOS, we will solve a single optimization
program whose resulting pseudo-expectation will in a certain sense be rich
enough to cover all intended solutions at once. To enforce this covering
property we rely on an analytical artifice, namely, we minimize a convex
function $\Psi$ that provides a proxy to how concentrated the SOS solution is.
More precisely, we use $\Psi$ from Definition 6.1. A similar list decoding
technique was also (independently) used by Karmalkar et al. [KKK19] and
Raghavendra–Yau [RY20], but in the context of learning.

######  Definition 6.1 (Entropic Proxy).

Let $\mathbf{Y}=\\{\mathbf{Y}_{\mathfrak{s}}\\}_{\mathfrak{s}\in X(k)}$ be a
$t$-local PSD ensemble with $t\geq 2$. We define
$\Psi=\Psi\left(\\{\mathbf{Y}_{\mathfrak{s}}\\}_{\mathfrak{s}\in X(k)}\right)$
as

$\Psi~{}\coloneqq~{}{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}.$

We also denote $\Psi$ equivalently as
$\Psi=\Psi\left(\widetilde{{\mathbb{E}}}\right)$ where
$\widetilde{{\mathbb{E}}}$ is the pseudo-expectation operator associated to
the ensemble $\mathbf{Y}$.

###  6.2 SOS Program for List Decoding

Let $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ be a word promised to be
$(1/2-\sqrt{\varepsilon})$-close to a lifted code
$\mathcal{C}_{k}=\operatorname{lift}(\mathcal{C}_{1})$. The word $\tilde{y}$
is to be regarded as a (possibly) corrupted codeword for which we want to do
list decoding. We consider the following SOS program.

$\displaystyle\mbox{minimize}\quad~{}~{}\Psi\left(\\{\mathbf{Y}_{\mathfrak{s}}\\}_{\mathfrak{s}\in
X(k)}\right)$ (List Decoding Program) subject to
$\displaystyle\qquad{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}\widetilde{{\mathbb{E}}}\left[\tilde{y}_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right]\geq
2\sqrt{\varepsilon}$ (Agreement Constraint)
$\displaystyle\qquad\mathbf{Z}_{1},\dots,\mathbf{Z}_{n}\textup{ being
$(L+2k)$-local PSD ensemble}$

Table 1: List decoding SOS formulation for $\tilde{y}$.

###  6.3 Properties of the Entropic Proxy

We establish some key properties of our negative entropic function $\Psi$.
First, we show that $\Psi$ is a convex function. Since the feasible set
defined by the SOS List Decoding Program is convex and admits an efficient
separation oracle 131313In our setting the pseudo-expectation has trace
bounded by $n^{O(t)}$ in which case semidefinite programming can be solved
efficiently [GM12, RW17]., the convexity of $\Psi$ implies that the List
Decoding Program can be efficiently solved within $\eta$-optimality in time
$n^{O(t)}\cdot{\mathrm{polylog}}(\eta^{-1})$ where $t$ is the SOS degree.

######  Lemma 6.2 (Convexity).

$\Psi$ is convex, i.e., for every pair of pseudo-expectations
$\widetilde{{\mathbb{E}}}_{1}$ and $\widetilde{{\mathbb{E}}}_{2}$ and
$\alpha\in[0,1]$,

$\Psi\left(\alpha\cdot\widetilde{{\mathbb{E}}}_{1}+(1-\alpha)\cdot\widetilde{{\mathbb{E}}}_{2}\right)~{}\leq~{}\alpha\cdot\Psi\left(\widetilde{{\mathbb{E}}}_{1}\right)+(1-\alpha)\cdot\Psi\left(\widetilde{{\mathbb{E}}}_{2}\right).$

###### Proof.

Suppose $\mathfrak{s}\cup\mathfrak{t}=\\{i_{1},\dots,i_{t}\\}$. By definition
$\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}=\operatorname{lift}(\mathbf{Z})_{\mathfrak{s}}\cdot\operatorname{lift}(\mathbf{Z})_{\mathfrak{t}}$,
i.e., $\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}$ is a function $f$
on input $\mathbf{Z}_{i_{1}},\dots,\mathbf{Z}_{i_{t}}\in\\{\pm 1\\}$. Let

$f(\mathbf{Z}_{i_{1}},\dots,\mathbf{Z}_{i_{t}})=\sum_{S\subseteq\mathfrak{s}\cup\mathfrak{t}}\widehat{f}(S)\cdot\prod_{i\in
S}\mathbf{Z}_{i},$

be the Fourier decomposition of $f$. Then

$\widetilde{{\mathbb{E}}}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]=\widetilde{{\mathbb{E}}}\left[f\right]=\sum_{S\subseteq\mathfrak{s}\cup\mathfrak{t}}\widehat{f}(S)\cdot\widetilde{{\mathbb{E}}}\left[\prod_{i\in
S}\mathbf{Z}_{i}\right].$

Since
$\widetilde{{\mathbb{E}}}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]$
is a linear function of $\widetilde{{\mathbb{E}}}$, we obtain
$\left(\widetilde{{\mathbb{E}}}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}$
is convex. Now, the convexity of $\Psi$ follows by noting that $\Psi$ is a
convex combination of convex functions.

The (sole) problem-specific constraint appearing in the SOS List Decoding
Program allows us to deduce a lower bound on $\Psi$. This lower bound will be
important later to show that a feasible solution that does not cover all our
intended solutions must have $\Psi$ bounded away from $0$ so that we still
have room to decrease $\Psi$. We note that an improvement in the conclusion of
the following lemma would directly translate to stronger list decoding
parameters in our framework.

######  Lemma 6.3 (Correlation $\Rightarrow$ entropic bound).

Let $\\{\mathbf{Y}_{\mathfrak{s}}\\}_{\mathfrak{s}\in X(k)}$ be $t$-local PSD
ensemble with $t\geq 2$. If there is some $y\in\\{\pm 1\\}^{X(k)}$ such that

$\left|{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}\widetilde{{\mathbb{E}}}\left[y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right]\right|\geq\beta,$

then

$\Psi\left(\\{\mathbf{Y}_{\mathfrak{s}}\\}_{\mathfrak{s}\in
X(k)}\right)~{}\geq~{}\beta^{4}.$

###### Proof.

We calculate

$\displaystyle{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}$
$\displaystyle~{}=~{}{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}\left[\left(y_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{s}}\right)\left(y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{t}}\right)\right]\right)^{2}$
$\displaystyle~{}\geq~{}\left({\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\widetilde{{\mathbb{E}}}\left[\left(y_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{s}}\right)\left(y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{t}}\right)\right]\right)^{2}$
(Jensen’s Inequality)
$\displaystyle~{}=~{}\left(\widetilde{{\mathbb{E}}}\left[({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}})^{2}\right]\right)^{2}$
$\displaystyle~{}\geq~{}\left(\widetilde{{\mathbb{E}}}\left[{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}\left[y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right]\right]\right)^{4}$
(Cauchy–Schwarz Inequality)
$\displaystyle~{}=~{}\left({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}\widetilde{{\mathbb{E}}}\left[y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right]\right)^{4}~{}\geq~{}\beta^{4}.$

We now show the role of $\Psi$ in list decoding: if an intended solution is
not represented in the pseudo-expectation
$\operatorname{\widetilde{\mathbb{E}}}$, we can get a new pseudo-expectation
$\operatorname{\widetilde{\mathbb{E}}}^{\prime}$ which attains a smaller value
of $\Psi$.

######  Lemma 6.4 (Progress lemma).

Suppose there exist $z\in\\{\pm 1\\}^{X(1)}$ and
$y=\operatorname{lift}(z)\in\\{\pm 1\\}^{X(k)}$ satisfying

$\operatorname{\widetilde{\mathbb{E}}}\left[\left({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right)^{2}\right]\leq\delta^{2}.$

If $\Psi\geq\delta^{2}$, then there exists a pseudo-expectation
$\widetilde{{\mathbb{E}}}^{\prime}$ such that

${\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}^{\prime}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}~{}\leq~{}\Psi-\frac{\left(\Psi-\delta^{2}\right)^{2}}{2}.$

In particular, if $\Psi\geq 2\delta^{2}$, then

${\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}^{\prime}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}~{}\leq~{}\Psi-\frac{\delta^{4}}{2}.$

###### Proof.

Let $\widetilde{{\mathbb{E}}}^{\prime}$ be the pseudo-expectation 141414By
summing the pseudo-expectation $\widetilde{{\mathbb{E}}}$ and actual
expectation ${\mathbb{E}}_{\delta_{z}}$, we mean that we are summing
$\widetilde{{\mathbb{E}}}$ to pseudo-expectation of the same dimensions
obtained from operator ${\mathbb{E}}_{\delta_{z}}$.

$\widetilde{{\mathbb{E}}}^{\prime}~{}\coloneqq~{}(1-\alpha)\cdot\widetilde{{\mathbb{E}}}+\alpha\cdot{\mathbb{E}}_{\delta_{z}},$

where ${\mathbb{E}}_{\delta_{z}}$ is the expectation of the delta distribution
on $z$ and $\alpha\in(0,1)$ is to be defined later. We have

$\displaystyle{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}^{\prime}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}$
$\displaystyle~{}=~{}{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left((1-\alpha)\cdot\widetilde{{\mathbb{E}}}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]+\alpha\cdot
y_{\mathfrak{s}}y_{\mathfrak{t}}\right)^{2}$
$\displaystyle~{}=~{}(1-\alpha)^{2}\cdot\Psi+\alpha^{2}\cdot{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}(y_{\mathfrak{s}}y_{\mathfrak{t}})^{2}+2\alpha(1-\alpha)\cdot{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left[\operatorname{\widetilde{\mathbb{E}}}[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}]y_{\mathfrak{s}}y_{\mathfrak{t}}\right]$
$\displaystyle~{}\leq~{}(1-\alpha)^{2}\cdot\Psi+\alpha^{2}+2\alpha(1-\alpha)\cdot\delta^{2}.$

The value of $\alpha$ minimizing the quadratic expression of the RHS above is

$\alpha^{\star}~{}=~{}\frac{\Psi-\delta^{2}}{1+\Psi-2\delta^{2}}.$

Using this value yields

$\displaystyle{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}\left(\widetilde{{\mathbb{E}}}^{\prime}\left[\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\right)^{2}$
$\displaystyle~{}\leq~{}\Psi-\frac{\left(\Psi-\delta^{2}\right)^{2}}{1+\Psi-2\delta^{2}}$
$\displaystyle~{}\leq~{}\Psi-\frac{\left(\Psi-\delta^{2}\right)^{2}}{2},$

where in the last inequality we used $\Psi\leq 1$.

###  6.4 Propagation Rounding

A central algorithm in our list decoding framework is the Propagation Rounding
6.5. It was studied by Barak et al. [BRS11] in the context of approximating
$2$-CSPs on low threshold rank graphs and it was later generalized to HDXs
(and low threshold rank hypergraphs) in the context of $k$-CSPs [AJT19].

Given an $(L+2k)$-local PSD ensemble
$\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$, the Propagation Rounding 6.5
chooses a subset of variables $S\subseteq[n]$ at random. Then it samples a
joint assignment $\sigma$ to the variables in $S$ according to
$\\{\mathbf{Z}_{S}\\}$. The value of the remaining variables $\mathbf{Z}_{i}$
are sampled according to the conditional marginal distributions
$\\{\mathbf{Z}_{i}|\mathbf{Z}_{S}=\sigma\\}$. An important byproduct of this
algorithm is the $2k$-local PSD ensemble
$\mathbf{Z}^{\prime}=\\{\mathbf{Z}_{1},\dots,\mathbf{Z}_{n}|\mathbf{Z}_{S}=\sigma\\}$.

The precise description of the Propagation Rounding 6.5 follows.

######  Algorithm 6.5 (Propagation Rounding Algorithm).

Input An $(L+2k)$-local PSD ensemble
$\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ and some distribution $\Pi_{k}$
on $X(k)$. Output A random assignment
$(\sigma_{1},\ldots,\sigma_{n})\in[q]^{n}$ and $2k$-local PSD ensemble
$\mathbf{Z}^{\prime}$. 1. Choose $m\in\left\\{1,\ldots,L/k\right\\}$ uniformly
at random. 2. Independently sample $m$ $k$-faces,
$\mathfrak{s}_{j}\sim\Pi_{k}$ for $j=1,\ldots,m$. 3. Write
$S=\bigcup_{j=1}^{m}\mathfrak{s}_{j}$, for the set of the seed vertices. 4.
Sample assignment $\sigma:S\rightarrow[q]$ according to the local distribution
$\\{\mathbf{Z}_{S}\\}$. 5. Set
$\mathbf{Z}^{\prime}=\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}|\mathbf{Z}_{S}=\sigma\\}$,
i.e. the local ensemble $\mathbf{Z}$ conditioned on agreeing with $\sigma$. 6.
For all $j\in[n]$, sample independently
$\sigma_{j}\sim\\{\mathbf{Z}^{\prime}_{j}\\}$. 7. Output
$(\sigma_{1},\ldots,\sigma_{n})$ and $\mathbf{Z}^{\prime}$.

To our list decoding task we will show that an ensemble minimizing $\Psi$
covers the space of possible solutions in the sense that for any intended
solution there will be a choice of $S$ and $\sigma$ such that the conditioned
ensemble $\mathbf{Z}^{\prime}$ enables the sampling of a word within the
unique decoding radius in $\mathcal{C}_{1}$ of this intended solution.

An execution of the 6.5 is completely determined by the tuple $(m,S,\sigma)$
which we will refer to as a slice of the PSD ensemble.

######  Definition 6.6 (Slice).

We call a tuple $(m,S,\sigma)$ obtainable by 6.5 a slice and let $\Omega$
denote the set of all slices obtainable by 6.5.

We can endow $\Omega$ with a natural probability distribution, where the
measure of each $(m,S,\sigma)$ is defined as the probability that this slice
is picked during an execution of 6.5. We also define a pseudo-expectation
operator for each slice.

######  Definition 6.7 (Pseudo-Expectation Slice).

Given a slice $(m,S,\sigma)$, we define the pseudo-expectation operator
$\widetilde{{\mathbb{E}}}_{|_{S,\sigma}}$ which is the pseudo-expectation
operator of the conditioned local PSD ensemble
$\\{\mathbf{Z}_{1},\dots,\mathbf{Z}_{n}|\mathbf{Z}_{s}=\sigma\\}$.

###  6.5 Tensorial Structures

In general, a local PSD ensemble
$\mathbf{Z}^{\prime}=\\{\mathbf{Z}_{1}^{\prime},\dots,\mathbf{Z}_{n}^{\prime}\\}$
output by the Propagation Rounding 6.5 may be far from corresponding to any
underlying joint global distribution 151515In fact, if this was the case, then
we would be able to approximate any $k$-CSP with SOS degree $(L+2k)$. However,
even for $L$ as large as linear in $n$ this is impossible for SOS [Gri01,
KMOW17].. In our application, we will be interested in the case where the
ensemble approximately behaves as being composed of independent random
variables over the collection of “local views” given by the hyperedges in
$X(k)$. In such case, rounding the SOS solution via independent rounding is
straightforward. A collection of local views admitting this property with a
given SOS degree parameter $L$ is denoted tensorial (variables behave as
products over the local views).

######  Definition 6.8 (Tensorial Hypergraphs).

Let $X(k)$ be a collection of $k$-uniform hyperedges endowed with a
distribution $\Pi_{k}$, $\mu\in[0,1]$, and $L\in\mathbb{N}$. We say that
$X(k)$ is $(\mu,L)$-tensorial if the local PSD ensemble $\mathbf{Z}^{\prime}$
returned by Propagation Rounding 6.5 with SOS degree parameter $L$ satisfies

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

To analyze the potential $\Psi$ we will need that the variables between pairs
of local views, i.e., pairs of hyperedges, behave as product.

######  Definition 6.9 (Two-Step Tensorial Hypergraphs).

Let $X(k)$ be a collection of $k$-uniform hyperedges endowed with a
distribution $\Pi_{k}$, $\mu\in[0,1]$, and $L\in\mathbb{N}$. We say that
$X(k)$ is $(\mu,L)$-two-step tensorial if it is $(\mu,L)$-tensorial and the
PSD ensemble $\mathbf{Z}^{\prime}$ returned by Propagation Rounding 6.5 with
SOS degree parameter $L$ satisfies

$\operatorname*{\mathbb{E}}_{\Omega}\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.$

In Section 7.1, we establish the relationship between the parameters $\mu$ and
$L$ and the expansion that will ensure HDXs are $(\mu,L)$-two-step tensorial.
Similarly, in Section 9.1.4 we provide this relationship when $X(k)$ is the
collection of walks of an expander graph.

#### Tensorial over Most Slices

By choosing $\mu$ sufficiently small it is easy to show that most slices
$(m,S,\sigma)$ satisfy the tensorial (or two-step tensorial) statistical
distance condition(s) with a slightly worse parameter $\tilde{\mu}$ such that
$\tilde{\mu}\rightarrow 0$ as $\mu\rightarrow 0$. If we could construct
tensorial (or two-step tensorial) objects for arbitrarily small parameter
$\mu$ with $L=O_{k,q,\mu}(1)$, then we would be able to obtain $\tilde{\mu}$
arbitrarily small. Lemma 7.4 establishes that HDXs of appropriate expansion
satisfy this assumption, and Lemma 9.20 does the same for walks on expanders.

We introduce two events. The first event captures when a slice $(m,S,\sigma)$
leads to the conditioned local variables
$\mathbf{Z}_{1}^{\prime},\dots,\mathbf{Z}_{n}^{\prime}$ being close to
$k$-wise independent over the $k$-sized hyperedges.

######  Definition 6.10 (Ground Set Close to $k$-wise Independent).

Let $\mu\in(0,1]$. We define the event $K_{\mu}$ as

$K_{\mu}\coloneqq\left\\{(m,S,\sigma)\in\Omega~{}|~{}\operatorname*{\mathbb{E}}_{\mathfrak{a}\sim\Pi_{k}}{\left\lVert\\{\mathbf{Z}_{\mathfrak{a}}|\mathbf{Z}_{S}=\sigma\\}-\left\\{\mathbf{Z}_{a_{1}}|\mathbf{Z}_{S}=\sigma\right\\}\cdots\left\\{\mathbf{Z}_{a_{k}}|\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}<\mu^{2}/2\right\\}.$

The second event captures when the variables between pairs of hyperedges are
close to independent.

######  Definition 6.11 (Lifted Variables Close to Pairwise Independent).

Let $\mu\in(0,1]$. We define the event $P_{\mu}$ as

$P_{\mu}\coloneqq\left\\{(m,S,\sigma)\in\Omega~{}|~{}\operatorname*{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}}{\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\\}-\left\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{S}=\sigma\right\\}\left\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}<\mu^{2}/2\right\\}.$

These events satisfy a simple concentration property.

######  Claim 6.12 (Concentration).

Suppose a simplicial complex $X(\leq k)$ with $X(1)=[n]$ and an $(L+2k)$-local
PSD ensemble $\mathbf{Z}=\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ are given
as input to Propagation Rounding 6.5. Let $\mu\in(0,1]$. If $X(k)$ is
$(\mu^{4}/4,L)$-two-step tensorial, then

$\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[K_{\mu}^{c}\right]\leq\frac{\mu^{2}}{2},$
(2)

and

$\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[P_{\mu}^{c}\right]\leq\frac{\mu^{2}}{2}.$
(3)

###### Proof.

We only prove Eq. 2 since the proof of Eq. 3 is similar. Define the random
variable
$\mathbf{R}\coloneqq\operatorname*{\mathbb{E}}_{\mathfrak{a}\sim\Pi_{k}}{\left\lVert\\{\mathbf{Z}_{\mathfrak{a}}^{\prime}\\}-\left\\{\mathbf{Z}_{a_{1}}^{\prime}\right\\}\cdots\left\\{\mathbf{Z}_{a_{k}}^{\prime}\right\\}\right\rVert_{1}}$
on the sample space $\Omega=\\{(m,S,\sigma)\\}$. From our $(\mu^{4}/4,L)$-two-
step tensorial assumption we have

${\mathbb{E}}_{\Omega}\left[\mathbf{R}\right]\leq\frac{\mu^{4}}{4}.$

Now, we can conclude

$\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[K_{\mu}^{c}\right]=\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[\mathbf{R}\geq\frac{\mu^{2}}{2}\right]\leq\frac{\mu^{2}}{2},$

using Markov’s inequality.

###  6.6 Further Building Blocks and Analysis

Before we delve into further phases of the list decoding framework, we
introduce some notation for the list of codewords we want to retrieve.

######  Definition 6.13 (Code list).

Given $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ and a code $\mathcal{C}$ on $X(k)$ with
relative distance at least $1/2-\varepsilon$, we define the list
$\mathcal{L}(\tilde{y},\mathcal{C})$ as

$\mathcal{L}(\tilde{y},\mathcal{C})~{}\coloneqq~{}\left\\{y\in\mathcal{C}~{}|~{}\Delta\lparen
y,\tilde{y}\rparen\leq\frac{1}{2}-\sqrt{\varepsilon}\right\\}.$

Under these assumptions the Johnson bound establishes that the list size is
constant whenever $\varepsilon>0$ is constant.

######  Remark 6.14.

The Johnson bound [GRS19] guarantees that

$\left|\mathcal{L}(\tilde{y},\mathcal{C})\right|\leq\frac{1}{2\cdot\varepsilon}$

provided the relative distance of $\mathcal{C}$ is at least $1/2-\varepsilon$.

In the case of lifted codes, it is more appropriate to consider a list of
pairs $\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ defined as
follows.

######  Definition 6.15 (Coupled code list).

Given $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ and a lifted code $\mathcal{C}_{k}$ on
$X(k)$ with relative distance at least $1/2-\varepsilon$, we define the
coupled code list $\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ as

$\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})~{}\coloneqq~{}\left\\{(z,\operatorname{lift}(z))~{}|~{}z\in\mathcal{C}_{1}~{}~{}\textrm{
and
}~{}~{}\Delta\left\lparen\operatorname{lift}(z),\tilde{y}\right\rparen\leq\frac{1}{2}-\sqrt{\varepsilon}\right\\}.$

Recovering this list $\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$
is the main goal of this section. This task will be accomplished by 6.16
stated below whose building blocks and analysis we develop in this section.

######  Algorithm 6.16 (List Decoding Algorithm).

Input A word $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ which is
$(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}$

As shown in Fig. 1 of Section 3, the first step is to solve the List Decoding
Program which results in a pseudo-expectation “covering” the list
$\mathcal{L}(\tilde{y},\mathcal{C})$ as we will make precise. A precursor
property to covering and some considerations about SOS rounding are treated in
Section 6.6.1. Next, the formal definition of cover is presented in Section
6.6.2 and we have all the elements to present the Cover Retrieval 6.29 with
its correctness in Section 6.6.3. Then, we use the robustness properties of
the lifting to purify the cover in Section 6.6.4. Finally, in Section 6.6.5,
we assemble the building blocks and prove the main technical result, Theorem
6.17, whose proof follows easily once the properties of the building blocks
are in place.

Note that Theorem 6.17 embodies an abstract list decoding framework which
relies only on the robustness and tensorial properties of the lifting. We
provide a concrete instantiation of the framework to the direct sum lifting on
HDXs in Section 7 and to the direct sum lifting on expander walks in Section
9.2.

######  Theorem 6.17 (List Decoding Theorem).

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}$.

######  Remark 6.18.

Regarding Theorem 6.17, we stress that although the lifting is
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust and we can perform list
decoding at least up to distance $1/2-\sqrt{\varepsilon}$, our framework does
not recover the Johnson bound. The issue is that our framework requires one of
the additional amplification guarantees of Theorem 6.17, which both make the
distance of $\mathcal{C}_{k}$ become
$1/2-\varepsilon^{\Omega_{\varepsilon_{0}}(1)}>1/2-\varepsilon$. Efficiently
recovering the Johnson bound remains an interesting open problem.

We observe that the algorithms themselves used in this framework are quite
simple (although their analyses might not be). Moreover, the tasks of cover
retrieval and purification are reasonably straightforward. However, Section
6.6.1 combines tensorial properties of the lifting with properties of $\Psi$,
requiring a substantial analysis. The list decoding framework is divided into
stages to make it modular so that key properties are isolated and their
associated functionality can be presented in a simple manner. Most of the
power of this framework comes from the combination of these blocks and the
concrete expanding objects capable of instantiating it.

####  6.6.1 SOS Rounding and Recoverability

We show that if a slice $(m,S,\sigma)$ “captures” an intended solution
$y\in\\{\pm 1\\}^{X(k)}$ (this notion is made precise in the assumptions of
Lemma 6.20), then we can retrieve a $z\in\\{\pm 1\\}^{X(1)}$ such that
$\operatorname{lift}(z)$ has some agreement with $y$. This agreement is
somewhat weak, but combined with the robustness of the lifting, it will be
enough for our purposes. In this subsection, we first explore how to recover
such words within a slice, which can be seen as local rounding in the slice.
Next, we establish sufficient conditions for an intended solution to be
recoverable, now not restricted to a given slice but rather with respect to
the full pseudo-expectation. Finally, we use all the tools developed so far to
show that by minimizing $\Psi$ in a two-step tensorial structure we end up
with a pseudo-expectation in which all intended solutions are recoverable. The
interplay between weak agreement and robustness of the lifting is addressed in
Section 6.6.4.

We will be working with two-step tensorial structures where the following
product distribution associated to a slice naturally appears.

######  Definition 6.19 (Product Distribution on a Slice).

We define $\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}$ to be the product
distribution on the marginals
$\\{\mathbf{Z}_{i}|\mathbf{Z}_{S}=\sigma\\}_{i\in X(1)}$, i.e.,
$\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}\coloneqq\prod_{i\in
X(1)}\\{\mathbf{Z}_{i}|\mathbf{Z}_{S}=\sigma\\}$.

Under appropriate conditions, Lemma 6.20 shows how to round the pseudo-
expectation in a slice.

######  Lemma 6.20 (From fractional to integral in a slice).

Let $(m,S,\sigma)\in\Omega$ be a slice. Suppose

$\operatorname*{\mathbb{E}}_{\mathfrak{a}\sim\Pi_{k}}{\left\lVert\\{\mathbf{Z}_{\mathfrak{a}}|\mathbf{Z}_{S}=\sigma\\}-\left\\{\mathbf{Z}_{a_{1}}|\mathbf{Z}_{S}=\sigma\right\\}\cdots\left\\{\mathbf{Z}_{a_{k}}|\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}\leq\mu,$
(4)

and

$\operatorname*{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}{\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\\}-\left\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{S}=\sigma\right\\}\left\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{S}=\sigma\right\\}\right\rVert_{1}}\leq\mu.$
(5)

For $\beta\in(0,1)$, if $\mu\leq\beta\cdot\kappa^{2}/6$ and $y\in\\{\pm
1\\}^{X(k)}$ is such that

${\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}\widetilde{{\mathbb{E}}}_{|S,\sigma}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\geq\kappa^{2},$

then

$\operatorname*{\mathbb{P}}_{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|\geq\sqrt{1-\beta}\cdot\kappa\right]\geq\frac{\beta\cdot\kappa^{2}}{4}.$
(6)

###### Proof.

Let
$\mu_{\mathfrak{s},\mathfrak{t}}\coloneqq\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{s}=\sigma\\}-\prod_{i\in\mathfrak{s}}\left\\{\mathbf{Z}_{i}|\mathbf{Z}_{s}=\sigma\right\\}\prod_{i\in\mathfrak{t}}\left\\{\mathbf{Z}_{i}|\mathbf{Z}_{s}=\sigma\right\\}\right\rVert_{1}$.
Using triangle inequality and simplifying, we get

$\displaystyle\mu_{\mathfrak{s},\mathfrak{t}}\leq$
$\displaystyle\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{s}=\sigma\\}-\left\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{s}=\sigma\right\\}\left\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{s}=\sigma\right\\}\right\rVert_{1}$
$\displaystyle+\left\lVert\\{\mathbf{Z}_{\mathfrak{s}}|\mathbf{Z}_{s}=\sigma\\}-\prod_{i\in\mathfrak{s}}\left\\{\mathbf{Z}_{i}|\mathbf{Z}_{s}=\sigma\right\\}\right\rVert_{1}+\left\lVert\\{\mathbf{Z}_{\mathfrak{t}}|\mathbf{Z}_{s}=\sigma\\}-\prod_{i\in\mathfrak{t}}\left\\{\mathbf{Z}_{i}|\mathbf{Z}_{s}=\sigma\right\\}\right\rVert_{1}.$

From our assumptions Eq. 4 and Eq. 5, it follows that
$\operatorname*{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi_{k}^{2}}\mu_{\mathfrak{s},\mathfrak{t}}\leq
3\cdot\mu$. Using the fact that $\left\lvert
y_{\mathfrak{s}}y_{\mathfrak{t}}\right\rvert=1$ and Hölder’s inequality, we
get

$\displaystyle{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}{\mathbb{E}}_{\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]$
$\displaystyle\geq{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}\widetilde{{\mathbb{E}}}_{|S,\sigma}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]-{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}\mu_{\mathfrak{s},\mathfrak{t}}$
$\displaystyle\geq{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}\widetilde{{\mathbb{E}}}_{|S,\sigma}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]-3\cdot\mu\geq\left(1-\frac{\beta}{2}\right)\cdot\kappa^{2}.$

Alternatively,

${\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}{\mathbb{E}}_{\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]={\mathbb{E}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\operatorname{lift}(z)_{\mathfrak{s}}\right)^{2}\geq\left(1-\frac{\beta}{2}\right)\cdot\kappa^{2}.$

Define the random variable
$\mathbf{R}\coloneqq\left({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot\operatorname{lift}(z)_{\mathfrak{s}}]\right)^{2}$.
Using A.1 with approximation parameter $\beta/2$, we get

${\mathbb{E}}\left[\mathbf{R}\right]\geq\left(1-\frac{\beta}{2}\right)\cdot\kappa^{2}\Rightarrow\Pr\left[\mathbf{R}\geq(1-\beta)\cdot\kappa^{2}\right]\geq\frac{\beta\cdot\kappa^{2}}{4},$

from which Eq. 6 readily follows.

To formalize the notion of a word being recoverable with respect to the full
pseudo-expectation rather than in a given slice we will need two additional
events. The first event captures correlation as follows.

######  Definition 6.21 ($y$-Correlated Event).

Let $\kappa\in(0,1]$ and $y\in\\{\pm 1\\}^{X(k)}$. We define the event
$C_{\kappa}(y)$ as

$C_{\kappa}(y)\coloneqq\left\\{(m,S,\sigma)\in\Omega~{}|~{}{\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}\widetilde{{\mathbb{E}}}_{|S,\sigma}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\geq\kappa^{2}\right\\}.$

The second event is a restriction of the first where we also require the slice
to satisfy the two-step tensorial condition from Definition 6.9.

######  Definition 6.22 ($y$-Recoverable Event).

Let $\kappa,\mu\in(0,1]$ and $y\in\\{\pm 1\\}^{X(k)}$. We define the event
$R_{\kappa,\mu}(y)$ as

$R_{\kappa,\mu}(y)\coloneqq K_{\mu}\cap P_{\mu}\cap C_{\kappa}(y).$

Lemma 6.20 motivates the following “recoverability” condition.

######  Definition 6.23 (Recoverable Word).

Let $\kappa,\mu\in(0,1]$ and $y\in\\{\pm 1\\}^{X(k)}$. We say that $y$ is
$(\kappa,\mu)$-recoverable provided

$\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[R_{\kappa,\mu}(y)\right]>0.$

One of the central results in our framework is the following “recoverability”
lemma. It embodies the power SOS brings to our framework.

######  Lemma 6.24 (Recoverability lemma).

Let $\mathcal{C}_{k}$ be a lifted code on $X(\leq k)$ with $X(1)=[n]$ and
distance at least $1/2-\varepsilon$. Let $\tilde{y}\in\\{\pm 1\\}^{X(k)}$ be a
word promised to be $(1/2-\sqrt{\varepsilon})$-close to $\mathcal{C}_{k}$ and
let $\mathcal{L}=\mathcal{L}(\tilde{y},\mathcal{C}_{k})$ be its code list.

Let $\theta\in(0,1]$ be arbitrary and set $\mu=\kappa\cdot\theta/2$ and
$\kappa=(4-\theta)\cdot\varepsilon$. Suppose
$\mathbf{Z}=\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ is an $(L+2k)$-local
PSD ensemble which is a solution to the List Decoding Program with objective
value $\Psi$ within $\eta$ additive value from the optimum where
$0\leq\eta\leq\theta^{2}\cdot\varepsilon^{4}$.

If $X(k)$ is $(\mu^{4}/4,L)$-two-step tensorial, then every $y\in\mathcal{L}$
is $(\kappa,\mu)$-recoverable. In particular, for every $\theta\in(0,1)$ and
under the preceding assumptions, we have that every $y\in\mathcal{L}$ is
$\left((4-\theta)\cdot\varepsilon,\theta\right)$-recoverable.

###### Proof.

First observe that since $\tilde{y}$ is $(1/2-\sqrt{\varepsilon})$-close to
$\mathcal{C}_{k}$ the List Decoding Program is feasible and so the solution
$\mathbf{Z}$ is well defined. Towards a contradiction with the
$\eta$-optimality of the SOS solution $\mathbf{Z}$, suppose there exists a
word $y\in\mathcal{L}$ that is not $(\kappa,\mu)$-recoverable. Let $z\in\\{\pm
1\\}^{X(1)}$ be such that $y=\operatorname{lift}(z)$. Then

$\displaystyle
1~{}=~{}\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[R_{\kappa,\mu}(y)^{c}\right]~{}\leq~{}\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[K_{\mu}^{c}\right]+\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[P_{\mu}^{c}\right]+\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[C_{\kappa}(y)^{c}\right].$

Using 6.12, we get

$\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[C_{\kappa}(y)^{c}\right]~{}\geq~{}1-\mu^{2}.$
(7)

Since $\widetilde{{\mathbb{E}}}$ is a valid solution to the List Decoding
Program, Lemma 6.3 implies the lower bound

$\Psi\left(\\{\mathbf{Y}_{\mathfrak{s}}\\}_{\mathfrak{s}\in
X(k)}\right)~{}\geq~{}16\cdot\varepsilon^{2}.$ (8)

By definition, for $(m,S,\sigma)\in C_{\kappa}(y)^{c}$ we have

${\mathbb{E}}_{\mathfrak{s},\mathfrak{t}\sim\Pi^{2}_{k}}\widetilde{{\mathbb{E}}}_{|S,\sigma}\left[y_{\mathfrak{s}}y_{\mathfrak{t}}\mathbf{Y}_{\mathfrak{s}}\mathbf{Y}_{\mathfrak{t}}\right]\leq\kappa^{2},$

implying

$\widetilde{{\mathbb{E}}}\left[\left({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right)^{2}\right]\leq{\mathbb{E}}_{m,S,\sigma}\widetilde{{\mathbb{E}}}_{|S,\sigma}\left[\left({\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\mathbf{Y}_{\mathfrak{s}}\right)^{2}\cdot\mathbf{1}_{C_{\kappa(y)}^{c}}\right]+\operatorname*{\mathbb{P}}_{(m,S,\sigma)\sim\Omega}\left[C_{\kappa}(y)\right]\leq\kappa^{2}+\mu^{2}.$

Let $\widetilde{{\mathbb{E}}}$ be the pseudo-expectation of the ground set
ensemble $\mathbf{Z}$ and let ${\mathbb{E}}^{\prime}$ be the expectation on
the delta distribution $\delta_{z}$. Note that the pseudo-expectation obtained
from ${\mathbb{E}}^{\prime}$ is a valid solution to the List Decoding Program.
Since

$\kappa^{2}+\mu^{2}\leq\left(1+\frac{\theta^{2}}{4}\right)\cdot\kappa^{2}=\left(1+\frac{\theta^{2}}{4}\right)\cdot\left(4-\theta\right)^{2}\cdot\varepsilon^{2}\leq\left(16-2\cdot\theta\right)\cdot\varepsilon^{2},$

and $\theta\geq 0$, Lemma 6.4 gives that there is a convex combination of
$\widetilde{{\mathbb{E}}}$ and ${\mathbb{E}}^{\prime}$ such that the new
$\Psi$, denoted $\Psi^{\prime}$, can be bounded as

$\Psi^{\prime}~{}\leq~{}\Psi-\frac{\left(\Psi-\left(\kappa^{2}+\mu^{2}\right)\right)^{2}}{2}\leq\Psi-2\cdot\theta^{2}\cdot\varepsilon^{4},$

contradicting the $\eta$-optimality of the SOS solution $\mathbf{Z}$ since
$\eta\leq\theta^{2}\cdot\varepsilon^{4}$.

####  6.6.2 Coupled Pairs, Coupled Lists, and Covers

The List Decoding Program minimizing $\Psi$ was instrumental to ensure that
every $y^{\prime}\in\mathcal{L}(\tilde{y},\mathcal{C}_{k})$ is recoverable in
the sense of the conclusion of Lemma 6.24. Unfortunately, this guarantee is
somewhat weak, namely, associated to every
$y^{\prime}\in\mathcal{L}(\tilde{y},\mathcal{C}_{k})$ there is a slice
$(m,S,\sigma)$ from which we can sample $y$ (our approximation of
$y^{\prime}$) satisfying

$\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot
y_{\mathfrak{s}}^{\prime}\rvert>C\cdot\varepsilon,$ (9)

where $C$ is a constant strictly smaller than $4$. A priori this seems
insufficient for our list decoding task. However, there are two properties
which will help us with list decoding. The first is that SOS finds not only
$y$ but also $z\in\\{\pm 1\\}^{X(1)}$ such that $y=\operatorname{lift}(z)$.
The second property is that the lifting is robust: even the weak agreement
given by Eq. 9 translates into a much stronger agreement in the ground set
between $z$ and $z^{\prime}\in\mathcal{C}_{1}$ where
$y^{\prime}=\operatorname{lift}(z^{\prime})$. This stronger agreement on the
ground set can be used to ensure that $z$ (or $-z$) lies inside the unique
decoding ball of $z^{\prime}$ in the base code $\mathcal{C}_{1}$.

To study this coupling phenomenon between words in the lifted space $\\{\pm
1\\}^{X(k)}$ and on the ground space $\\{\pm 1\\}^{X(1)}$ we introduce some
terminology. The most fundamental one is a coupled pair.

######  Definition 6.25 (Coupled Pair).

Let $z\in\\{\pm 1\\}^{X(1)}$ and $y\in\\{\pm 1\\}^{X(k)}$. We say that $(z,y)$
is a coupled pair with respect to a lift function $\operatorname{lift}$
provided $y=\operatorname{lift}(z)$.

######  Remark 6.26.

If the function $\operatorname{lift}$ is clear in the context, we may assume
that the coupled pair is with respect to this function.

Coupled pairs can be combined in a list.

######  Definition 6.27 (Coupled List).

We say that a list
$\mathcal{M}=\\{(z^{(1)},y^{(1)}),\dots,(z^{(h)},y^{(h)})\\}$ is coupled with
respect to lift function $\operatorname{lift}$ provided $(z^{(i)},y^{(i)})$ is
a coupled pair for every $i$ in $[h]$.

A coupled list can “cover” a list of words in the lifted space $\\{\pm
1\\}^{X(k)}$ as defined next.

######  Definition 6.28 (Coupled Bias Cover).

Let $\mathcal{M}=\\{(z^{(1)},y^{(1)}),\dots,(z^{(h)},y^{(h)})\\}$ be a coupled
list and $\mathcal{L}\subset\\{\pm 1\\}^{X(k)}$. We say that $\mathcal{M}$ is
a $\delta$-bias cover of $\mathcal{L}$ provided

$\left(\forall
y^{\prime}\in\mathcal{L}\right)\left(\exists(z,y)\in\mathcal{M}\right)\left(\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}^{\prime}\cdot
y_{\mathfrak{s}}\rvert>\delta\right).$

A $\delta$-bias cover for “small” $\delta$ might seem a rather weak property,
but as alluded to, when combined with enough robustness of the lifting, it
becomes a substantial guarantee enabling list decoding.

####  6.6.3 Cover Retrieval

When the code list $\mathcal{L}(\tilde{y},\mathcal{C}_{k})$ becomes
recoverable in the SOS sense as per Lemma 6.24, we still need to conduct local
rounding on the slices to collect a bias cover. Recall that this local
rounding is probabilistic (c.f. Lemma 6.20), so we need to repeat this process
a few times to boost our success probability161616In fact, this process can be
derandomized using standard techniques in our instantiations. See Lemma C.1
for detais.. This is accomplished by 6.29.

######  Algorithm 6.29 (Cover Retrieval Algorithm).

Input An $(L+2k)$-local PSD ensemble $\mathbf{Z}$ which is a
$(\theta^{2}\varepsilon^{4})$-optimal solution to the List Decoding Program.
Output A $2\varepsilon$-bias cover $\mathcal{M}$ for
$\mathcal{L}(\tilde{y},\mathcal{C}_{k})$. 1. Let $\mathcal{M}=\emptyset$ 2.
Let $T=4\cdot\ln(|\Omega|)\cdot n/(\beta\cdot\varepsilon^{2})$ 3. For
$(m,S,\sigma)\in\Omega$ do 4. If $(m,S,\sigma)\in K_{\mu}\cap P_{\mu}$ then 5.
Run Propagation Rounding $T$ times conditioned on $(m,S,\sigma)$ 6. Let
$\mathcal{M}|_{m,S,\sigma}=\\{(z^{(1)},y^{(1)}),\dots,(z^{(T)},y^{(T)})\\}$ be
the coupled list 7. Set $\mathcal{M}=\mathcal{M}\cup\mathcal{M}|_{m,S,\sigma}$
8. Output $\mathcal{M}$.

The correctness of 6.29 follows easily given the properties established so
far.

######  Lemma 6.30 (Cover lemma).

Let $\beta\in(0,1)$. Suppose that $\operatorname{lift}$ is a
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust
$(\beta^{4}\cdot\varepsilon^{8}/2^{18},L)$-two-step tensorial lifting from
$\mathcal{C}_{1}$ to $\mathcal{C}_{k}$. Let $\tilde{y}\in\\{\pm 1\\}^{X(k)}$
be $(1/2-\sqrt{\varepsilon})$-close to $\mathcal{C}_{k}$. If
$\theta\leq\beta\cdot\varepsilon/2^{4}$, then w.v.h.p.171717The abbreviation
w.v.h.p. stand for with very high probability and means with probability
$1-\exp(-\Theta(n))$. the Cover Retrieval algorithm 6.29 returns a
$\delta$-bias cover $\mathcal{M}$ of the code list
$\mathcal{L}(\widetilde{y},\mathcal{C}_{k})$ where
$\delta=(4-\beta)\cdot\varepsilon$. Furthermore, the running time is at most
$n^{O(L+k)}/(\beta\cdot\varepsilon^{2})$ where $n=|X(1)|$.

###### Proof.

Let $\mathbf{Z}=\\{\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}\\}$ be an
$\eta$-optimum solution to the List Decoding Program where
$\eta\leq\theta^{2}\cdot\varepsilon^{4}$ and
$\theta=\beta\cdot\varepsilon/2^{4}$. By our
$(\beta^{4}\cdot\varepsilon^{8}/2^{18},L)$-two-step tensorial assumption and
our choice of SOS degree for the List Decoding Program, we can apply Lemma
6.24 to conclude that every
$y\in\mathcal{L}=\mathcal{L}(\tilde{y},\mathcal{C}_{k})$ is
$((4-\theta)\cdot\varepsilon,(4-\theta)\cdot\varepsilon\cdot\theta/2)$-recoverable.
Then for $y\in\mathcal{L}$, there exists $(m,S,\sigma)\in\Omega$ such that
Lemma 6.20 yields

$\operatorname*{\mathbb{P}}_{z\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}}\left[\left|{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\operatorname{lift}(z)\right|\geq(4-\beta)\cdot\varepsilon\right]\geq\frac{\beta\cdot(4-\theta)^{2}\cdot\varepsilon^{2}}{32}\geq\frac{\beta\cdot\varepsilon^{2}}{4}.$

where $\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}$ (c.f. Definition 6.19) is the
product distribution of the marginal distributions after conditioning the
ensemble on slice $(m,S,\sigma)$. By sampling
$\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}$ independently $T$ times we obtain
$z^{(1)},\dots,z^{(T)}$ and thus also the coupled list

$\mathcal{M}|_{m,S,\sigma}=\\{(z^{(1)},y^{(1)}),\dots,(z^{(T)},y^{(T)})\\},$

where $y^{(i)}=\operatorname{lift}(z^{(i)})$. Then

$\displaystyle\operatorname*{\mathbb{P}}_{z^{(1)},\dots,z^{(T)}\sim\\{\mathbf{Z}^{\otimes}|_{(S,\sigma)}\\}^{\otimes
T}}\left[\forall
i\in[T]~{}\colon~{}\left|{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}y_{\mathfrak{s}}\cdot\operatorname{lift}\left(z^{(i)}\right)\right|<(4-\beta)\cdot\varepsilon\right]$
$\displaystyle~{}\leq~{}\exp{\left(-\frac{\beta\cdot\varepsilon^{2}\cdot
T}{4}\right)}$
$\displaystyle~{}\leq~{}\frac{\exp{\left(-n\right)}}{|\Omega|},$

where the last inequality follows from our choice of $T$. Then by union bound

$\operatorname*{\mathbb{P}}\left[\mathcal{M}\textup{ is not a
}2\varepsilon\textup{-bias cover of
}\mathcal{L}\right]\leq|\mathcal{L}|\cdot\frac{\exp{\left(-n\right)}}{|\Omega|}\leq\exp{\left(-n\right)},$

concluding the proof.

####  6.6.4 Cover Purification and Robustness

Now we consider the third and final stage of the list decoding framework. We
show how despite the weak guarantee of the bias cover returned by the Cover
Retrieval 6.29 we can do a further processing to finally obtain the coupled
code list $\mathcal{L}(\tilde{y},\mathcal{C}_{1},\mathcal{C}_{k})$ provided
the lifting admits some robustness properties. We first develop these
properties and later present this process, denoted Cover Purification.

#### Further Lifting Properties

Given two coupled pairs $(z,y=\operatorname{lift}(z))$ and
$(z^{\prime},y^{\prime}=\operatorname{lift}(z^{\prime}))$ (where
$z\in\mathcal{C}_{1}$), we show how weak agreement between $y$ and
$y^{\prime}$ on the lifted space is enough to provide non-trivial guarantees
between $z$ and $z^{\prime}$ as long as the lifting admits appropriate
robustness.

######  Claim 6.31 (Coupled unique decoding from distance).

Suppose that $\operatorname{lift}$ is a
$(1/4-\varepsilon_{0}/2,1/2-\varepsilon)$-robust lifting from
$\mathcal{C}_{1}$ to $\mathcal{C}_{k}$. Let $(z,y)$ and
$(z^{\prime},y^{\prime})$ be coupled pairs. If $y\in\mathcal{C}_{k}$
(equivalently $z\in\mathcal{C}_{1}$) and $\Delta\lparen
y,y^{\prime}\rparen<1/2-\varepsilon$, then $\Delta\left\lparen
z,z^{\prime}\right\rparen\leq 1/4-\varepsilon_{0}/2$, i.e., $z^{\prime}$ is
within the unique decoding radius of $z$.

###### Proof.

Towards a contradiction suppose that $\Delta\left\lparen z,z\right\rparen\geq
1/4-\varepsilon_{0}/2$. Since the lifting is
$(1/4-\varepsilon_{0}/2,1/2-\varepsilon)$-robust, this implies that
$\Delta\left\lparen y,y^{\prime}\right\rparen\geq 1/2-\varepsilon$
contradicting our assumption.

From bias amplification (i.e., parity sampling), we deduce 6.32.

######  Claim 6.32 (Coupled unique decoding from bias I).

Suppose $\operatorname{lift}$ is a
$(1/2-\varepsilon_{0},1/2-\varepsilon)$-robust linear lifting from
$\mathcal{C}_{1}$ to $\mathcal{C}_{k}$ which is also a
$(1/2+\varepsilon_{0},2\cdot\varepsilon)$-parity sampler. Let $(z,y)$ and
$(z^{\prime},y^{\prime})$ be coupled pairs. If $y\in\mathcal{C}_{k}$
(equivalently $z\in\mathcal{C}_{1}$) and
$\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot
y^{\prime}_{\mathfrak{s}}]\rvert>2\cdot\varepsilon$, then

$\lvert{\mathbb{E}}_{i\sim\Pi_{1}}[z_{i}\cdot z^{\prime}_{i}]\rvert\geq
1/2+\varepsilon_{0},$

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

###### Proof.

The verification follows easily from our assumptions. Towards a contradiction
suppose that $\lvert{\mathbb{E}}_{i\sim\Pi_{1}}[z_{i}\cdot
z^{\prime}_{i}]\rvert<1/2+\varepsilon_{0}$, i.e., the word
$z^{\prime\prime}=z\cdot z^{\prime}$ has bias at most $1/2+\varepsilon_{0}$.
Using the assumption that the lift is linear, we have
$\operatorname{lift}(z^{\prime\prime})=\operatorname{lift}(z)\cdot\operatorname{lift}(z^{\prime})$.
Since the lifting takes bias $1/2+\varepsilon_{0}$ to $2\cdot\varepsilon$, we
have

$\textup{bias}(\operatorname{lift}(z)\cdot\operatorname{lift}(z^{\prime}))=\textup{bias}(\operatorname{lift}(z^{\prime\prime}))\leq
2\cdot\varepsilon,$

or equivalently
$\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot
y^{\prime}_{\mathfrak{s}}]\rvert\leq 2\cdot\varepsilon$ contradicting our
assumption.

If the lifting function is odd, then we obtain 6.33.

######  Claim 6.33 (Coupled unique decoding from bias II).

Suppose $\operatorname{lift}$ is a
$(1/4-\varepsilon_{0}/2,1/2-\varepsilon)$-robust lifting from
$\mathcal{C}_{1}$ to $\mathcal{C}_{k}$ which is odd, i.e.,
$\operatorname{lift}(-z)=-\operatorname{lift}(z)$. Let $(z,y)$ and
$(z^{\prime},y^{\prime})$ be coupled pairs. If $y\in\mathcal{C}_{k}$
(equivalently $z\in\mathcal{C}_{1}$) and
$\lvert{\mathbb{E}}_{\mathfrak{s}\sim\Pi_{k}}[y_{\mathfrak{s}}\cdot
y^{\prime}_{\mathfrak{s}}]\rvert>2\cdot\varepsilon$, then either $z^{\prime}$