Name: noc21-cs49-lec40 | Videos | Gan Jing World
Uploaded: 2023-12-01T23:12:37.596Z
Duration: 1 h 29 min 50 s
Description: The two views of considering the PCP Theorem -- as a locally and probabilistically checkable proof system, and as a hardness ofapproximation. The MAX optimizati... | Videos | Gan Jing World

IIT Kanpur July 201

https://video4-us-west.cloudokyo.cloud/video/v6/87/01/c2/8701c286-cc3b-45a5-a93c-14fb113be880/master.m3u8

The two views of considering the PCP Theorem -- as a locally and probabilistically checkable proof system, and as a hardness ofapproximation. The MAX optimization problem. An approximation algorithm for MAX. Definition of the class PCP(r(n),q(n)).NP=PCP(logn,1) [The PCP Theorem]. GNIâˆˆPCP(poly,1). Hardness of approximation view of the PCP Theorem.Equivalence of the two views.