The Exact Communication Threshold for Parallel Repetition
Daiki Suruga
原文摘要
The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all $n$ independent instances of a finite two-player game decays exponentially in $n$, provided that the game has no perfect strategy. The classical theorem assumes that the players cannot communicate, raising the question of how much communication can be allowed while preserving this exponential decay. For every finite total relation $g$ and arbitrary input distribution $μ$, we prove exponential decay at every fixed communication rate below a quantity called zero-error internal information complexity, denoted by $\mathrm{IC}_μ(g,0)$. Together with known results showing that $n\,\mathrm{IC}_μ(g,0)+o(n)$ bits of communication suffice to solve all $n$ instances with success probability tending to one, our bound determines the exact communication threshold. As a by-product, we obtain exact characterizations of amortized distributional and randomized communication complexity under the global-error criterion.
cs.CC