49 citations · 105 across the 13 of their papers we have counts for
15 papers
On the Role of Shared Randomness in Simultaneous Communication
Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits. It allows the parties to act in a correlated…
Approximate Span Programs
Tsuyoshi Ito, Stacey Jeffery
Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. For any decision problem, there exists a span program that lea…
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,…
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…
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…
Quantum interactive proofs with weak error bounds
Tsuyoshi Ito, Hirotada Kobayashi, John Watrous
This paper proves that the computational power of quantum interactive proof systems, with a double-exponentially small gap in acceptance probability between the completeness and so…