Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914454685351936 |
|---|---|
| author | Hsieh, Jun-Ting Mohanty, Sidhanth Zhang, Rachel Yun |
| author_facet | Hsieh, Jun-Ting Mohanty, Sidhanth Zhang, Rachel Yun |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12606 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks Hsieh, Jun-Ting Mohanty, Sidhanth Zhang, Rachel Yun Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics 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. |
| title | Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2601.12606 |