Monogamy of Non-signaling Correlations

on YouTube ↗52m

" summary

Shows that any k‑extendable non‑signaling box has a local hidden‑variable approximation with trace‑distance error O(sqrt((log |A|)/k)), proved by bounding conditional mutual information and converting to variation distance via Pinsker's inequality. Uses linear programs over k extensions, gives a rounding that yields separable quantum states for k‑extendable states, and yields quasi‑polynomial algorithms (take k = O((log m)/ε^2)) for free‑game value and ε‑Nash. Leaves open switching the quantifiers (one q that works for all input distributions) and explicit non‑signaling counterexamples.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:34"correlations" (multipartite conditional probability distributions)
3. 1:41why study boxes?
4. 3:06why non-signalling?
5. 9:12monogamy
6. 22:42proof idea of thm 1
7. 24:31proof sketch of thm 1
8. 27:05what about the inputs?
9. 31:59finding (approximate) Nash eq
10. 34:15algorithm for approx Nash
11. 36:55application: free games
12. 40:05E-nets vs. info theory
13. 42:02general games? Theorem 1: If p is k-extendable and is a distribution
14. 43:15general quantum games
15. 45:15open questions 1. Switch quantifiers and find a separable approximation (a) independent of the distribution on measurements (b) with error depending on the size of the output. 2. We know the non-signalling version of this is false. Can we find a simple counter-example?