Non-Signalling Parallel Repetition Using de Finetti Reductions

on YouTube ↗31m

" summary

Proves parallel repetition bounds for no-signalling strategies by applying finite de Finetti reductions to permutation‑invariant strategy distributions, then using local tomography on sampled coordinates to rule out high‑mass signalling components. The amortized winning probability is bounded by the best single‑round strategy (up to a factor tending to 1 with repetitions), extends to any number of players and gives optimal threshold concentration, but incurs a polynomial‑in‑n prefactor with exponential dependence on question/answer alphabet size.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 0:57Permutation invariance
3. 10:46Conditional distributions: "systems"
4. 14:49Extensions & applications
5. 16:06Multiplayer games
6. 19:38The parallel repetition question
7. 20:23Parallel repetition via de Finetti reductions
8. 24:10Controlling the de Finetti states

" related talks

• 55mFoundations 2Iftach Haitner · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 01mDerandomization: A Quick TutorialLijie Chen · Minimal Complexity Assumptions for Cryptography 2023
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 48mOutput-Compressing Randomized Encodings and ApplicationsHuijia Lin · The Mathematics of Modern Cryptography
• 01h 06mDelegating Computation IIYael Tauman Kalai · Cryptography Boot Camp 2015
• 29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round CollapsingVipul Goyal · Secure Computation 2025
• 28mSample-based Proofs of ProximityGuy Goldberg, Guy N. Rothblum · ITCS 2022
• 41mSpotlight TalksRashida Hakim, Chhavi Yadav · Agency in Collaborative Learning 2026