Abstract
Parallel repetition theorems are fundamental tools in theoretical computer science, primarily used for amplifying the hardness of approximation in various computational problems. While the two-prover case is well-understood, the multiprover setting—especially under nonsignalling constraints—has historically required complex combinatorial machinery. This paper presents a streamlined, purely information-theoretic proof for the multiprover nonsignalling parallel repetition theorem. By leveraging a change of measure technique and drawing parallels to multiuser rate-distortion theory, the authors establish exponential decay of the winning probability without the need for de Finetti-type structural decompositions.
Introduction
In the study of interactive proof systems and the hardness of approximation, the concept of a multi-prover game is central. In a typical scenario, a verifier sends queries to multiple provers who are physically separated and cannot communicate. The goal of the provers is to provide answers that satisfy a specific predicate. If the maximum probability of winning a single round of the game is $v < 1$, a natural question arises: how quickly does the winning probability decay if the game is played $n$ times in parallel?
Ideally, one might expect the probability to decay as $v^n$. However, provers can employ sophisticated strategies involving shared correlations—such as quantum entanglement or broader nonsignalling correlations—to achieve higher winning probabilities than independent play would suggest. Proving that the winning probability still decays exponentially with $n$ is the objective of a parallel repetition theorem. While this has been established for two-prover games, the multiprover case has remained significantly more challenging, often requiring mathematically dense "de Finetti type" decompositions to handle the dependencies between players.
The Problem: Beyond Two Provers
The difficulty in multiprover parallel repetition stems from the complex entanglement of strategies when more than two parties are involved. In the nonsignalling model, provers are constrained only by the requirement that their individual responses do not allow for communication between them. Previous proofs for this setting relied on structural theorems that decompose a global distribution into a convex combination of product distributions. While effective, these methods are often non-intuitive and technically cumbersome.
This research addresses the need for a more direct approach. The authors seek to answer whether the tools of information theory—specifically those used in proving strong converses in communication theory—can provide a more elegant path to proving exponential decay in multiprover games.
Methodology: Information-Theoretic Change of Measure
The core of the new proof is a "change of measure" strategy, a technique borrowed from information theory typically used to show that exceeding a channel's capacity leads to an error probability approaching one. The methodology follows four primary stages:
1. Softening Constraints
Traditional proofs often struggle with the "hard" constraints of nonsignalling strategies. The authors replace these with "soft" constraints using Kullback-Leibler (KL) divergence. Instead of requiring absolute conditional independence, they bound the divergence between the actual distribution and a target distribution, allowing for a more flexible mathematical treatment.
2. Change of Measure
The proof analyzes the probability of winning by shifting the perspective to a new probability distribution. This distribution is obtained by conditioning the original game distribution on the event that the provers actually win the game. By comparing this "winning" distribution to the original, the authors can quantify the cost of winning in terms of information.
3. Tensorization
A critical component of the proof is Lemma 5, which establishes a "tensorization" property. This allows the researchers to relate the complex, $n$-fold repeated game back to the properties of a single instance of the game. This step is vital for showing that the constraints on the provers in the repeated game translate to constraints on their behavior in any individual round.
4. Single-Letterization
By utilizing the soft constraints and KL divergence, the authors bound the expected number of wins in the $n$-fold game using the value of a "single-letter" game. This reduces a high-dimensional problem into a manageable single-game analysis.
Key Insights: The Rate-Distortion Connection
The paper’s most significant conceptual leap is the recognition that parallel repetition is essentially an exponential strong converse problem for a multiuser rate-distortion system with zero communication. By framing the problem this way, the authors can use the standard toolkit of information theory—entropy, mutual information, and the chain rule—rather than relying on heavy combinatorics.
Furthermore, the proof targets "sub-nonsignalling" strategies. These are a generalization of nonsignalling strategies where the response distributions are subnormalized (summing to $\leq 1$). This broader focus actually simplifies the proof, as the set of sub-nonsignalling strategies possesses better mathematical properties (such as being a convex body) than the standard set.
Results
The primary result of the paper is Theorem 4, which confirms the exponential decay of the winning probability. For a multiprover game $G$, the probability of winning more than a fraction $\Delta$ of $n$ games (where $\Delta$ exceeds the single-game sub-nonsignalling value $\rho_{SNS}(G)$) is bounded as follows:
$$\rho_{SNS}(G^n, \Delta) \leq \exp\left( -n \frac{\nu^2}{C_m} \right)$$
Here, the constant $C_m$ in the exponent depends only on the number of provers $m$, specifically scaling as $O(2^{2m})$. This makes the result universal for any game with a fixed number of players. The proof successfully provides a completely information-theoretic framework that bypasses the de Finetti reductions used in earlier landmark works, such as those by Lancien and Winter (2016).
Limitations and Future Research
While the proof is a significant step forward in clarity and methodology, it currently applies only to nonsignalling and sub-nonsignalling strategies. It does not yet extend to the "standard" classical setting (strategies satisfying hidden variable theory), which is the most common model in classical computer science.
The authors note that applying this technique to the standard two-prover case is difficult because it is hard to identify a "soft constraint" that captures the specific Markov chain structure required for classical strategies. Future research will likely focus on finding an "approximate tensorization property" for the value function under suitable soft constraints to bridge the gap between nonsignalling and classical parallel repetition.
Summary updated