IC Colloquium : The complexity of entangled games: hardness results and approximation algorithms
Event details
| Date | 04.03.2013 |
| Hour | 16:15 › 17:30 |
| Speaker |
Thomas Vidick, Massachusetts Institute of Technology IC faculty candidate |
| Location | |
| Category | Conferences - Seminars |
Abstract
The study of multiplayer games is a major theme in modern computational complexity; key results from the PCP theorem to the hardness of constraint satisfaction problems such as MAXCUT or 3-SAT were derived through their investigation. In a multiplayer game, a trusted referee interacts with two or more players who collaborate in an attempt to win the game. The only restriction on the players is that they are not allowed to communicate once the game has started.
Entanglement is arguably the most counter-intuitive aspect of quantum mechanics, and also its most powerful --- it plays a crucial role in the exponential speed-ups of quantum computers. Its study in the context of multiplayer games allows for a whole new perspective. The nonlocal properties of entanglement, once infamously derided by Einstein as ``spooky action at a distance'', now play the role of a new distributed resource available to the players (akin but much more powerful than shared randomness). How does its use affect the power of the players in winning the game? Can the classical referee still exert any control on the players' abilities to confound him?
In this talk I will show how powerful techniques from complexity theory can be brought about for the study of these questions, which go right at the heart of fundamental issues in quantum mechanics. Key to our resolution will be the development of a deeper understanding of a fundamental property of entanglement, its monogamy. In the process we will also obtain new insights on a classic construction in complexity theory, the linearity test.
Biography
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".
The study of multiplayer games is a major theme in modern computational complexity; key results from the PCP theorem to the hardness of constraint satisfaction problems such as MAXCUT or 3-SAT were derived through their investigation. In a multiplayer game, a trusted referee interacts with two or more players who collaborate in an attempt to win the game. The only restriction on the players is that they are not allowed to communicate once the game has started.
Entanglement is arguably the most counter-intuitive aspect of quantum mechanics, and also its most powerful --- it plays a crucial role in the exponential speed-ups of quantum computers. Its study in the context of multiplayer games allows for a whole new perspective. The nonlocal properties of entanglement, once infamously derided by Einstein as ``spooky action at a distance'', now play the role of a new distributed resource available to the players (akin but much more powerful than shared randomness). How does its use affect the power of the players in winning the game? Can the classical referee still exert any control on the players' abilities to confound him?
In this talk I will show how powerful techniques from complexity theory can be brought about for the study of these questions, which go right at the heart of fundamental issues in quantum mechanics. Key to our resolution will be the development of a deeper understanding of a fundamental property of entanglement, its monogamy. In the process we will also obtain new insights on a classic construction in complexity theory, the linearity test.
Biography
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".
Links
Practical information
- Informed public
- Free
- This event is internal
Contact
- Christine Moscioni