Sound 3-query PCPPs are long
Prahladh Harsha, TTI Chicago
February 29, 2008, 3:30PM, Wean 7220
Abstract:
The celebrated PCP Theorem [AS+ALMSS] states that any NP proof can be rewritten in such a manner that a probabilistic verifier can check the veracity of the proof by querying the proof in at most a constant number of locations. In this paper, we ask the question if there exist 3-query PCPs that are both short (of size n.\poly\log n) as well as reject proofs of false assertions with probability close to 1/2? In other worlds, can we have the best of the results of both Hastad (3-query PCPs with soundness 1/2-eps but long proofs) and Ben-Sasson-Sudan+Dinur (3-query PCPs with short proofs, but poor soundness)?
We show that any PCP construction that yields PCPs of proximity with similar parameters CANNOT achieve the above property. We obtain this result by studying the trade-off between the length of a PCP of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle access to the proof. Our main result is that a verifier limited to querying a short (i.e, polynomial) proof cannot obtain the same soundness as that obtained by a verifier querying a long (i.e, exponential) proof.
