BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : The complexity of entangled games: hardness result
 s and approximation algorithms
DTSTART:20130304T161500
DTEND:20130304T173000
DTSTAMP:20260916T043437Z
UID:a22d3d93b2dca1749f85f208ca492b7ea4a10d53d95b904dc6af7ba0
CATEGORIES:Conferences - Seminars
DESCRIPTION:Thomas Vidick\, Massachusetts Institute of Technology\nIC facu
 lty candidate\nAbstract\nThe study of multiplayer games is a major theme i
 n modern computational complexity\; key results from the PCP theorem to th
 e hardness of constraint satisfaction problems such as MAXCUT or 3-SAT wer
 e derived through their investigation. In a multiplayer game\, a trusted r
 eferee 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 al
 lowed to communicate once the game has started.\nEntanglement 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 quan
 tum computers. Its study in the context of multiplayer games allows for a 
 whole new perspective. The nonlocal properties of entanglement\, once infa
 mously derided by Einstein as ``spooky action at a distance''\, now play t
 he role of a new distributed resource available to the players (akin but m
 uch more powerful than shared randomness). How does its use affect the pow
 er of the players in winning the game? Can the classical referee still exe
 rt any control on the players' abilities to confound him?\nIn this talk I 
 will show how powerful techniques from complexity theory can be brought ab
 out for the study of these questions\, which go right at the heart of fund
 amental issues in quantum mechanics. Key to our resolution will be the dev
 elopment of a deeper understanding of a fundamental property of entangleme
 nt\, its monogamy. In the process we will also obtain new insights on a cl
 assic construction in complexity theory\, the linearity test.Biography\nTh
 omas Vidick is currently a postdoctoral associate in the Computer Science 
 and Artificial Intelligence Laboratory (CSAIL) at MIT. His research intere
 sts are in quantum computing and complexity theory\, and he has made contr
 ibutions to the theory of quantum multi-prover interactive proofs\, quantu
 m cryptography\, pseudo-randomness\, and approximation algorithms.\nHe com
 pleted his Ph.D. in Computer Science from UC Berkeley in Fall 2011\, worki
 ng with Umesh Vazirani. His thesis was awarded the Bernard Friedman Memori
 al 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".
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR