Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Tsuyoshi Ito:

TR15-137 | 22nd August 2015
Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito

On the Role of Shared Randomness in Simultaneous Communication

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 manner, which can be quite useful.
But what happens if the shared randomness is not perfect?

In this work, ... more >>>

TR13-044 | 25th March 2013
Dmytro Gavinsky, Tsuyoshi Ito, Guoming Wang

Shared Randomness and Quantum Communication in the Multi-Party Model

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, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

TR12-085 | 5th July 2012
Tsuyoshi Ito, Thomas Vidick

A multi-prover interactive proof for NEXP sound against entangled provers

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 languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic ... more >>>

TR10-165 | 4th November 2010
Dmytro Gavinsky, Tsuyoshi Ito

Quantum Fingerprints that Keep Secrets

We introduce a new type of cryptographic primitive that we call hiding fingerprinting. No classical fingerprinting scheme is hiding. We construct quantum hiding fingerprinting schemes and argue their optimality.

more >>>

ISSN 1433-8092 | Imprint