All reports by Author Ron D. Rothblum:

__
TR18-083
| 25th April 2018
__

Tom Gur, Ron D. Rothblum, Yang P. Liu#### An Exponential Separation Between MA and AM Proofs of Proximity

Revisions: 2

Tom Gur, Ron D. Rothblum, Yang P. Liu

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 ...
more >>>