All reports by Author Yang P. Liu:

__
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

__
TR18-048
| 11th March 2018
__

Ofer Grossman, Yang P. Liu#### Reproducibility and Pseudo-Determinism in Log-Space

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

Ofer Grossman, Yang P. Liu

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits ... more >>>