Lecture 8: Locally testable codes, PCPs and hardness of approximation

Written on 09.06.2021 12:42 by Anand Narayanan

Hi all,

On today's lecture we will discuss

PCPs in a little more detail and state the PCP theorem,

the role of locally testable codes in the original proof of the PCP theorem,

and hardness of approximation through PCPs.


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