Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914164734164992 |
|---|---|
| author | Jeronimo, Fernando Granha Shagrithaya, Nikhil |
| author_facet | Jeronimo, Fernando Granha Shagrithaya, Nikhil |
| contents | We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon-Edmonds-Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025). The main theorem demonstrates that if random linear codes satisfy the complement of an LCL property $\mathcal{P}$ with high probability, then one can construct explicit codes satisfying the complement of $\mathcal{P}$ as well, with an enlarged yet constant alphabet size. This gives the first explicit constructions for list recovery, as well as special cases (e.g., list recovery with erasures, zero-error list recovery, perfect hash matrices), with parameters matching those of random linear codes. More broadly, our constructions realize the full range of parameters associated with these properties at the same level of optimality as in the random setting, thereby offering a systematic pathway from probabilistic guarantees to explicit codes that attain them. Furthermore, our derandomization of random linear codes also admits efficient (list) decoding via recently developed expander-based decoders. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06185 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes Jeronimo, Fernando Granha Shagrithaya, Nikhil Information Theory Combinatorics We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon-Edmonds-Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025). The main theorem demonstrates that if random linear codes satisfy the complement of an LCL property $\mathcal{P}$ with high probability, then one can construct explicit codes satisfying the complement of $\mathcal{P}$ as well, with an enlarged yet constant alphabet size. This gives the first explicit constructions for list recovery, as well as special cases (e.g., list recovery with erasures, zero-error list recovery, perfect hash matrices), with parameters matching those of random linear codes. More broadly, our constructions realize the full range of parameters associated with these properties at the same level of optimality as in the random setting, thereby offering a systematic pathway from probabilistic guarantees to explicit codes that attain them. Furthermore, our derandomization of random linear codes also admits efficient (list) decoding via recently developed expander-based decoders. |
| title | Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes |
| topic | Information Theory Combinatorics |
| url | https://arxiv.org/abs/2510.06185 |