Abstract
A relaxed locally correctable code is equipped with an algorithm that, when given query access to a (potentially corrupted) codeword and an index i, either returns the ith bit of the nearest codeword or detects corruption. We build the first asymptotically good relaxed locally correctable codes with polylogarithmic query complexity, which finally closes the superpolynomial gap between query lower and upper bounds.
Our construction makes use of locally testable codes, which have algorithms that probabilistically detect the presence of corruption with few queries. By combining high-rate locally testable codes of various sizes, we can produce a code with local testers at every scale: we can gradually "zoom in" to any desired codeword index i, and a local tester at each step certifies that the next, smaller restriction of the input has low error. If no local tester detects corruption throughout this process, then the ith bit of the input is likely not corrupt and can be safely returned.