All reports by Author Henry Yuen:

__
TR19-086
| 7th June 2019
__

Alex Bredariol Grilo, William Slofstra, Henry Yuen#### Perfect zero knowledge for quantum multiprover interactive proofs

__
TR18-105
| 30th May 2018
__

Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen#### Quantum proof systems for iterated exponential time, and beyond

__
TR17-010
| 18th January 2017
__

Xiaodi Wu, Penghui Yao, Henry Yuen#### Raz-McKenzie simulation with the inner product gadget

Revisions: 1

__
TR16-160
| 26th October 2016
__

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen#### Multiplayer parallel repetition for expander games

Revisions: 1

__
TR16-060
| 15th April 2016
__

Henry Yuen#### A parallel repetition theorem for all entangled games

__
TR16-047
| 23rd March 2016
__

Mohammad Bavarian, Thomas Vidick, Henry Yuen#### Parallel repetition via fortification: analytic view and the quantum case

Alex Bredariol Grilo, William Slofstra, Henry Yuen

In this work we consider the interplay between multiprover interactive proofs, quantum

entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory,

quantum information and cryptography. In particular, we study the relationship between the

complexity class MIP$^*$ , the set of languages decidable by multiprover interactive ...
more >>>

Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen

We show that any language in nondeterministic time $\exp(\exp(\cdots\exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - \exp(-C\exp(\cdots\exp(n)))$, ... more >>>

Xiaodi Wu, Penghui Yao, Henry Yuen

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

Henry Yuen

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known.

...
more >>>

Mohammad Bavarian, Thomas Vidick, Henry Yuen

In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial ... more >>>