News
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..
-Anand