49 citations · 105 across the 13 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
quant-ph2012
Shared Randomness and Quantum Communication in the Multi-Party Model
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players,…
quant-ph2012
A multi-prover interactive proof for NEXP sound against entangled provers
Tsuyoshi Ito, Thomas Vidick
We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of language…
quant-ph2012★ 9 cited
A quantum query algorithm for the graph collision problem
Dmitry Gavinsky, Tsuyoshi Ito
We construct a new quantum algorithm for the graph collision problem; that is, the problem of deciding whether the set of marked vertices contains a pair of adjacent vertices in a…