Preprint
Aug 2026
A Simple Algebraic Proof of the PCP Theorem
We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and...
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan et al.
· 0 citations