On Multi-Point Local Decoding of Reed-Muller Codes
Ronald Cramer, Chaoping Xing, Chen Yuan · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2016
Reed-Muller codes are among the most important classes of locally correctable codes.Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate.To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate.This decoding algorithm might be more expensive, i.e., require higher query complexity.In this paper, we focus on Reed-Muller codes with evaluation polynomials of total degree d σ √ q for some σ ∈ (0, 1).By introducing a local decoding of Reed-Muller codes via the