Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Fall 2015 Schedule
Winter 2016 Schedule

2013/02/12, McConnell 437, 10:00 - 11:00

The complexity of entangled games: hardness results and approximation algorithms
Thomas Vidick , MIT: Department of Computer Science and Artificial Intelligence Laboratory


Multiplayer games, from their use in cryptography to their role in the proof of the PCP theorem, play a central role in modern theoretical computer science. Recently the introduction of a new element, quantum entanglement, has brought a second life to the study of these games. Entanglement plays the role of a distributed resource that the players can tap in order to increase their odds of winning: how does its use affect the properties of the game? In turn, multiplayer games have proved a valuable tool in the study of fundamental properties of entanglement. In this talk I will present some recent result on the complexity of entangled games. I will show that the class MIP*(3) of languages having three-prover entangled proof systems contains the class NEXP. This resolves a long-standing open question in quantum complexity by showing that entangled-prover proof systems are no less powerful than their classical counterparts. The proof is based on adapting the multilinearity test from Babai et al's seminal result MIP = NEXP [BFL'91] to the entangled-player setting, and demonstrates the strength of one of the most interesting aspects of entanglement, its monogamy. Time permitting I will briefly discuss applications of entangled games to two very different areas: device-independent proofs of security in cryptography and approximation algorithms based on the use of semidefinite programming.

Biography of Speaker:

Thomas Vidick is currently a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT. His research interests are in quantum computing and complexity theory, and he has made contributions to the theory of quantum multi-prover interactive proofs, quantum cryptography, pseudo-randomness, and approximation algorithms. He completed his Ph.D. in Computer Science from UC Berkeley in Fall 2011, working with Umesh Vazirani. His thesis was awarded the Bernard Friedman Memorial Prize in applied mathematics. He is a co-recipient of the FOCS'12 best paper award for his paper with Tsuyoshi Ito on "A multi-prover interactive proof for NEXP sound against entangled provers".