News
Lecture 7: PCPs, linearity testing, locally testable codes.
Written on 02.06.2021 10:20 by Anand Narayanan
Hi all,
On today's lecture we start with a gentle/infomal introduction to Probabilistic Checkable Proofs PCPs and their relation to NP. Then we build tools from algebraic coding theory that played a part in the original proof of the PCP theorem. The main tool will be the Blum-Luby-Rubinfeld linearity test. We conclude with low degree testing (local testing of Reed-Muller codes). Most of what we discuss today is new and understandble even if you missed the past few classes.
Next class: We will study PCPs with greater care and prove a very weak version of the PCP theorem with a long witness.
-Anand