Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.12606
curl -X POST /api/v1/records/arxiv/2601.12606/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.12606/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'