Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR18-048 | 11th March 2018
Ofer Grossman, Yang P. Liu

Reproducibility and Pseudo-Determinism in Log-Space

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

ISSN 1433-8092 | Imprint