Hi Quanta, This is to let people know that I'm giving a talk on parallel repetition of entangled games on Wednesday at 4pm (abstract below). This is joint work with Xiaodi Wu (MIT) and Kai-min Chung (Academia Sinica). If you like quantum games, or uses of quantum information in complexity theory, this topic may be of interest. The talk will be self-contained; no background in parallel repetition or quantum games will be assumed. I hope to see some of you there! Regards, Henry ---------- Forwarded message ---------- From: <calendar(a)csail.mit.edu> Date: Mon, Apr 13, 2015 at 2:22 PM Subject: [Theory-seminars] Wednesday 04-15-2015 Henry Yuen: Parallel repetition for entangled games via fast quantum search To: seminars(a)csail.mit.edu, theory-seminars(a)csail.mit.edu Henry Yuen: Parallel repetition for entangled games via fast quantum search *Host:* Ilya Razenshteyn *Date:* Wednesday, April 15, 2015 *Time:* 4:00 PM to 5:00 PM *Location:* 32-G575 Abstract: We give improved parallel repetition theorems for multiplayer, one-round games with entangled players, when the inputs to the players are uncorrelated. We do so by exploiting a novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa: by taking advantage of fast quantum protocols for distributed search, we show that for this class of games (called free games), the entangled value of the n-fold repetition decays as (1 - eps^{3/2})^{\Omega(n/s)}, where 1 - eps is the entangled value of the original game, and s is the output alphabet size. In contrast, the best known parallel repetition theorem for free games (due to Barak, et al.) in the classical setting is that the n-fold repetition value is bounded by (1 - eps^2)^{\Omega(n/s)}, suggesting the possibility of a separation between the behavior of quantum and classical games under parallel repetition. Our proof takes advantage of the Aaronson-Ambainis quantum search protocol, and a general theorem of Nayak and Salzman that bounds the ability of parties to convey classical messages using two-way quantum communication. Joint work with Kai-Min Chung and Xiaodi Wu. Relevant URL: For more information please contact: Rebecca Yadegar, ryadegar(a)csail.mit.edu _______________________________________________ Theory-seminars mailing list Theory-seminars(a)lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/theory-seminars _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip