Probabilistically checkable proofs, part 2
Kent Quanrud · 80:01
This lecture continues a proof of the PCP theorem by showing that gap-CSP is NP-hard: after a three-step cycle (expanderify, random-walk power, alphabet-reduce), a single unsatisfied constraint can be amplified to a c...