Paper 2021/915
A PCP Theorem for Interactive Proofs
Gal Arnon and Alessandro Chiesa and Eylon Yogev
Abstract
The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads $O(1)$ bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multiple rounds while reading a small number of bits from each prover message. While PCPs are relatively well understood, the power captured by IOPs (beyond NP) has yet to be fully explored. We present a generalization of the PCP theorem for interactive languages. We show that any language decidable by a $k(n)$-round IP has a $k(n)$-round public-coin IOP, where the verifier makes its decision by reading only $O(1)$ bits from each (polynomially long) prover message and $O(1)$ bits from each of its own (random) messages to the prover. Our proof relies on a new notion of PCPs that we construct called index-decodable PCPs, which may be of independent interest. We are then able to bring transformations that previously applied only for IPs into the realm of IOPs. We show IOP-to-IOP transformations that preserve query complexity and achieve: (i) private-coins to public-coins; (ii) round reduction; and (iii) imperfect to perfect completeness.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- interactive proofsprobabilistically checkable proofsinteractive oracle proofs
- Contact author(s)
- galarnon42 @ gmail com,alexch @ berkeley edu,eylony @ gmail com
- History
- 2023-01-17: last of 8 revisions
- 2021-07-08: received
- See all versions
- Short URL
- https://ia.cr/2021/915
- License
-
CC BY