1. Circuit satisfiability has 3-round IOPs with linear proof length (counted in bits) and constant query complexity.
2. Reed--Solomon codes have 2-round IOPs of proximity with linear proof length and constant query complexity.
3. Tensor product codes have 1-round IOPs of proximity with sublinear proof length and constant query complexity.
For all of the above, known PCP constructions give *quasilinear* proof length and constant query complexity [BS08,Dinur07]. In addition, for circuit satisfiability, [BKKMS13] obtain PCPs with linear proof length but *sublinear* query complexity. As in [BKKMS13], we rely on algebraic-geometry codes to obtain our first result; but, unlike [BKKMS13], our use of such codes is much "lighter" because we do not rely on any automorphisms of the code.
We obtain our results in a modular way by proving and combining "IOP-analogues" of two fundamental tools:
*Interactive proof composition:* Proof composition is used to reduce the query complexity of PCP verifiers, but the proof length of the composed proof system depends exponentially on the randomness complexity of the outer proof system. We prove a composition theorem for IOPs that does not suffer from this inefficiency.
*Sublinear sumcheck:* The sumcheck protocol is an IP that enables an IP verifier to check the sum of values of a low-degree polynomial on an exponentially-large hypercube, but the verifier running time depends linearly on the individual degree. We prove a sumcheck protocol for IOPs that does not suffer from this inefficiency.
Overall, our work demonstrates that even constant-round IOPs are more efficient than known PCPs and IPs.Category / Keywords: foundations / probabilistically checkable proofs, interactive proofs, proof composition, sumcheck Date: received 23 Mar 2016, last revised 29 Apr 2016 Contact author: alexch at berkeley edu Available format(s): PDF | BibTeX Citation Version: 20160429:063108 (All versions of this report) Short URL: ia.cr/2016/324 Discussion forum: Show discussion | Start new discussion