Local correction of codes of high rate

Locally correctable codes (LCC) are error-correcting codes with efficient decoding schemes, which can recover any bit of a codeword by visiting a small number of locations of the codeword. LCCs have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. In this work, we investigate the locally correctable codes of high rate. We are mainly interested in new constructions of high-rate locally correctable codes, local correction of multiple bits, and the inner connection between the lifted Reed-Solomon codes and the multiplicity codes. Firstly, we extend the techniques of lifted Reed-Solomon codes by lifting multivariate polyno- mials 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. Furthermore, we take a deeper look into the method of multiplicities and provide a new con- struction of locally correctable codes of rate approaching 1, which is also a theoretical connection between the multiplicity codes and lifted Reed Solomon Codes. At last, we generalize the concept of traditional local correction to local correction of multiple bits, and present a family of codes which allow multiple bits to be recovered with probability approaching 1 by visiting a small number of locations of the received word, even when a constant fraction of errors exist. Moreover, our codes are of high rate.​Doctor of Philosophy (SPMS