Correcting on Curves and Highly Sound Locally Correctable Codes of High Rate

Abstract—Locally correctable codes have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. Recently, Guo et al. [1], discovered a family of high rate locally correctable codes by considering lifting of multivariate polynomials. In this paper, we extend their method by lifting multivariate polynomials on curves, and generalize the “decoding on curve ” algorithm from Reed-Muller codes to these lifted codes to provide correcting algorithms with success probability arbitrarily approaching 1. This gives a family of high rate locally correctable codes that is highly sound. I