Efficiently decoding Reed-Muller codes from random errors

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1{\}}^m$. We denote this code by $RM(m,r)$. The minimal distance of $RM(m,r)$…