Distributed PCP Theorems for Hardness of Approximation in P

Amir Abboud, Aviad Rubinstein, Ryan Williams

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment $x\in \{0,1{\}}^n$ to a CNF formula $\phi$ is shared between two parties, where…