Probabilistically Checkable Proofs (PCPs) allow a verifier to check the validity of a proof by reading only a few symbols chosen at random. While the symbols are chosen at random, classical PCP constructions rely on complex correlations between the different queries. Motivated by applications to proofs over noisy channels, in this work we initiate the study of "sample-based PCPs" in which the verifier's queries are chosen uniformly at random without such correlations.
Our main results are constructions of sample-based PCPs:
1. For proving the satisfiability of a circuit C of size S, we construct a sample-based PCP of length S*polylog(S) over a constant size alphabet in which the verifier reads \sqrt{S}*polylog(S) random symbols.
2. We construct a "zero-knowledge" sample-based PCP with similar parameters to our first result, but for which the sample-based verifier learns essentially nothing beyond the fact that C is satisfiable.