Revisiting the multiplicity codes: A new class of high-rate locally correctable codes
Liyasi Wu · 2015
Locally correctable codes 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. Recently Kopparty et. al. [1] and Guo et. al. [2] presented multiplicity codes and lifted Reed-Solomon codes, respectively, which are two families of high-rate locally correctable codes. In this paper, we generalize the method of multiplicities and provide a new construction of locally correctable codes of rate approaching 1, which is also a theoretical connection between the codes in [1] and [2].