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