Spring 2014

A Survey on the Complexity of Entangled Provers

Tuesday, Feb. 25, 2014 10:30 am11:30 am PST

Add to Calendar


Calvin Lab Auditorium

We will survey the power of interactive proof systems with multiple entangled provers and a classical verifier.

Three topics will be discussed in more detail. These include the NP-hardness of exactly determining the game value of a nonlocal game, the breakthrough of Ito and Vidick on multi-prover interactive proofs for NEXP sound against entangled provers, and some recent observations on the binary constraint system games.

The theme of this talk will be how shared entanglement between provers can break certain interactive proofs and what we can do to suppress and to make use of this effect.