Small Value Parallel Repetition for General Games
summary
Proves a general parallel-repetition bound showing that when a game has initial value 1 − ε the value after n independent repetitions falls exponentially in n with an explicit polynomial dependence on ε (roughly replacing ε by ε^{32} in the decay). Uses correlated sampling, entropy and chain-rule style mutual information bounds and a related sampling theorem to break dependencies between answers. Applies to projection games to get near‑optimal gap amplification and gives new hardness/PCP consequences and connections to the Unique Games framework.
AI-written summary · about
chapters (14)
- 0:002-prover 1-round games
- 1:37Example: CHSH game
- 2:14Projection and unique games
- 2:52Parallel repetition of a game
- 7:03PCP amplification
- 7:55Many other connections
- 8:07Small value regime
- 9:13Main theorem
- 11:23Proof
- 12:29Try 2
- 14:38High level idea
- 19:06Interlude
- 22:13Structure of R
- 24:54Open problems
related talks
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
01h 00mAverage-case Complexity for Polynomials, and All That
01h 02mConsistency of NEXP Not in P/poly in a Strong Theory
56mEntropy, Capacity, and Counting
26mComplete Problems for Multi-Pseudodeterministic Computations
45mImproved Learning from Time-bounded Kolmogorov Complexity
52mThe Mystery of the Missing String
48mUnstructured Hardness to Average-Case Randomness