Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
This addresses the problem of efficient error-correcting code design for communication and storage systems, but it is incremental as it builds on prior work to simplify and optimize the construction.
The paper tackles constructing explicit codes matching the Gilbert-Varshamov bound in the low-rate, high-distance regime, achieving a simpler almost-optimal construction with rate Ω(ε^{2+o(1)}) and relative distance (1-ε)/2.
We study the problem of constructing explicit codes whose rate and distance match the Gilbert-Varshamov bound in the low-rate, high-distance regime. In 2017, Ta-Shma gave an explicit family of codes where every pair of codewords has relative distance $\frac{1-\varepsilon}{2}$, with rate $Ω(\varepsilon^{2+o(1)})$, matching the Gilbert-Varshamov bound up to a factor of $\varepsilon^{o(1)}$. Ta-Shma's construction was based on starting with a good code and amplifying its bias with walks arising from the $s$-wide-replacement product. In this work, we give a simpler almost-optimal construction, based on what we call free expander walks: ordinary expander walks where each step is taken on a distinct expander from a carefully chosen sequence. This sequence of expanders is derived from the construction of near-$X$-Ramanujan graphs due to O'Donnell and Wu. We additionally discuss some additional applications of near-$X$-Ramanujan graphs to "on average" lossless expansion and rotating expanders.