Theory Seminar

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

Xiaodi Wu

Friday, November 16, 2012
10:30am - 11:30am
3941 BBB

Add to Google Calendar

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.)

Additional Information

Sponsor(s): EECS

Open to: Public