Paper Info
Title
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.
Abstract
Locally correctable codes (LCCs) are codes C: Σk → Σn which admit local algorithms that can correct any individual symbol of a corrupted codeword via a minuscule number of queries. One of the central problems in algorithmic coding theory is to construct O(1)-query LCC with minimal block length. Alas, state-of-the-art of such codes requires exponential block length to admit O(1)-query algorithms for local correction, despite much attention during the last two decades. This lack of progress prompted the study of relaxed LCCs, which allow the correction algorithm to abort (but not err) on small fraction of the locations. This relaxation turned out to allow constant-query correction algorithms for codes with polynomial block length. Specifically, prior work showed that there exist O(1)-query relaxed LCCs that achieve nearly-quartic block length n = k4+α, for an arbitrarily small constant α > 0. We construct an O(1)-query relaxed LCC with nearly-linear block length n = k1+α, for an arbitrarily small constant α > 0. This significantly narrows the gap between the lower bound which states that there are no O(1)-query relaxed LCCs with block length n = k1+o(1). In particular, this resolves an open problem raised by Gur, Ramnarayan, and Rothblum (ITCS 2018).
Year
DOI
Venue
2020
10.5555/3381089.3381173
SODA '20: ACM-SIAM Symposium on Discrete Algorithms Salt Lake City Utah January, 2020
Field
DocType
Volume
Discrete mathematics,Combinatorics,Computer science
Conference
27
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Alessandro Chiesa189946.20
Tom Gur2307.96
Igor Shinkar3248.97