Details

Autor(en) / Beteiligte

• Lin, Sian-Jheng
• Han, Yunghsiang S.
• Yu, Nenghai

Titel

New Locally Correctable Codes Based on Projective Reed-Muller Codes

Ist Teil von

• IEEE transactions on communications, 2019-06, Vol.67 (6), p.3834-3841

Ort / Verlag

New York: IEEE

Erscheinungsjahr

2019

Quelle

IEEE Electronic Library Online

Beschreibungen/Notizen

• 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 whether there exist codes that have shorter codeword lengths than GRM codes with the same query complexity and message length. In this paper, we show that the projective Reed-Muller (PRM) codes are such LCCs for some parameters. The GRM code is specified by the alphabet size <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula>, the number of variables <inline-formula> <tex-math notation="LaTeX">m </tex-math></inline-formula>, and the degree <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">d\le q-2 </tex-math></inline-formula>. When <inline-formula> <tex-math notation="LaTeX">d= q-2 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q-1 </tex-math></inline-formula> is a power of a prime, we prove that there exists a PRM code with shorter codeword length than the GRM code with the same query complexity and message length. We also present for these PRM codes a perfectly smooth local decoder to recover a symbol in a codeword by accessing not more than <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula> symbols at the coordinates of the codeword.