2026-07-22T13:28:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22695 2026-04-17T05:32:25Z ddc:004 open_access

Error-Correcting Graph Codes Kopparty, Swastik Potukuchi, Aditya Sha, Harry Graph codes explicit construction concatenation codes tensor codes 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Swastik Kopparty and Aditya Potukuchi and Harry Sha 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.67 urn:nbn:de:0030-drops-226950 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.67 eng https://creativecommons.org/licenses/by/4.0/legalcode