The focus of this paper is multi-player games, and in particular their asymptotic behavior under parallel repetition. Multi-player games consist of a one-round interaction between a referee and k players. In this interaction, the referee first samples a "query" (q 1 , . . . , q k ) from some joint query distribution Q, and for each i sends q i to the i th player. The players are required to respectively produce "answers" a 1 , . . . , a k without communicating with one another (that is, each a i is a function only of q i ) and they are said to win the game if (q 1 , . . . , q k , a 1 , . . . , a k ) satisfy some predicate W that is fixed and associated with the game.
Suppose that a game G has the property that the maximum probability with which players can win is 1 -ϵ, no matter what strategy they use. This quantity is called the value of G. The parallel repetition question [13] asks How well can the players concurrently play in n independent copies of G? More precisely, consider the following k-player game, which we call the n-wise parallel repetition of G and denote by G n : 1. The referee samples, for each i ∈ [n] independently, query tuples (q i 1 , . . . , q i k ) ∼ Q. We refer to the index i as a coordinate of the parallel repeated game. 2. The j th player is given (q 1 j , . . . , q n j ) and is required to produce a tuple (a 1 j , . . . , a n j ). 3. The players are said to win in coordinate i if (q i 1 , . . . , q i k , a i 1 , . . . , a i k ) satisfies W . They are said to win (without qualification) if they win in every coordinate i ∈ [n].
One might initially conjecture that the value of G n is (1 -ϵ) n . However, this turns out not to be true [14,9,12,25], as players may benefit from correlating their answers across different coordinates. Still, Raz showed that if G is a two-player game, then the value of G n is 2 -Ω(n) , where the Ω hides a game-dependent constant [23,17]. Tighter results, based on the value of the initial game are also known [8,5]. For many applications, such bounds are qualitatively as good as the initial flawed conjecture.
Games involving three or more players have proven more difficult to analyze, and the best known general bound on their parallel repeated value is due to Verbitsky [26]. This bound states that the value of G n approaches 0, but the bound is extremely weak (it shows that the value is at most 1 α(n) , where α denotes an inverse Ackermann function). The weakness of this bound is generally conjectured to reflect limitations of current proof techniques rather than a fundamental difference in the behavior of many-player games. In the technically incomparable but related no-signaling setting however, Holmgren and Yang showed that three-player games genuinely behave differently than two-player games [19]. Specifically, they showed that there exists a three-player game with "no-signaling value" bounded away from 1 such that no amount of parallel repetition reduces the no-signaling value at all.
Parallel repetition is a mathematically natural operation that we find worthy of study in its own right. At the same time, parallel repetition bounds have found several applications in theoretical computer science (see this survey by [24]). For example, parallel repetition of 2 player games shares intimate connections with multi-player interactive proofs [4], probabilistically checkable proofs and hardness of approximation [3,10,16], geometry of foams [11,20, 1], quantum information [6], and communication complexity [22,2]. Recent work also shows that strong parallel repetition for a particular class of multiprover games implies new time lower bounds on Turing machines that can take advice [21].
Dinur et al. [7] describe a restricted class of multi-player games for which Raz's approach generalizes (giving exponential parallel bounds). Specifically, they consider games whose query distribution satisfies a certain connectivity property. For games outside this class, Verbitsky's bound was the best known. Dinur et al. highlighted one simple three-player game, called the GHZ game [15], that in some sense is maximally far from the aforementioned tractable class of multi-player games. In the GHZ game, the players' queries are (q 1 , q 2 , q 3 ) chosen uniformly at random from {0, 1} 3 such that q 1 ⊕ q 2 ⊕ q 3 = 0, and the players' goal is to produce (a 1 , a 2 , a 3 ) such that a 1 ⊕ a 2 ⊕ a 3 = q 1 ∨ q 2 ∨ q 3 . Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general games. The GHZ game has also played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds will find applications in this setting as well.
In a recent work, Holmgren and Raz [18] proved the following polynomial upper bound on the parallel repetition of the GHZ game:
▶ Theorem 1. The value of the n-wise repeated GHZ game is at most n -Ω(1) .
Our main contribution is a different proof of this theorem that, in our view, is significantly simpler and more direct than the proof of [18]. Like [18], we actually do not rely on any properties of the GHZ game other than its query distribution, and in particular we do not rely on specifics of the win condition. Furthermore, unlike most previous works on parallel repetition, our proof makes no use of information theory, and instead relies on the use of Fourier analysis.
Let P denote the distribution of queries in the n-wise parallel repeated GHZ game. Let α = Θ(1/n ε ) for a small constant ε > 0 and E = E 1 × E 2 × E 3 be any product event with significant probability under P, i.e., P(E) ≥ α. The core of our proof is establishing that for a random coordinate i ∈ [n], the query distribution P|E (P conditioned on E) is mildly hard in the i th coordinate. That is, given queries sampled from P|E, the players' maximum winning probability in the i th coordinate is bounded away from 1. Using standard arguments from the parallel repetition literature, this will imply an inverse polynomial bound for the value of the n-fold GHZ game. The difficulty, as usual, is that the n different queries in P|E may not be independent.
Our approach at a high level is to: 1. Identify a class D of simple distributions (over queries for the n-wise repeated GHZ game) such that it is easy to analyze (in step 3 below) which coordinates are hard for any given D ∈ D. By hard, we mean that the players' maximum winning probability in the i th coordinate is 3 4 . 2. Approximate P|E by a convex combination of distributions from D. That is, we write
where {D j } are distributions in D, p j are non-negative reals summing to 1, and ≈ denotes closeness in total variational distance. 3. Show that in the above convex combination, "most" of the D i have many hard coordinates.
More precisely, if we sample j with probability p j , then the expected fraction of coordinates in which D j is hard is at least a constant (say 1/3). Completing this approach implies that if i ∈ [n] is uniformly random, then the i th coordinate of P|E can be won with probability at most 1 -Ω(1). We elaborate on each of these steps below.
Parallel Repetition for the GHZ Game: A Simpler Proof
For our class of "simple" distributions D, we introduce the notion of a "bow tie" distribution. We then define D to be the set of all bow tie distributions. A bow tie is a set B of the form
such that for each (x, y, z) in B, we have x + y + z = 0. In particular this requires that
A bow tie distribution is the uniform distribution on a bow tie. Our name of "bow tie" is based on the fact that bow ties are thus determined by {(x 0 , y 0 ), (x 0 , y 1 ), (x 1 , y 0 ), (x 1 , y 1 )}, which we sometimes view as a set of edges in a graph. In this case, bow ties are special kinds of K 2,2 subgraphs, where K 2,2 denotes the complete bipartite graph.
The main property of a bow tie distribution D is that for every coordinate i for which (x 0 ) i ̸ = (x 1 ) i (equivalently (y 0 ) i ̸ = (y 1 ) i , or (z 0 ) i ̸ = (z 1 ) i ), the i th coordinate of D is as hard as the GHZ game (i.e. players cannot produce winning answers for the i th coordinate with probability more than 3 4 ). This follows by "locally embedding" the (unrepeated) GHZ query distribution into the i th coordinate of D as follows. We first swap x 0 ↔ x 1 , y 0 ↔ y 1 , z 0 ↔ z 1 as necessary to ensure that
An even number of swaps are required to do this by the assumption that x 0 + y 0 + z 0 = 0, and bow ties are invariant under an even number of such swaps. Thus Equation (1) is without loss of generality. Suppose f1 , f2 , f3 : F n 2 → F 2 comprise a strategy for the i th coordinate of D. Then a strategy f 1 , f 2 , f 3 : F 2 → F 2 for the basic (unrepeated) GHZ game can be constructed as
The winning probability of this strategy is the same as the winning probability of f1 , f2 , f3 in the i th coordinate because (x b1 ) i , (y b2 ) i , (z b3 ) i = (b 1 , b 2 , b 3 ). Hence both probabilities are at most 3/4.
We now sketch how to approximate P|E by a convex combination of bow tie distributions, where E is a product event E 1 × E 2 × E 3 . We assume for now that the non-zero Fourier coefficients of each E j are small. We will return to this assumption at the end of the overview -it turns out to be nearly without loss of generality.
We show that P|E is close in total variational distance to the distribution obtained by sampling a uniformly random bow tie B ⊆ E, and then outputting a random element of B. The latter distribution is equivalent to sampling (x, y, z) with probability proportional to the number of bow ties B ⊆ E that contain (x, y, z). This number is
where we identify E 1 , E 2 , and E 3 with their indicator functions. Note that we are subtracting 1 to cancel the term corresponding to z ′ = z.
Intuitively, the fact that all E j have small Fourier coefficients means that they look random with respect to linear functions. Thus, one might guess that the above sum is close to 2 n • µ(E 1 )µ(E 2 )µ(E 3 ) for most (x, y, z) ∈ supp(P|E), where µ(S) = |S|/2 n denotes the measure of S under the uniform distribution on F n 2 . If "close to" and "most" have the right meanings, then this would imply that our distribution is close in total variational distance to P|E as desired.
Our full proof indeed establishes this. More precisely, we view Equation (2) as a vector indexed by (x, y, z) and establish bounds on that vector's ℓ 1 and ℓ 2 norms as a criterion for near-uniformity. In the process our proof repeatedly uses the following claims (see Lemma 16). For all sets S, T ⊆ F n 2 that are sufficiently large, we have
and
For the final step of our proof, we need to show that the distribution of bow ties analyzed in the previous step produces (with high probability) bow ties that differ in many coordinates. We begin by parameterizing a bow tie by (x 0 , y 0 , x 0 ⊕ x 1 ) and noting that in the previous step, we essentially showed that E contains 2 3n-O(log n) different bow ties. The O(log n) term in the exponent arises from the fact that the events {E j } have density in F n 2 that is inverse polynomial in n. A simple counting argument then shows that for a random bow tie, the min-entropy of x 0 ⊕ x 1 is close to n. This means that x 0 ⊕ x 1 is close to the uniform distribution in the sense that any event occurring with probability p under the uniform distribution occurs with probability p • n O(1) under the distribution of x 0 ⊕ x 1 . Thus we can finally apply a Chernoff bound to deduce that with all but 2 -Ω(n) probability, x 0 ⊕ x 1 has Hamming weight at least n/3.
In other words, a bow tie sampled uniformly at random differs in at least a 1 3 fraction of coordinates. By the main property of bow ties, this implies that the corresponding bow tie distribution is hard on a 1 3 fraction of coordinates (indeed, the same set of coordinates).
For general (product) events E = E 1 × E 2 × E 3 (where the sets {E i } need not have small Fourier coefficients), we can partition the universe
into parts π such that for most of the parts π, the event E restricted to π has the structure that we already analyzed. For this to make sense, we ensure several properties of the partition. First, π should be a product set (π = π 1 × π 2 × π 3 ) so that E ∩ π is a product set as well, i.e. E ∩ π has the form Ẽ1 × Ẽ2 × Ẽ3 . Second, each π i should be an affine subspace of F n 2 so that we can do Fourier analysis with respect to this subspace. Finally π 1 , π 2 , and π 3 should all be affine shifts of the same linear subspace so that the set {(x, y, z) ∈ π : x + y + z = 0} has the same Fourieranalytic structure as the parallel repeated GHZ query set {(x, y, z) ∈ (F n ′ 2 ) 3 : x + y + z = 0} for some n ′ < n.
We prove the existence of such a partition with n ′ not too small (n ′ = n -o(n)) by a simple iterative approach, which is similar to [18].
Our proof has some similarity to [18] -in particular, both proofs partition (F n 2 ) 3 into subspaces according to Fourier-analytic criteria and analyze these subspaces separately -but the resemblance ends there. In fact, there are fundamental high-level differences between the two proofs.
The biggest qualitative difference is that our high-level approach decomposes any conditional distribution P|E into components (bow tie distributions) for which many coordinates are hard. [18] takes an analogous approach, but it establishes a weaker result that differs in the order of quantifiers: it first fixes a strategy f , and then decomposes P|E into components such that f performs poorly on many coordinates of many components. This difference is due to the fact that [18] uses uniform distributions on high-dimensional affine spaces as their basic "hard" distributions. It is not in general possible to express P|E as a convex combination of such distributions (for example if each E j is a uniformly random subset of
2 ). Instead, [18] expresses P|E as a convex combination of "pseudo-affine" distributions. This significantly complicates their proof, and we avoid this complication entirely by our use of bow tie distributions, which are novel to this work.
The remainder of our proof (the analysis of hardness within each part of the partition) is entirely different.
A significant portion of these preliminaries is taken verbatim from [18]. We write exp(t) to denote e t for t ∈ R.
Let n ∈ N. For a vector v ∈ R n and i ∈ [n], we write v(i) or v i to denote the i-th coordinate of v. For p ∈ N, we write ∥v∥
to denote the ℓ p norm of v.
For z ∈ {0, 1} * , hwt(z) def = ∥z∥ 1 denotes the Hamming weight of z. We crucially rely on the Cauchy-Schwarz inequality.
Let Ω be a universe. By a partition of Ω, we mean a collection of pairwise disjoint subsets of Ω, whose union equals Ω. If Π is a partition of Ω and ω is an element of Ω, we will write Π(ω) to denote the (unique) element of Π that contains ω. Thus, we can view Π as a function Π : Ω → 2 Ω . For a set S ⊆ Ω, we identify S with its indicator function S : Ω → {0, 1} defined at ω ∈ Ω by
For sets S, T ⊆ Ω such that T ̸ = ∅, we use S| T ⊆ T to denote the set S ∩ T when viewed as a subset of T . In particular, S| T is an indicator function from T to {0, 1}.
U. Girish, J. Holmgren, K. Mittal, R. Raz, and W. Zhan 62:7
Let P be a distribution over a universe Ω. We sometimes think of P as a vector in R |Ω| whose value in coordinate ω ∈ Ω is P (ω). In particular, we use ∥P -Q∥ 1 to denote the ℓ 1 norm of the vector P -Q ∈ R |Ω| , where P and Q are probability distributions. We use ω ∼ P to denote a random element ω distributed according to P . We use supp(P ) = {ω ∈ Ω : P (ω) > 0} to denote the support of the distribution P .
Let Σ be any alphabet. We say that X : Ω → Σ is a Σ-valued random variable. If Σ = R, we say that the random variable is real-valued. If X is a real-valued random variable, the expectation of X under P is denoted E ω∼P [X(ω)]. Often, the underlying distribution P is implicit, in which case we simply use E[X]. If X is a Σ-valued random variable and P is a probability distribution, we write P X or X(P ) to denote the induced probability distribution of X under P , i.e., P X (σ) = (X(P ))(σ) def = P (X = σ) for all σ ∈ Σ. In particular, we say that X is distributed according to P X and we use σ ∼ X(P ) to denote a random variable σ distributed according to P X . The distribution P is often implicit, and we identify X with the underlying distribution P X .
We refer to subsets of Ω as events. We use standard shorthand for denoting events. For instance, if X is a Σ-valued random variable and x ∈ Σ, we write X = x to denote the event {ω ∈ Ω : X(ω) = x}. Similarly, for a subset F ⊆ Σ, we write X ∈ F to denote the event {ω ∈ Ω : X(ω) ∈ F }. We use P (E) to denote the probability of E under P . When P is implicit, we use the notation Pr(E) to denote P (E).
Let E ⊆ Ω be an event with P (E) > 0. Then the conditional distribution of P given E is denoted (P |E) : Ω → R and is defined to be
If E is an event, we write P X|E as shorthand for (P |E) X .
For any set S ⊆ Ω, we sometimes identify S with the uniform distribution over S. In particular, we use x ∼ S to denote x sampled according to the uniform distribution on S.
For S, π ⊆ Ω such that π ̸ = ∅, we use µ π (S) = |S∩π| |π| to denote the measure of S under the uniform distribution over π. When π = Ω, we omit the subscript and simply use µ(S).
For any (finite) vector space V over F 2 , the character group of V, denoted V, is the set of group homomorphisms mapping V (viewed as an additive group) to {-1, 1} (viewed as a
Parallel Repetition for the GHZ Game: A Simpler Proof multiplicative group). Each such homomorphism is called a character of V. For functions mapping V → R, we define the inner product
The character group of V forms an orthonormal basis under this inner product. We refer to the all-ones functions χ : V → {-1, 1}, χ ≡ 1 as the trivial character or the zero character and denote this by χ = ∅.
For all characters χ ̸ = ∅, since ⟨χ, ∅⟩ = 0, we have
, where we identify S with its indicator function S : V → {0, 1} as mentioned before. For
. ▶ Fact 3. Given a choice of basis for V, there is a canonical isomorphism between V and V. Specifically, if V = F n 2 , then the characters of V are the functions of the form
▶ Definition 4. For any function f : V → R, its Fourier transform is the function
Since the characters of V are orthonormal and V is finite, we can deduce that f is equal to
An important special case of Plancherel's theorem is Parseval's theorem:
Fix any subspace V ⊆ F n 2 and a vector a ∈ F n 2 . Let U = a + V denote the affine subspace obtained by shifting V by a. For every function f : V → R, we associate it with a function f a : U → R defined by f a (x) = f (x + a) for all x ∈ U. This is a bijective correspondence between the set of functions from U to R and the set of functions from V to R. Under this association, we can identify χ ∈ V with χ a : U → {-1, 1} where χ a (x) = χ(x + a) for all x ∈ U. This defines an orthonormal basis U a := {χ a : U → {-1, 1} | χ ∈ V} for the vector space of functions from U to R. We call this the Fourier basis for U with respect to a. This basis depends on the choice of the shift a ∈ U. However, for all possible shifts b ∈ U and character functions χ ∈ V, the functions χ a and χ b only differ by a sign. To see this, observe that
We will sometimes ignore the subscript and simply use χ ∈ V to index functions in the Fourier basis of U. This is particularly the case when the properties we are dealing are independent of choice of basis (for example, the absolute values of Fourier coefficients of a function).
In parallel repetition we often work with Cartesian product sets of the form (X
For these sets, we will use subscripts to index the inner product and superscripts to index the outer product. That is, for X = X 1 × . . . × X k we view elements x of X n as tuples (x 1 , . . . , x k ), where x i ∈ X n i . We use x j i or x i (j) to refer to the j th coordinate of x i . We use x j to denote the vector (x j 1 , . . . , x j k ).
Q is a probability measure on X , and W : X × Y → {0, 1} is a "winning" predicate. We refer to Q as the query distribution or the input distribution of the game.
The most important quantity associated with a game is the maximum probability with which the game can be "won".
▶ Definition 9. The value of a k-player game G = (X , Y, Q, W ), denoted val(G), is the maximum, over all deterministic strategies f , of val(G, f ).
It is often easier to construct probabilistic strategies for a game, i.e. strategies in which players may use shared and/or individual randomness in computing their answers.
▶ Definition 10 (Probabilistic Strategies). Let G = (X , Y, Q, W ) be a k-player game. A probablistic strategy for G is a distribution F of deterministic strategies for G. The success probability of F in G is denoted and defined as
A standard averaging argument implies that for every game, probabilistic strategies cannot achieve better success probability than deterministic strategies: ▶ Fact 11. Replacing "deterministic strategies" by "probabilistic strategies" in Definition 9 yields an equivalent definition.
The main operation on multi-player games that we consider in this paper is parallel repetition:
▶ Definition 12 (Parallel Repetition). Given a k-player game G = (X , Y, Q, W ), its n-fold parallel repetition, denoted G n , is defined as the k-player game (X n , Y n , Q n , W n ), where W n (x, y) def = n j=1 W (x j , y j ). For x ∈ X n , we refer to x i ∈ X n i as the input to the i-th player.
To bound the value of parallel repeated games, it is helpful to analyze the probability of winning in a particular instance of the game under various modified query distributions.
) is a game (with a product winning predicate), the value of G in the j th coordinate for j ∈ [n], denoted val (j) (G), is the value of the game (X , Y, Q, W ′ ), where W ′ (x, y) = W (x j , y j ).
▶ Definition 14 (Game with Modified Query Distribution). Let G = (X , Y, Q, W ) be a game. For a probability measure P on X , we write G|P to denote the game (X , Y, P, W ). For an event E on X , we write G|E to denote the game (X , Y, Q E , W ).
Let Q denote the uniform distribution over {(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)}. Define W : X × Y → {0, 1} at x ∈ X , y ∈ Y by W (x, y) = 1 if and only if x 1 ∨ x 2 ∨ x 3 = y 1 + y 2 + y 3 (mod 2). The GHZ game refers to the 3-player game (X , Y, Q, W ), which has value 3/4. The n-fold repeated GHZ game refers to the n-fold parallel repetition of (X , Y, Q, W ). Our parallel repetition results easily generalize with any other (constant-sized) answer alphabet Y ′ and any predicate W ′ , as long as the game (X , Y ′ , Q, W ′ ) has value less than 1.
We typically use X = (X 1 , X 2 , X 3 ) ∈ X n to denote a random variable distributed according to Q n where X i ∈ X n i denotes the input to the i-th player.
We make use of the notion of affine partition similar to the one defined in [18]. We say that Π is an affine partition of (F n 2 ) 3 of codimension at most d if Π is a partition on (F n 2 ) 3 and: Each part π ∈ Π has the form a π + V 3 π where V π is a subspace of F n 2 and a π ∈ (F n 2 ) 3 , and Each V π has codimension at most d. The main take-away from this section is Proposition 15, which states the following: Given the query distribution to the n-fold GHZ game, and a product event E ⊆ (F n 2 ) 3 with large enough probability mass, we can find an affine partition Π of (F n
2 ) 3 such that on a typical part π ∈ Π, the non-zero Fourier coefficients of the indicator functions
Formally, the proposition is as follows: 3 be such that P(E) = α. For all δ > 0, there exists an affine partition Π of (F n 2 ) 3 of codimension at most 3 δ 3 such that the following holds. With probability at least 1 -δ α over π ∼ Π(P|E), for all i ∈ [3] and non-zero χ ∈ V, we have
Recall that Π(P|E) is the distribution induced by sampling x ∼ P|E and outputting the part of Π to which x belongs. Note that in the statement of the proposition, we don't specify a choice of Fourier basis for π i . This is because for any set S ⊆ π i , the quantity S(χ ai ) is independent of choice of a i ∈ π i so we simply write S(χ) . The proof of Proposition 15 is similar in nature to the proof of Lemma 6.2 in [18], but is much simpler and is presented in the full version of the paper.
We crucially make use of the following lemma, the proof of which can be found in the full version of the paper.
If furthermore for all non-zero χ ∈ V, we have B(χ) ≤ δ 2 , then
Recall from Section 2.2 that µ πi (S) ≜ |S∩πi| |πi| . In the statement of this lemma, we don't specify a choice of Fourier basis for π 2 and π 3 . Since the properties C(χ a3 ) ≤ δ 1 and B(χ a2 ) ≤ 2 are independent of the choice of a 2 and a 3 , we simply write C(χ) ≤ δ 1 and
We use the following Parallel Repetition Criterion which is similar to, but weaker than the one from [18] for the GHZ game and has a slightly simpler proof. Let G refer to the n-fold parallel repetition of the GHZ game. Let P = Q n .
▶ Lemma 17 (Parallel Repetition Criterion). Let c ∈ (0, 1] be a constant and ρ(n) : N → R be a function such that ρ(n) ≥ exp(-n). Suppose for all large n ∈ N and all subsets
This lemma is proved in [18] under the weaker assumption that there is some coordinate i ∈ [n] for which val (i) (G|E) ≤ 1 -c. The proof is slightly simpler under our stronger assumption that E i∼[n] val (i) (G|E) ≤ 1 -c. We prove this in Appendix A.1.
and n be large enough. It suffices to show that E i∼[n] val (i) (G|E) ≤ 0.95. We do this as follows.
Let δ = α 20 n 1/40 . Proposition 15 implies the existence of a partition Π of (F n 2 ) 3 into affine subspaces of codimension at most
Every π ∈ Π is of the form a + V 3 where V ⊆ F n 2 is a subspace and a ∈ (F n 2 ) 3 . With probability at least 1 -δ P(E) ≥ 1 -o(1) over π ∼ Π(P|E), we have E i | πi (χ) ≤ δ for all i ∈ [3] and non-zero χ ∈ V, where V is the subspace of F n 2 for which π is an affine shift of V 3 .
Under the distribution Π(P|E), the probability that π is sampled equals (P|π)(E)•P(π) P(E) by Bayes' rule. This implies that the probability that π ∼ Π(P|E) satisfies (P|π)(E) ≤ P(E)/10 is at most 1/10. We will focus on π = π 1 × π 2 × π 3 that satisfy both these properties, namely, the measure of E under P|π is significant, furthermore, for all i ∈ [3], all non-zero Fourier coefficients of the sets E i restricted to π i are small. ▶ Definition 18. We say that π is good if (P|π)(E) ≥ α/10, and for all non-zero χ ∈ V and i ∈ [3], we have
By a union bound, a random π ∼ Π(P|E) will be good with probability at least 1 -1 10 -δ α . Fix any such good π = π 1 × π 2 × π 3 ∈ Π, and let V be the subspace such that π is an affine shift of V 3 .
For all z ∈ E 3 ∩ π 3 , define a (partial) matching M z between π 1 and π 2 as follows. For
be the bipartite graph between π 1 and π 2 obtained by combining edges from the matchings for z ∈ E 3 ∩π 3 . Let E(G) denote the set of edges in G. For every edge e ∈ E(G), we can identify e with a valid input to the n-fold GHZ game that is contained in E ∩ π. Namely, we associate (x 0 , y 0 ) ∈ E(G) to the input (x 0 , y 0 , x 0 + y 0 ) ∈ supp(P) ∩ E ∩ π. This is a bijective correspondence because of the way we defined the graph G. Under this correspondence, the uniform distribution over edges of G corresponds to the distribution P|E, π. We now introduce the important notion of a bow tie.
▶ Definition 19 (Bow Tie). We say that a subset of edges b ⊆ E(G) is a bow tie if b = {x 0 , x 1 } × {y 0 , y 1 } for some x 0 ̸ = x 1 ∈ π 1 , y 0 ̸ = y 1 ∈ π 2 such that x 0 + y 0 = x 1 + y 1 (or equivalently x 0 + y 1 = x 1 + y 0 ). Alternatively, for z 0 = x 0 + y 0 and z 1 = x 0 + y 1 , we have (x i , y j , z k ) ∈ supp(P) for all (i, j, k) ∈ supp(Q).
Let b = {x 0 , x 1 } × {y 0 , y 1 } be a bow tie. As before, we identify b with the indicator vector b ∈ {0, 1} E(G) of the edges of b, that is, b(e) = 1 iff e ∈ {(x i , y j ) : i, j ∈ {0, 1}}. We use b to denote the uniform distribution on the edges of the bow tie, when viewed as inputs to the n-fold GHZ game. More precisely, b denotes the uniform distribution on {(x i , y j , x i + y j ) | i, j ∈ {0, 1}}.
We say that b differs in the i-th
Let b be a bow tie and I ⊆ [n] be the coordinates on which b differs. The following claim shows that val (i) (G| b) ≤ 3/4 for all i ∈ I. The proof is deferred to Appendix A.2 ▷ Claim 20. Let b = {x 0 , x 1 }×{y 0 , y 1 } be a bow tie. Let I ⊆ [n] be the subset of coordinates on which b differs. Then, val (i) (G| b) ≤ 3/4 for all i ∈ I.
Let B denote the set of all bow ties. Consider the distribution on edges defined by first sampling a uniformly random bow tie from B, and then a uniformly random edge from the bow tie. We now provide an alternate description of this distribution. For each z ∈ E 3 ∩ π 3 , define 1 z ∈ {0, 1} |E(G)| as follows. For each e = (x, y) ∈ E(G), define 1 z (e) = 1 if x and y are both matched in M z but not to each other, and define 1 z (e) = 0 otherwise. Alternatively, 1 z is the indicator of the set ((
each of which have non-negative values, so v induces a distribution on E(G). Consider this distribution ṽ = v ∥v∥1 on E(G) defined by normalizing v. We show that this distribution is an alternate description of the aforementioned distribution.
In particular, we can think of the distribution ṽ := v ∥v∥1 on E(G) as obtained by sampling a uniformly random bow tie b in G and outputting a uniformly random edge of b.
The proof of this is deferred to Appendix A.3. Our goal now is to show that the distribution ṽ is close to the uniform distribution over edges of G. To do so, we study some
the set π ∩ supp(P) is non-empty, therefore, we may choose a ∈ supp(P) so that π = a + V 3 . This, along with Equation (3) implies that the first hypothesis of Lemma 16 is satisfied. Lemma 16 implies that
We make use of the following bounds on the ℓ 1 and ℓ 2 norms of v. The proofs of these are by Fourier analysis and are deferred to Appendices A.4 and A.5.
.
▷ Claim 23.
We now bound ∥ṽ∥ 2 = ∥v∥2 ∥v∥1 by plugging in appropriate bounds on δ and dividing Equation (6) by Equation (5). Our choice of δ = α 20 /n 1/40 , and our assumption that α/10 ≤ (P|π)(E) (which in turn is at most min i∈ [3] (µ πi (E i ))) implies that δ is much smaller than any µ πi (E i ). In particular, we highlight that
Thus the dominant term on the right-hand side of Equation ( 5) is
, and the dominant term on the right-hand side of Equation ( 6) is
). More precisely, we have
This implies that
In comparison, Equation (4) gave that
Thus we can rewrite Equation (9) as
This, together with the fact that by construction ∥ṽ∥ 1 = 1, is sufficient to deduce that ṽ is close to the "uniform distribution" vector
More formally, we have: ▶ Fact 24. Suppose that ṽ ∈ R m is an m-dimensional vector such that ∥ṽ∥ 1 = 1, and
where ũ denotes the vector (foot_0 m , . . . , 1 m ).
The proof of Fact 24 is deferred to Appendix A.6 Applying Fact 24 to Equation (10) shows that d TV (ṽ, ũ) = o(1). In other words, a uniformly random edge of a uniformly random bow tie is distributed close to uniformly on E(G).
We now show that a typical bow tie differs in a considerable fraction of coordinates. π ∼ Π(P|E) is good with probability at least 1 -δ • α -1 -1/10 ≥ 0.9 -o(1) ≥ 0.8, we have Let W i denote the event of winning the GHZ game in the j i -th coordinate under the strategy f and let
We show how to construct a sequence of coordinates so that every term in the above product is at most 1 -c/2. This would imply that val(G) ≤ (1 -c/2) Θ(log(1/ρ(n)) = ρ(n) Ω(1) . Fix any i ∈ {0, . . . , m -1} and assume that we have found j 1 , . . . , j i . Let X ∼ P and X ≤i denote X restricted to the coordinates {j 1 , . . . , j i }. Let Y ≤i denote the outputs of the players restricted to the coordinates {j 1 , . . . , j i }. Let Z ≤i = (X ≤i , Y ≤i ). Since W ≤i is a function of Z ≤i , we have
Let F = F (z ≤i ) denote the event that
where N = 32 i ≥ supp(Z ≤i ). We argue that F occurs with probability at least 1 -c/2. This is because we are sampling z ≤i with probability P[Z ≤i = z ≤i |W ≤i ], hence the measure of z ≤i for which
Fix any z ≤i such that F holds. Our choice of m implies that 1 N • c 2 ≥ ρ(n). Note that we can express the distribution P|Z ≤i = z ≤i as P|E where
By linearity of expectation, we can fix a j ∈
Note that j / ∈ {j 1 , . . . , j i } since we already win the game on these coordinates. This, along with Equation (11) completes the proof. ◀
Proof of Claim 20. Let i ∈ I. Since the bow tie b differs in the i-th coordinate, we have
We may thus assume without loss of generality that x 0 (i) = y 0 (i) = 0. Define embeddings ϕ 1 : F 2 → {x 0 , x 1 }, ϕ 2 : F 2 → {y 0 , y 1 } and ϕ 3 : F 2 → {z 0 , z 1 } at a ∈ F 2 by ϕ 1 (a) = x a , ϕ 2 (a) = y a and ϕ 3 (a) = z a . It follows for all a ∈ {0, 1} and j ∈ [3], we have (ϕ j (a))(i) = a. In particular, for ϕ = ϕ 1 × ϕ 2 × ϕ 3 , the distribution ϕ(Q) is exactly the distribution b. Given any strategies f1 , f2 , f3 : F n 2 → F n 2 for the players for the n-fold GHZ game restricted to the query distribution b, the functions ϕ 1 , ϕ 2 , ϕ 3 induce a strategy for the GHZ game as follows. Define f j : F 2 → F 2 by f j (a) = ( fj (ϕ j (a)))(i). The success probability of the strategy f 1 × f 2 × f 3 on the distribution Q is exactly the success probability in the i-th coordinate of the strategy f1 × f2 × f2 on the distribution b. It follows that val (i) (G| b) ≤ 3/4. ◁
Proof of Claim 21. Fix any e ∈ E(G), e = (x 0 , y 0 ). This implies that
where
This implies that for all e = (x 0 , y 0 ) ∈ E(G) and z 1 ∈ E 3 ∩ π 3 , we have 1 z1 (e) = 1 if and only if b = {x 0 , x 1 } × {y 0 , y 1 } is a bow tie. Observe that as we vary z 1 ∈ E 3 ∩ π 3 , we obtain all possible bow ties that contain the edge e, i.e. the bow ties b for which b(e) ̸ = 0. This implies that v
For ease of notation, we define weight functions as follows.
▶ Definition 26 (Weight functions).
The first hypothesis of Lemma 16 is satisfied due to Equation (3). Lemma 16 implies that
All the hypothesis are satisfied due to Equation (3). Lemma 16, along with conditioning z ∼ π 3 on z ∈ E 3 implies that
62:18 Parallel Repetition for the GHZ Game: A Simpler Proof
Substituting this in the previous inequalities and taking an expectation over z ∼ E 3 ∩ π 3 ,
Proof of Claim 23. Define wt π (•) as in the proof of Claim 22. Let z, z ′ ∈ E 3 ∩ π 3 . Observe that ⟨1 z ,
We apply Lemma 16 with parameters
The first hypothesis is satisfied due to Equation (3). Lemma 16 implies that
Taking an expectation over z ′ ∼ E 3 ∩ π 3 and applying Cauchy-Schwartz yields that
Observe that µ π1 (L z ∩ L z ′ ) = E x∼π1 [L z (x)E 2 (x + z ′ )] for all z ′ ∈ E 3 ∩ π 3 . We now apply Lemma 16 with parameters A = L z ∩ π 1 , B = E 2 ∩ π 2 , C = E 3 ∩ π 3 . All the hypotheses are satisfied due to Equation (3). Lemma 16, along with the aforementioned observation implies that
An analogous inequality holds for |R z ∩ R z ′ |. Substituting this in the previous inequality and using the fact that √ a + b ≤ √ a + √ b, we have
We now take an expectation over z ∼ E 3 ∩ π 3 and use Equation (12) to conclude that ∥ṽ -ũ∥ 2 2 = ⟨ṽ -ũ, ṽ -ũ⟩ = ∥ṽ∥ 2 2 + ∥ũ∥ 2 2 -2⟨ũ, ṽ⟩
Finally, we bound the ℓ 1 distance in terms of the ℓ 2 distance: ∥ṽ -ũ∥ 1 ≤ ∥ṽ -ũ∥ 2 • √ m ≤ 3β. ◀
Proof of Claim 25. It suffices to show that a random b ∼ B differs in less than n/3 coordinates with probability at most 2 -Ω(n) = o(1).
The Chernoff bound implies that Pr x0,x1∼F n 2 [hwt(x 0 + x 1 ) < n/3] ≤ 2 -Ω(n) . We condition on x 0 , x 1 ∈ π 1 to conclude that Pr x0,x1∼π1 [hwt(x 0 + x 1 ) < n/3] ≤ 2 -Ω(n) • 2 2n |V| 2 . Let b = {x 0 , x 1 } × {y 0 , y 1 } be a bow tie. By definition, we have y 1 = x 0 + x 1 + y 0 . In particular, the bow tie b is uniquely identified by x 0 , x 1 , y 0 . This implies that the probability that a random b ∼ B differs in less than n/3 coordinates is precisely [hwt(x 0 + x 1 ) < n/3]
Recall that v = E z∼E3∩π3 [1 z ] = 1 µπ 3 (E3)•|V| z∈E3∩π3 1 z , where for each e, z∈E3∩π3 1 z (e) equals the number of bow ties containing the edge e. Since each bow tie contains 4 edges, we have that ∥v∥ 1 = 4 µπ 3 (E3)•|V| • |B|. Then, equation (7) implies that
This implies that |V| 3 |B| ≤ 8/α 6 . Recall that α ≥ n -O(1) and the co-dimension of V is o(n). This implies that 2 2n |V| 2 = 2 o(n) . This along with the above calculation implies that the probability that a uniformly random b ∼ B differs in less than n/3 coordinates is at most
• 2 o(n) = 2 -Ω(n) . This completes the proof. ◁
Noga Alon and Bo'az Klartag. Economical toric spines via Cheeger's inequality. J. Topol. Anal., 1(2):101-111,
2 Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM J. Comput., 42(3):1327-1363, 2013. (also in STOC 2010).
Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. (also in STOC 1995).
Ran Raz. Parallel repetition of two prover games. In CCC, pages 3-6. 2010.
Ran Raz. A counterexample to strong parallel repetition. SIAM J. Comput., 40(3):771-777, 2011.
Oleg Verbitsky. Towards the parallel repetition conjecture. In CCC, pages 304-307. IEEE Computer Society, 1994.