{"id":"arxiv/2601.12606","url":"https://arxiv.org/abs/2601.12606","tags":["cs.CC","cs.DM","cs.DS","math.CO"],"score":0,"title":"Explicit Almost-Optimal $\\varepsilon$-Balanced Codes via Free Expander Walks","domain":"cs.CC","source":"arxiv","authors":["Jun-Ting Hsieh","Sidhanth Mohanty","Rachel Yun Zhang"],"reviews":0,"subject":"cs.CC","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-18","reactions":{}}