All reports by Author Yang P. Liu:

__
TR23-198
| 8th December 2023
__

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer#### Parallel Repetition of k-Player Projection Games

__
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

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with value less than 1.

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