The starting point for our work is the framework developed
in [1]} for decoding direct sum codes, obtained by starting
from a code \(\mathcal {C}\subseteq {\mathbb {F}}_2^n\)  and considering all parities
corresponding to a set of \(t\) -tuples \(W(t) \subseteq [n]^t\) .
Ta-Shma's near optimal \(\varepsilon \) -balanced codes are
constructed by starting from a code with constant rate and constant
distance and considering such a direct sum lifting. The set of
tuples \(W(t)\)  in his construction corresponds to a set of walks of
length \(t-1\)  on the \(s\) -wide replacement product of an expanding graph
\(G\)  with vertex set \([n]\)  and a smaller expanding graph \(H\) . The
\(s\) -wide replacement product can be thought of here as a way of
constructing a much smaller pseudorandom subset of the set of all
walks of length \(t-1\)  on \(G\) , which yields a similar distance
amplification for the lifted code.
