0
$\begingroup$

Can someone recommend a reference on the PCP theorem that explains how it works via examples rather than formal CS language?

Specifically, I'm looking for the example on how graph colouring can be modified so that it suffices to check a few bits of a coloring or something like that.

Had posted this in cstheory.stackexchange was asked to move it here.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The PCP theorem is not particularly simple. I don't think what you're looking for is possible. It's like asking for an elementary proof of the prime number theorem that any high-schooler can follow. The fact that the statement is simple doesn't imply that there are any simple proofs. (An even worse example is Fermat's last theorem.) $\endgroup$ – Yuval Filmus May 3 '20 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.