About the Event
Ito & Vidick (2012) proved a strong limitation on the ability of entangled provers to collude in a multiplayer game. The 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 exponential time. While Babai, Fortnow, and Lund (Computational Complexity 1991) proved the celebrated equality MIP = NEXP in the absence of entanglement, ever since the introduction of the class MIP* it was open whether shared entanglement between the provers could weaken or strengthen the computational power of multi-prover interactive proofs. Their result shows that it does not weaken their computational power: MIP* contains MIP.
In the talk, I will discuss more about the necessary background and the reason why the shared entanglement case is interesting, while keeping the technical part involving quantum computation at a minimum. (This result appears in this year FOCS and is one of the co-winners of the best paper award.)