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 TR18-083 | 9th May 2018 07:13

An Exponential Separation Between MA and AM Proofs of Proximity

RSS-Feed




Revision #2
Authors: Tom Gur, Yang P. Liu, Ron D. Rothblum
Accepted on: 9th May 2018 07:13
Downloads: 988
Keywords: 


Abstract:

Interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work we consider two natural minimally interactive variants of such proofs systems, in which the prover only sends a single message, referred to as the proof.

The first variant, known as MA-proofs of Proximity (MAP), is fully non-interactive, meaning that the proof is a function of the input only. The second variant, known as MA-proofs of Proximity (AMP), allows the proof to additionally depend on the verifier’s (entire) random string. The complexity of both MAPs and AMPs is the total number of bits that the verifier observes — namely, the sum of the proof length and query complexity.

Our main result is an exponential separation between the power of MAPs and AMPs. Specifically, we exhibit an explicit and natural property $\Pi$ that admits an AMP with complexity $O(\log n)$, whereas any MAP for $\Pi$ has complexity $\tilde{\Omega}(n^{1/4})$, where $n$ denotes the length of the input in bits. Our MAP lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014).

Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier’s queries are oblivious to the proof. In this setting we show that AMPs can only be quadratically stronger than MAPs. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.



Changes to previous version:

Minor revision


Revision #1 to TR18-083 | 9th May 2018 06:33

An Exponential Separation Between MA and AM Proofs of Proximity





Revision #1
Authors: Tom Gur, Yang P. Liu, Ron D. Rothblum
Accepted on: 9th May 2018 06:33
Downloads: 741
Keywords: 


Abstract:

Non-interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, given access to a short proof. Two natural variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof is a function of the input only, and AM-proofs of Proximity (AMP), in which the proof additionally may depend on the verifier’s (entire) random string. The complexity of both MAPs and AMPs is the total number of bits that the verifier observes — namely, the sum of the proof length and query complexity.

Our main result is an exponential separation between the power of MAPs and AMPs. Specifically, we exhibit an explicit and natural property $\Pi$ that admits an AMP with complexity $O(\log n)$, whereas any MAP for $\Pi$ has complexity $\tilde{\Omega}(n^{1/4})$, where $n$ denotes the length of the input in bits. Our MAP lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014).

Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier’s queries cannot depend on the proof. In this setting we show that AMPs can only be quadratically stronger than MAPs. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.



Changes to previous version:

Minor revision


Paper:

TR18-083 | 25th April 2018 01:10

An Exponential Separation Between MA and AM Proofs of Proximity





TR18-083
Authors: Tom Gur, Yang P. Liu, Ron D. Rothblum
Publication: 25th April 2018 10:14
Downloads: 938
Keywords: 


Abstract:

Non-interactive proofs of proximity allow a sublinear-time verifier to check that
a given input is close to the language, given access to a short proof. Two natural
variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof
is a function of the input only, and AM-proofs of Proximity (AMP), in which the proof
additionally may depend on the verifier’s (entire) random string. The complexity of
both MAPs and AMPs is the total number of bits that the verifier observes – namely,
the sum of the proof length and query complexity.
Our main result is an exponential separation between the power of MAPs and
AMPs. Specifically, we exhibit an explicit and natural property ? that admits an AMP
with complexity O(log n), whereas any MAP for ? has complexity ?(n^(1/4)), where n
denotes the length of the input in bits. Our MAP lower bound also yields an alternate
proof, which is more general and arguably much simpler, for a recent result of
Fischer et al. (ITCS, 2014).
Lastly, we also consider the notion of oblivious proofs of proximity, in which the
verifier’s queries cannot depend on the proof. In this setting we show that AMPs can
only be quadratically stronger than MAPs. As an application of this result, we show
an exponential separation between the power of public and private coin for oblivious
interactive proofs of proximity.



ISSN 1433-8092 | Imprint