Conflict Checkable and Decodable Codes and Their Applications
Benny Applebaum, Eliran Kachlon
Abstract
Let C be an error-correcting code over a large alphabet q of block length n, and assume that, a possibly corrupted, codeword c is distributively stored among n servers where the ith entry is being held by the ith server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are “consistent” with some legal codeword or “conflicted”. What type of information about c can be inferred from this consistency graph? Can we check whether errors occurred and if so, can we find the error locations and effectively decode? We initiate the study of conflict-checkable and conflict-decodable codes and prove the following main results:
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Builds on2
Related papers
- Robust Clustering Oracle and Local Reconstructor of Cluster Structure of GraphsPan PengSODA 2020 · 1 citation
- On the Optimal Repair-Scaling Trade-off in Locally Repairable CodesSi Wu, Zhirong Shen, Patrick P. C. LeeINFOCOM 2020 · 30 citations
- Proximity Gaps for Reed-Solomon CodesEli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty et al.FOCS 2020 · 58 citations
- Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear CodesElena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey MonSTOC 2026 · 4 citations
- Practical Design Considerations for Wide Locally Recoverable Codes (LRCs)Saurabh Kadekodi, Shashwat Silas, David Clausen, Arif MerchantFAST 2023 · 55 citations
