Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

DOI10.1137/1.9781611975994.84zbMath1502.68119OpenAlexW2997631494MaRDI QIDQ5146859

Alessandro Chiesa, Igor Shinkar, Tom Gur

Publication date: 2 February 2021

Published in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975994.84

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (2)

Smooth and strong PCPs ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP

This page was built for publication: Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity