Documentation

MIPRE.Background.Repetition.CommutingRepetition.MainTheorem.Main

theorem CommutingRepetition.uniform_parallel_repetition :
∃ (c : ), 0 < c ∀ (X Y A B : Type) [inst : Fintype X] [inst_1 : Fintype Y] [inst_2 : Fintype A] [inst_3 : Fintype B] [Nonempty X] [Nonempty Y] [Nonempty A] [Nonempty B] (G : Game X Y A B) (n : ), 1 n(G.repeat n).omegaCO Real.exp (-(c * ((1 - G.omegaCO) ^ 7 / (1 - G.omegaCO + Real.log ((Fintype.card A) * (Fintype.card B))))) * n)

Uniform direct parallel repetition for commuting-operator strategies (07_main_theorem.tex, Theorem 7.1): there is a universal c > 0 such that for every finite game G with payoffs in [0,1] and every n ≥ 1, ω^co(G^{⊗n}) ≤ exp(−c·n·ε⁷/(ε + log(|A||B|))) where ε = 1 − ω^co(G).

theorem CommutingRepetition.uniform_parallel_repetition_pow13 :
∃ (c : ), 0 < c ∀ (X Y A B : Type) [inst : Fintype X] [inst_1 : Fintype Y] [inst_2 : Fintype A] [inst_3 : Fintype B] [Nonempty X] [Nonempty Y] [Nonempty A] [Nonempty B] (G : Game X Y A B) (n : ), 1 n(G.repeat n).omegaCO Real.exp (-(c * ((1 - G.omegaCO) ^ 13 / (1 - G.omegaCO + Real.log ((Fintype.card A) * (Fintype.card B))))) * n)

Power-thirteen corollary (07_main_theorem.tex, Corollary 7.2): some universal constant gives the ε¹³ bound. The paper's "with the same universal constant" is not encoded by this second ∃ c (a deliberate weaker-but-true rendering recorded in DIFFERENCES.md); the main theorem's constant does work, since ε⁷ ≥ ε¹³ on [0,1].