2026-07-28T01:18:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16572 2024-03-06T10:57:49Z ddc:004 open_access

New Near-Linear Time Decodable Codes Closer to the GV Bound Blanc, Guy Doron, Dean Unique decoding list decoding the Gilbert-Varshamov bound small-bias sample spaces hypergraphs expander walks We construct a family of binary codes of relative distance 1/2-ε and rate ε² ⋅ 2^(-log^α (1/ε)) for α ≈ 1/2 that are decodable, probabilistically, in near-linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who gave a randomized decoding of Ta-Shma codes with α ≈ 5/6 [Ta-Shma, 2017; Jeronimo et al., 2021]. Each code in our family can be constructed in probabilistic polynomial time, or deterministic polynomial time given sufficiently good explicit 3-uniform hypergraphs. Our construction is based on a new graph-based bias amplification method. While previous works start with some base code of relative distance 1/2-ε₀ for ε₀ ≫ ε and amplify the distance to 1/2-ε by walking on an expander, or on a carefully tailored product of expanders, we walk over very sparse, highly mixing, hypergraphs. Study of such hypergraphs further offers an avenue toward achieving rate Ω̃(ε²). For our unique- and list-decoding algorithms, we employ the framework developed in [Jeronimo et al., 2021]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy Blanc and Dean Doron 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.10 urn:nbn:de:0030-drops-165726 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.10 eng https://creativecommons.org/licenses/by/4.0/legalcode