The Library
An exponential separation between MA and AM proofs of proximity
Tools
Tools
Tools
Gur, Tom, Liu, Yang P. and Rothblum, Ron (2018) An exponential separation between MA and AM proofs of proximity. In: The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 9-13 Jul 2018. Published in: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 107 73:1-73:15. ISBN 9783959770767. doi:10.4230/LIPIcs.ICALP.2018.73 ISSN 1868-8969.
|
PDF
WRAP-exponential-separation-between-MA-AM-proofs-Gur-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (554Kb) | Preview |
Official URL: https://iuuk.mff.cuni.cz/~icalp2018/
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 AM-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 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.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | ||||
| ISBN: | 9783959770767 | ||||
| ISSN: | 1868-8969 | ||||
| Official Date: | 29 June 2018 | ||||
| Dates: |
|
||||
| Volume: | 107 | ||||
| Page Range: | 73:1-73:15 | ||||
| DOI: | 10.4230/LIPIcs.ICALP.2018.73 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Date of first compliant deposit: | 11 April 2019 | ||||
| Date of first compliant Open Access: | 11 April 2019 | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Prague, Czech Republic | ||||
| Date(s) of Event: | 9-13 Jul 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
