Lecture 6: Reed-Muller codes/Schwartz-Zippel lemma

Written on 19.05.2021 11:57 by Anand Narayanan

Hi All,

Today we will introduce Reed-Muller codes and prove their distance using the Schwartz-Zippel lemma. Then we study a local decoding algorithm for Reed-Muller codes. 

We also take a few fun deviations outside coding theory. We apply the Schwartz-Zippel lemma to polynomial identity testing. In particular, simple algorithms for

i) finding perfect matchings in graphs

ii) and testing if a given number is a prime. 

Next class: Application of Reed-Muller codes to property testing/PCPs etc..


Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.