  We develop new list decoding algorithms for Tanner codes and
distance-amplified codes based on bipartite spectral expanders. We show that
proofs exhibiting lower bounds on the minimum distance of these codes can be
used as certificates discoverable by relaxations in the Sum-of-Squares (SoS)
semidefinite programming hierarchy. Combining these certificates with certain
entropic proxies to ensure that the solutions to the relaxations cover the
entire list, then leads to algorithms for list decoding several families of
codes up to the Johnson bound.
  We prove the following:
  - We show that the LDPC Tanner codes of Sipser-Spielman [IEEE Trans. Inf.
Theory 1996] and Z\'{e}mor [IEEE Trans. Inf. Theory 2001] with alphabet size
$q$, block-length $n$ and distance $\delta$, based on an expander graph with
degree $d$, can be list-decoded up to distance $\mathcal{J}_q(\delta) -
\epsilon$ in time $n^{O_{d,q}(1/\epsilon^4)}$, where $\mathcal{J}_q(\delta)$
denotes the Johnson bound.
  - We show that the codes obtained via the expander-based distance
amplification procedure of Alon, Edmonds and Luby [FOCS 1995] can be
list-decoded close to the Johnson bound using the SoS hierarchy, by reducing
the list decoding problem to unique decoding of the base code. In particular,
starting from \emph{any} base code unique-decodable up to distance $\delta$,
one can obtain near-MDS codes with rate $R$ and distance $1-R - \epsilon$,
list-decodable up to the Johnson bound in time $n^{O_{\epsilon, \delta}(1)}$.
  - We show that the locally testable codes of Dinur et al. [STOC 2022] with
alphabet size $q$, block-length $n$ and distance $\delta$ based on a square
Cayley complex with generator sets of size $d$, can be list-decoded up to
distance $\mathcal{J}_q(\delta) - \epsilon$ in time
$n^{O_{d,q}(1/\epsilon^{4})}$, where $\mathcal{J}_q(\delta)$ denotes the
Johnson bound.
