Explicit Codes approaching Generalized Singleton Bound using Expanders
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910822093029376 |
|---|---|
| author | Jeronimo, Fernando Granha Mittal, Tushant Srivastava, Shashank Tulsiani, Madhur |
| author_facet | Jeronimo, Fernando Granha Mittal, Tushant Srivastava, Shashank Tulsiani, Madhur |
| contents | We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of $O(\frac{1}ε)$. In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs.
Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS'95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a "local-to-global" phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every $R, ε\in (0,1)$ and $k \in \mathbb{N}^+$, we obtain an \emph{explicit} family of codes $\mathcal{C} \subseteq Σ^n$, with rate $R$ such that,
- They achieve the $ε$-relaxed generalized Singleton bound: for any $g \in Σ^n$ and any list $\mathcal{H}$ of at most $k$ codewords, we have, \[ \underset{h \in \mathcal{H}}{\mathbb{E}} [Δ(g,h)] ~\geq~ \frac{|\mathcal{H}|-1}{|\mathcal{H}|} \cdot (1 - R - ε). \]
- The alphabet size is a constant depending only on $ε$ and $k$.
- They can be list decoded up to radius $\frac{k-1}{k}(1-R-ε)$, in time $n^{O_{k,ε}(1)}$.
As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07308 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Explicit Codes approaching Generalized Singleton Bound using Expanders Jeronimo, Fernando Granha Mittal, Tushant Srivastava, Shashank Tulsiani, Madhur Information Theory Computational Complexity We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of $O(\frac{1}ε)$. In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs. Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS'95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a "local-to-global" phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every $R, ε\in (0,1)$ and $k \in \mathbb{N}^+$, we obtain an \emph{explicit} family of codes $\mathcal{C} \subseteq Σ^n$, with rate $R$ such that, - They achieve the $ε$-relaxed generalized Singleton bound: for any $g \in Σ^n$ and any list $\mathcal{H}$ of at most $k$ codewords, we have, \[ \underset{h \in \mathcal{H}}{\mathbb{E}} [Δ(g,h)] ~\geq~ \frac{|\mathcal{H}|-1}{|\mathcal{H}|} \cdot (1 - R - ε). \] - The alphabet size is a constant depending only on $ε$ and $k$. - They can be list decoded up to radius $\frac{k-1}{k}(1-R-ε)$, in time $n^{O_{k,ε}(1)}$. As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound. |
| title | Explicit Codes approaching Generalized Singleton Bound using Expanders |
| topic | Information Theory Computational Complexity |
| url | https://arxiv.org/abs/2502.07308 |