Source-linked AI summary
Analytical Approach to Parallel Repetition
Irit Dinur, David Steurer
TL;DR
The paper addresses how game value behaves under parallel repetition, especially for projection games with small soundness and for few repetitions. It introduces the relaxation val+, proves that it is multiplicative and approximates true value, and uses these properties to establish new repetition and hardness results. The work also identifies scope boundaries, including unresolved tight bounds in general and an open trade-off between Label Cover soundness and alphabet size.
Problem
It was previously unknown whether parallel repetition decreases the value of projection games whose value is already sub-constant, or how to bound products involving only a few games.
Method
The paper analyzes projection games through the collision value and a relaxation val+, proving approximation via rounding, partial assignments, and correlated sampling.
Results
The relaxation is multiplicative for projection games and supports bounds for small-value games, few repetitions, and products of games, with consequences for Label Cover and Set Cover hardness.
Takeaways & Limitations
The framework gives exponential decay for repeated projection games with small value and yields stronger inapproximability results for Label Cover and Set Cover.
Takeaways & Limitations
Tight parallel repetition bounds remain open in general, and the correct trade-off between Label Cover soundness and alphabet size is unresolved.
Abstract
from arXiv · showhide
We propose an analytical framework for studying parallel repetition, a basic product operation for one-round two-player games. In this framework, we consider a relaxation of the value of a game, $\mathrm{val}_+$, and prove that for projection games, it is both multiplicative (under parallel repetition) and a good approximation for the true value. These two properties imply a parallel repetition bound as $$ \mathrm{val}(G^{\otimes k}) \approx \mathrm{val}_+(G^{\otimes k}) = \mathrm{val}_+(G)^{k} \approx \mathrm{val}(G)^{k}. $$ Using this framework, we can also give a short proof for the NP-hardness of Label-Cover$(1,δ)$ for all $δ>0$, starting from the basic PCP theorem. We prove the following new results: - A parallel repetition bound for projection games with small soundness. Previously, it was not known whether parallel repetition decreases the value of such games. This result implies stronger inapproximability bounds for Set-Cover and Label-Cover. - An improved bound for few parallel repetitions of projection games, showing that Raz's counterexample is tight even for a small number of repetitions. Our techniques also allow us to bound the value of the direct product of multiple games, namely, a bound on $\mathrm{val}(G_1\otimes ...\otimes G_k)$ for different projection games $G_1,...,G_k$.
1 Introduction
The paper develops an analytical framework for parallel repetition in projection games, using a relaxation that supports multiplicative analysis and approximates game value. It derives new bounds for small-value games and few repetitions, with consequences for Label Cover and Set Cover hardness.
- The analytical framework: The framework proves a multiplicative relaxation for projection games and uses it to obtain parallel repetition bounds.The relaxation is designed to approximate the true game value while enabling product analysis.
- Repetition of small-value games: Parallel repetition can reduce projection-game value even when the initial value is sub-constant.This addresses a question left open by earlier work and yields exponential decay with the number of repetitions.
- Hardness consequences: The results yield stronger hardness consequences: it is NP-hard to distinguish Label Cover value 1 from value at most ε, and to approximate Set Cover within (1 −α) ln n.For Set Cover, the reduction runs in time n^O(1/α), and the corresponding time complexity is 2^n^Θ(α) under the stated assumption.
- Few repetitions: For k ≪1/ε^2, the paper gives an improved and tight bound for a projection game with val(G) = 1 −ε.The result matches Raz’s bound even for small k and confirms a conjecture of Ryan O’Donnell.
- The collision-value analysis: Theorem 1.8 bounds the collision value of a product of projection games through a function of one factor and the collision value of the other.It also rules out a projection game G with ∥G ⊗G∥ = ∥G∥ < 1.
- The proof strategy: A rounding procedure connects the relaxation to ordinary game value, using expander mixing for expanding games and a Cheeger-type argument plus correlated sampling otherwise.The procedure may first produce partial assignments for non-expanding games before combining them into a proper assignment.
2 Technique
The paper models projection games as linear operators and analyzes them through collision values and symmetrized constraint graphs. These tools support direct-product arguments and characterize expansion via the associated random walk.
- Game and operator representation: A projection game is represented by a linear operator whose bilinear form gives the success probability of Alice and Bob's assignments.Assignments are nonnegative functions over questions and labels, normalized separately for each question.
- Game and operator representation: The direct product combines games independently, and its operator is the tensor product of the component operators; G⊗k denotes k repeated factors.The product game requires satisfying every component constraint.
- Collision value: The collision value replaces two-player success with a symmetrized process in which two Bob answers must project to the same answer for Alice's question.For projection games, the collision value is quadratically related to the ordinary game value.
- Product monotonicity: Collision value cannot increase when a game is played in parallel with another game, as shown by averaging assignments and a coupling argument.The proof derives an assignment for G from an optimal assignment for G⊗H while preserving the relevant norm inequality.
- Collision value: The collision value equals the square root of the maximum value of a CSP on the symmetrized constraint graph.Randomized assignments yield the CSP value, which equals the square of the collision value.
- Expansion: A game is expanding when its symmetrized constraint graph is an expander, and c-expansion is defined by a spectral gap of at least c.The associated reversible random walk has real eigenvalues, enabling the spectral-gap formulation.
3 The Basic Approach
The section develops multiplicative game parameters for projection games and uses them to derive parallel-repetition bounds. It first introduces λ+ and then refines it to val+, which approximates the usual game value.
- Main theorem: Theorem 1.8 bounds the product norm of projection games by ∥G ⊗ H∥2 ⩽ ϕ(∥G∥2) · ∥H∥2.Repeated application yields a bound on parallel repetitions.
- Parallel repetition: Repeated application gives val(G⊗k)2 ⩽ ϕ(∥G∥2)^k, while ϕ(x) ⩽ 2√x and ϕ(1 − ε) ⩽ 1 − ε2/8.These inequalities yield the stated corollaries, including decay when the base value is bounded away from one.
- Game parameters: val+(G) is designed to upper-bound the relative value loss when G is played in parallel with any projection game H.This parameter is intended to depend on G rather than on the auxiliary game H.
- Game parameters: Theorem 3.2 establishes ∥G ⊗ H∥ ⩽ λ+(G) · ∥H∥, but λ+ is not generally a good approximation to the usual value.λ+ is sufficient for expanding games but requires refinement for non-expanding games.
- Game parameters: Theorem 3.3 establishes ∥G ⊗ H∥ ⩽ val+(G) · ∥H∥ for any two projection games.The paper then shows that val+ is a good approximation of the game value.
- Expanding games: For γ-expanding projection games, λ+(G) > 1 − ε implies ∥G∥ > 1 − O(ε/γ).The argument converts a near-optimal nonnegative assignment into a deterministic assignment and uses expansion.
4 General projection games
This section proves that val+ approximates projection-game value and is multiplicative, including for non-expanding games. The proof converts vector assignments into partial assignments and combines them through correlated sampling.
- Approximation: If ∥G∥2 is small, then val+(G)2 ⩽ 2∥G∥; if ∥G∥2 < 1−ε, then val+(G)2 < 1 − ε2/8.These approximation inequalities provide the link between val+ and the usual game value.
- Approximation: The approximation proof extracts a global assignment from a nonnegative vector assignment for G.The construction proceeds through deterministic slices, randomized rounding, and a final combination step.
- Approximation: Randomized rounding converts each deterministic fractional slice into a distribution over 0/1 partial assignments through a Cheeger inequality for projection games.The rounding preserves the relevant vertex-wise mass while retaining a controlled game value.
- Approximation: The denominator in val+ uses max_v ∥(Tv ⊗ IdΩ) f∥2, forcing the partial assignments to cover every vertex uniformly.This prevents concentration on the same small subgame.
- Approximation: Correlated sampling combines the partial assignments into one global assignment with value at least 1−γ.The players use shared randomness to select a common partial assignment and answer according to it.
- Multiplicativity: val+ is multiplicative under products: val+(G ⊗ G′) = val+(G) · val+(G′).This property is proved after establishing the approximation guarantee and supports parallel-repetition bounds.
5 Few Repetitions — Proof of Theorem 1.7
The proof derives a tight few-repetition bound for projection games by applying an analytic relation between two games and iterating the resulting recurrence. This yields square-root growth in the soundness loss for k much smaller than 1/ε^2.
- Proof ingredients: The proof proceeds through Lemmas 5.2 and 5.3, which round fractional assignments and convert suitable functions into assignments for the game.The intermediate functions satisfy deterministic-slice and norm conditions before rounding.
- Analytic relation: Theorem 5.1 converts high value of G⊗H, together with ∥H∥2 ≤ 1−γ, into a lower bound on ∥G∥2.The proof constructs and derandomizes an assignment, rounds it to a 0/1-valued function, and then recovers an assignment for G.
- Comparison: The bound is worse than the alternative bound from Theorem 1.10 when γ is close to 0.The comparison follows from the term O(η + √(ηγ)) in the derived estimate.
- Analytic relation: Theorem 5.1 is reformulated for games with ∥G∥2 ≤ 1−ε and ∥H∥2 ≤ 1−tε, where 1 ≤ t ≪ 1/ε.This formulation is chosen for the induction proving the few-repetition result.
- Few repetitions: The induction gives ∥G⊗k∥2 ≤ 1 − Ω(k)^1/2 · ε for k ≪ 1/ε^2.Writing ∥G⊗k∥2 = 1−t(k)ε, the recurrence t(k+1) ≥ t(k)+Ω(1/t(k)) implies t(k)^2 = Ω(k).
6 Inapproximability Results
The paper strengthens hardness results for label cover through a new small-soundness reduction and uses the resulting agreement structure in a set-cover reduction. The construction preserves polynomial-size reductions while improving the dependence of alphabet size on soundness.
- Label-cover hardness: The reduction establishes NP-hardness of label covers(1, ε), where satisfiable instances have value 1 and unsatisfiable instances have value at most ε.This is the operational meaning of the label-cover decision problem used by the reduction.
- Label-cover hardness: For every constant α > 0, a reduction maps 3SAT instances of size n to label covers(1, ε) instances of size n^O(1) · poly(1/ε), with s ≤ exp(1/ε^α).The improvement over the prior theorem is that the statement holds for every constant α > 0.
- Label-cover hardness: The new label-cover theorem is obtained by starting from the Moshkovitz–Raz PCP and applying a constant number of parallel repetitions.The construction sets ε1 as a function of ε and α and uses k = 3c/α repetitions.
- Set-cover reduction: For most vertices u, the neighbors of u project to D distinct values under every assignment, giving the required agreement soundness property.The property holds for at least 1−ε1 fraction of vertices when ε1 is sufficiently small relative to α and log n.
- Set-cover reduction: The set-cover construction is complete with |V1| sets when the label-cover instance has a satisfying assignment.For each v, the reduction selects the set indexed by its assigned label.
- Set-cover reduction: Choosing the parameters appropriately yields hardness within factor (1−α) ln N for set cover on instances of size N.The soundness argument derives a contradiction from agreement soundness when a cover is too small.
7 Conclusions
Tight parallel repetition bounds remain open beyond the projection-game setting, including general two-player games, XOR games, and games with more than two parties. The paper also asks whether analytical methods can complement information-theoretic approaches in other areas.
- Open problems: Tight parallel repetition bounds remain open for general non-projection two-player games, XOR games, and games with more than two parties.These cases lie outside the paper’s established tight-bound setting.
- Open problems: The authors ask whether their analytical approach can improve parallel repetition bounds for these broader classes of games.They note that a related approach has already produced a bound for entangled games.
- Broader directions: A broader open question is whether analytical approaches can complement or replace information-theoretic approaches in contexts such as communication complexity.The stated goal is to obtain new bounds or simpler proofs.
A Additional Proofs
The appendix gives a transformation from any projection game to an expanding projection game while preserving perfect value and creating a constant eigenvalue gap. The construction adds trivial constraints and can preserve regularity with controlled degree changes.
- Reduction to expanding games: The transformation produces a projection game G′ with val(G′) = 1 and eigenvalue gap at least γ for a constant γ > 0.This reduction supplies an expanding instance suitable for the paper’s analytic arguments.
- Construction: The construction adds a new vertex u0 with a trivial constraint that accepts when Alice answers 1, regardless of Bob’s answer.The new distribution mixes the original game with a product distribution involving u0.
- Construction: For a (c, d)-regular game, replacing u0 by a suitable set U0 yields a (c, 2d)-regular transformed game.The auxiliary graph between U0 and V is chosen so its symmetrized graph has eigenvalue gap 2γ.
B Feige’s Game
Feige’s game provides a counterexample separating ordinary game value from the collision-norm relaxation: its single and repeated values can remain 1, while the relaxation decreases under repetition. The example motivates proving multiplicativity for the relaxation rather than for val itself.
- Game definition: Feige’s game has val(G) = val(G⊗G) = 1, so ordinary game value need not decrease under parallel repetition.The game uses binary question sets with uniformly likely question pairs and accepts agreement on either player-question pair.
- Implication: The example rules out a useful multiplicative theorem for val and motivates the paper’s multiplicative relation for ∥G∥ using val+.The paper states ∥G ⊗H∥⩽val+(G) · ∥H∥, with val+ bounded away from 1 when val(G) is bounded away from 1.
- Repeated-game strategy: Feige’s strategy for G⊗G wins with probability 1/2 by answering according to whether Bob’s second question matches Alice’s first.Bob answers (Av2, Bv2), hoping that v2 = u1.
- Norm calculation: For Feige’s repeated-game strategy, val(G⊗G, f) = 1/2 while ∥G⊗G f∥2 = 1, illustrating the gap between winning probability and the collision norm.The calculation analyzes the accepted answer tuples for Alice’s possible question pairs.