New Locally Correctable Codes Based on Projective Reed–Muller Codes

Locally decodable codes and locally correctable codes (LCCs) have several important applications, such as private information retrieval, secure multiparty computation, and circuit lower bounds. Three major parameters are considered in LCCs: query complexity, message length, and codeword length. The most familiar LCCs in the regime of low query complexity are the generalized Reed-Muller (GRM) codes. However, it has not previously been determined...