This talk is likely to be interesting to many of us. ---------- Forwarded message ---------- From: <calendar(a)csail.mit.edu> Date: Wed, Dec 4, 2013 at 12:01 AM Subject: [Theory-seminars] TALK: Wednesday 12-11-2013 Algorithms and Complexity Seminar: Information causality, Szemerédi-Trotter and algebraic variants of CHSH by Mohammad Bavarian To: theory-seminars(a)csail.mit.edu, seminars(a)csail.mit.edu, compalgsem(a)lists.csail.mit.edu Beyond XOR Games: Information causality, Szemerédi-Trotter and Algebraic Variants of CHSH Speaker: Mohammad Bavarian Speaker Affiliation: MIT Host: Ilya Razenshteyn Date: Wednesday, December 11, 2013 Time: 4:00 PM to 5:00 PM Location: 32-G575 The CHSH game is arguably the most well-studied game in quantum information theory, and plays a crucial role in applications to quantum cryptography and complexity. CHSHq is a natural larger alphabet generalization of CHSH introduced by Buhrman and Massar. In CHSHq, two parties receive x,y?Fq uniformly at random, and each must produce an output a,b?Fq without communicating to the other. They succeed if a+b=xy in Fq. In this work, we obtain the first asymptotic results on the quantum and classical values of these games. Our main result regarding the quantum value of CHSH_q is an upper bound of O(q?1/2). Regarding the classical value of the game, we prove an improved upper bound O(q?1/2??0) in the case of q=p2k?1. We complement this with a tight lower bound of ?(q?1/2) for q=p2k. We believe the techniques established here to obtain the above results are interesting in their own right, and could find applications in other contexts. For example, the geometric view we develop while studying the classical value of CHSHq reveals an intimate connection between this game and the celebrated finite field Szemeredi-Trotter theorem of Bourgain-Katz-Tao (GAFA 14.1 (2004)). This connection could also be useful in pseudorandomness, and especially the study of multi-source extractors. Another novel point is an information theoretic result proved as an intermediate step in our quantum upper bound, which resolves an open problem of Pawlowski and Winter (Phys. Rev. A 85.2 (2012)). An important fact regarding the task of studying CHSHq, and generally any game with q>2, is that we cannot rely on the powerful result of Tsirelson on SDP characterization of the quantum value of games, which is only known for XOR games (a subclass of q=2 games). As a result, there are few examples and techniques available for analyzing quantum games with q>2. Hence, one main contribution of this work is to expand on the set of tools and examples in a setting beyond the relatively well-understood case of XOR games. Joint work with Peter Shor. Relevant URL: For more information please contact: Joanne Talbot Hanley, 617-253-6054, joanne(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