High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
From MaRDI portal
Publication:4640284
DOI10.1145/3051093zbMath1426.94160arXiv1504.05653MaRDI QIDQ4640284
Or Meir, Swastik Kopparty, Shubhangi Saraf, Noga Ron-Zewi
Publication date: 17 May 2018
Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.05653
query complexity; locally testable codes; locally decodable codes; locally correctable codes; singleton bound; asymptotically good codes; Zyablov bound
94B05: Linear codes (general theory)
94B65: Bounds on codes
94B60: Other types of codes
94B35: Decoding