2026-07-25T06:30:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21046 2024-09-16T06:02:39Z ddc:004 open_access

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? Doron, Dean Mosheiff, Jonathan Wootters, Mary Error-correcting codes Concatenated codes Derandomization Gilbert-Varshamov bound The Gilbert-Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate ε² has relative distance at least 1/2 - O(ε) with high probability. However, it is a major challenge to construct explicit codes with similar parameters. One hope to derandomize the Gilbert-Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code 𝒞_out over a large alphabet, and concatenate that with a small binary random linear code 𝒞_in. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code 𝒞_in can lie on the GV bound; and if so what conditions on 𝒞_out are sufficient for this. We show that first, there do exist linear outer codes 𝒞_out that are "good" for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for 𝒞_out, so that if 𝒞_out satisfies these, 𝒞_out∘𝒞_in will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes 𝒞_out. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dean Doron and Jonathan Mosheiff and Mary Wootters 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.53 urn:nbn:de:0030-drops-210467 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.53 eng https://creativecommons.org/licenses/by/4.0/legalcode