2017/02/09 by Sian-Jheng Lin, Lin, Sian-Jheng
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Coding theory and cryptography #Cooperative Communication and Network Coding #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1702.02671
arxiv created 2017/02/09 · openalex publication_date 2017/02/09 · arxiv updated 2017/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we show that the projective Reed-Muller~(PRM) codes form a family of locally correctable codes~(LCC) in the regime of low query complexities. A PRM code is specified by the alphabet size q, the number of variables m, and the degree d. When d≤ q-1, we present a perfectly smooth local decoder to recover a symbol by accessing γ≤ q symbols to the coordinates fall on a line. There are three major parameters considered in LCCs, namely the query complexity, the message length and the code length. This paper shows that PRM codes are shorter than generalized Reed-Muller~(GRM) codes in LCCs. Precisely, given a GRM code over a field of size q, there exists a class of shorter codes over a field of size q-1, while maintaining the same values on the query complexities and the message lengths.