[Aspuru-Guzik Group List] [qip] tomorrow and upcoming talks

Dear quanta, We will cancel group meeting tomorrow because there is a crypto seminar that may be of interest to many of us. At 1:30pm in 6C-442, Adam will tell us about his recent work (with me and Nicole) on macroscopic Bell inequalities. Next Monday we will have a talk by Jonathan Oppenheim at 10:30am in 6C-442 on his proposal for classical gravity. It should be accessible to QI people. The following Monday (Dec 16) will be Anurag Anshu at 10:30am speaking about his recent paper on a subvolume law in 2D systems. Details below. Tomorrow's morning talk. https://toc.csail.mit.edu/node/1360 Dhiraj Holden: No-Signaling Proofs with sqrt(log⁡ n) Provers is in PSPACE Friday, December 6, 2019 - 10:30am to 12:00pm Location: Hewlett, G882 Abstract: No-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover no-signaling proofs, for 2 < k < poly(n) remained an open problem. We show that k-prover no-signaling proofs (with negligible soundness) for k = √(log⁡ n) are contained in PSPACE. We prove this via two different routes that are of independent interest. In both routes we consider a relaxation of no-signaling called sub-no-signaling. Our main technical contribution (which is used in both our proofs) is a reduction showing how to convert any sub-no-signaling strategy with value at least 1 - 2^(-Omega(k^2)) into a no-signaling one with value at least 2^-O(k^2). In the first route, we show that the classical prover reduction method for converting k-prover games into 2-prover games carries over to the no-signaling setting with the following loss in soundness: if a k-player game has value less than 2^(−ck^2) (for some constant c>0), then the corresponding 2-prover game has value at most 1−2(-dk^2) (for some constant d>0). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers. Afternoon talk 1:30pm, Fri, Dec 6, 6C-442 Adam Bene Watts Nonlinear Bell inequality for macroscopic measurements https://arxiv.org/abs/1911.09122 -aram _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip