Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.04197 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909943228006400 |
|---|---|
| author | Li, Yuting Gabrys, Ryan Farnoud, Farzad |
| author_facet | Li, Yuting Gabrys, Ryan Farnoud, Farzad |
| contents | We present a general framework for constructing error-correcting codes using distributed graph coloring under the LOCAL model. Building on the correspondence between independent sets in the confusion graph and valid codes, we show that the color of a single vertex - consistent with a global proper coloring - can be computed in polynomial time using a modified version of Linial's coloring algorithm, leading to efficient encoding and decoding. Our results include: i) uniquely decodable code constructions for a constant number of errors of any type with redundancy twice the Gilbert-Varshamov bound; ii) list-decodable codes via a proposed extension of graph coloring, namely, hypergraph labeling; iii) an incremental synchronization scheme with reduced average-case communication when the edit distance is not precisely known; and iv) the first asymptotically optimal codes (up to a factor of 8) for correcting bursts of unbounded-length edits. Compared to syndrome compression, our approach is more flexible and generalizable, does not rely on a good base code, and achieves improved redundancy across a range of parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_04197 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constructing Low-Redundancy Codes via Distributed Graph Coloring Li, Yuting Gabrys, Ryan Farnoud, Farzad Information Theory We present a general framework for constructing error-correcting codes using distributed graph coloring under the LOCAL model. Building on the correspondence between independent sets in the confusion graph and valid codes, we show that the color of a single vertex - consistent with a global proper coloring - can be computed in polynomial time using a modified version of Linial's coloring algorithm, leading to efficient encoding and decoding. Our results include: i) uniquely decodable code constructions for a constant number of errors of any type with redundancy twice the Gilbert-Varshamov bound; ii) list-decodable codes via a proposed extension of graph coloring, namely, hypergraph labeling; iii) an incremental synchronization scheme with reduced average-case communication when the edit distance is not precisely known; and iv) the first asymptotically optimal codes (up to a factor of 8) for correcting bursts of unbounded-length edits. Compared to syndrome compression, our approach is more flexible and generalizable, does not rely on a good base code, and achieves improved redundancy across a range of parameters. |
| title | Constructing Low-Redundancy Codes via Distributed Graph Coloring |
| topic | Information Theory |
| url | https://arxiv.org/abs/2512.04197 |