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.
Go to Source of this post
Author Of this post: