Computer Science/Discrete Mathematics Seminar II

Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$. Its distance is $2^{m-r}$ and so it cannot correct more than that many errors/erasures in the worst case. For random errors one may hope for a better result. In his seminal paper Shannon exactly determined the amount of errors and erasures one can hope to correct for codes of a given rate. Codes that achieve Shannon's bound are called capacity achieving codes. In this talk we will show that Reed-Muller codes of low rate achieve capacity for both erasures and errors. We will also show that for high rate RM codes achieve capacity for erasures. In addition, we will describe a novel efficient algorithm for decoding random errors in Reed-Muller codes far beyond the minimal distance. In particular, for codes of degree at most $\sqrt{m}$ the algorithm can decode from fraction of $1/2 - o(1)$ random errors, with high probability. Based on joint works with Emmanuel Abbe and Avi Wigderson and with Ramprasad Saptharishi and Ben lee Volk.