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.

翻译：我们提出了一个在LOCAL模型下利用分布式图着色构建纠错码的通用框架。基于混淆图中独立集与有效编码之间的对应关系，我们证明了单个顶点的颜色——与全局真着色一致——可以通过改进版的Linial着色算法在多项式时间内计算，从而实现高效的编码与解码。我们的研究成果包括：i) 针对任意类型恒定数量错误的唯一可译码构造，其冗余度为Gilbert-Varshamov界的两倍；ii) 通过提出的图着色扩展（即超图标记）实现列表可译码；iii) 当编辑距离未知时，具有降低平均情况通信量的增量同步方案；iv) 首个用于纠正无界长度编辑突发错误的渐近最优编码（达到8倍因子内）。与校验子压缩方法相比，我们的方法更具灵活性和可扩展性，不依赖于优质基码，并在多种参数范围内实现了更优的冗余度。