Error-Correcting Graph Codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913536859439104 |
|---|---|
| author | Kopparty, Swastik Potukuchi, Aditya Sha, Harry |
| author_facet | Kopparty, Swastik Potukuchi, Aditya Sha, Harry |
| contents | In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance $δ$ is a family $C$ of graphs on a common vertex set of size $n$, such that if we start with any graph in $C$, we would have to modify the neighborhoods of at least $δn$ vertices in order to obtain some other graph in $C$. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric, constructing good codes for $δ< 1/2$, and optimal codes for a large-alphabet analogue. We extend their work by showing
1. Combinatorial results determining the optimal rate vs. distance trade-off nonconstructively.
2. Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances.
3. Graph code analogues of dual-BCH codes, yielding large codes with distance $δ= 1-o(1)$. This gives an explicit ''graph code of Ramsey graphs''.
Several recent works, starting with the paper of Alon, Gujgiczer, Körner, Milojević, and Simonyi, have studied more general graph codes; where the symmetric difference between any two graphs in the code is required to have some desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13867 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Error-Correcting Graph Codes Kopparty, Swastik Potukuchi, Aditya Sha, Harry Information Theory Discrete Mathematics Combinatorics G.2.1; E.4 In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance $δ$ is a family $C$ of graphs on a common vertex set of size $n$, such that if we start with any graph in $C$, we would have to modify the neighborhoods of at least $δn$ vertices in order to obtain some other graph in $C$. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric, constructing good codes for $δ< 1/2$, and optimal codes for a large-alphabet analogue. We extend their work by showing 1. Combinatorial results determining the optimal rate vs. distance trade-off nonconstructively. 2. Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances. 3. Graph code analogues of dual-BCH codes, yielding large codes with distance $δ= 1-o(1)$. This gives an explicit ''graph code of Ramsey graphs''. Several recent works, starting with the paper of Alon, Gujgiczer, Körner, Milojević, and Simonyi, have studied more general graph codes; where the symmetric difference between any two graphs in the code is required to have some desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept. |
| title | Error-Correcting Graph Codes |
| topic | Information Theory Discrete Mathematics Combinatorics G.2.1; E.4 |
| url | https://arxiv.org/abs/2406.13867 |