Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-046 | 21st September 2017 22:20

Interactive Oracle Proofs with Constant Rate and Query Complexity

RSS-Feed




Revision #2
Authors: Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
Accepted on: 21st September 2017 22:20
Downloads: 1029
Keywords: 


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 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 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 super-constant) query complexity. As in [BKKMS13], we rely on algebraic-geometry 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 "IOP-analogues" 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 low-degree multi-variate polynomial on an exponentially-large 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 constant-round IOPs are more efficient than known PCPs and IPs.



Changes to previous version:

Revised full version.


Revision #1 to TR16-046 | 29th April 2016 08:18

Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck





Revision #1
Authors: Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
Accepted on: 29th April 2016 08:18
Downloads: 972
Keywords: 


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 general 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 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 *quaslinear* 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.



Changes to previous version:

added references to [RRR16]


Paper:

TR16-046 | 23rd March 2016 07:33

Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck


Abstract:

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general 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 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 *quaslinear* 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.



ISSN 1433-8092 | Imprint