Abstract
We study interactive oracle proofs (IOPs) [BCS16,RRR16], which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs or IPs alone. Our main results are:
1. Circuit satisfiability has 3round IOPs with linear proof length (counted in bits) and constant query complexity.
2. ReedSolomon codes have 2round IOPs of proximity with linear proof length and constant query complexity.
3. Tensor product codes have 1round IOPs of proximity with sublinear proof length and constant query complexity.
For all the above, known PCP constructions give quasilinear proof length and constant query complexity [BS08,Din07]. Also, for circuit satisfiability, [BKKMS13] obtain PCPs with linear proof length but sublinear (and superconstant) query complexity. As in [BKKMS13], we rely on algebraicgeometry codes to obtain our first result; but, unlike that work, our use of such codes is much "lighter" because we do not rely on any automorphisms of the code.
We obtain our results by proving and combining "IOPanalogues" of tools underlying numerous IPs and PCPs:
* Interactive proof composition. Proof composition [AS98] is used to reduce the query complexity of PCP verifiers, at the cost of increasing proof length by an additive factor that is exponential in the verifier's randomness complexity. We prove a composition theorem for IOPs where this additive factor is linear.
* Sublinear sumcheck. The sumcheck protocol [LFKN92] is an IP that enables the verifier to check the sum of values of a lowdegree multivariate polynomial on an exponentiallylarge hypercube, but the verifier's running time depends linearly on the bound on individual degrees. We prove a sumcheck protocol for IOPs where this dependence is sublinear (e.g., polylogarithmic).
Our work demonstrates that even constantround IOPs are more efficient than known PCPs and IPs.
BibTeX  Entry
@InProceedings{bensasson_et_al:LIPIcs:2017:7471,
author = {Eli BenSasson and Alessandro Chiesa and Ariel Gabizon and Michael Riabzev and Nicholas Spooner},
title = {{Interactive Oracle Proofs with Constant Rate and Query Complexity}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {40:140:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7471},
URN = {urn:nbn:de:0030drops74713},
doi = {10.4230/LIPIcs.ICALP.2017.40},
annote = {Keywords: probabilistically checkable proofs, interactive proofs, proof composition, sumcheck}
}
Keywords: 

probabilistically checkable proofs, interactive proofs, proof composition, sumcheck 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

06.07.2017 