# Document Layout Analysis on BaDLAD Dataset: A Comprehensive MViTv2 Based
Approach

Ashrafur Rahman  Department of Computer Science
Bangladesh University of Engineering and Technology
Dhaka, Bangladesh
Email<EMAIL_ADDRESS>Asif Azad  Department of Computer Science
Bangladesh University of Engineering and Technology
Dhaka, Bangladesh
Email<EMAIL_ADDRESS>
###### Abstract

In the rapidly evolving digital era, the analysis of document layouts plays a
pivotal role in automated information extraction and interpretation. In our
work, we have trained MViTv2 transformer model architecture with cascaded mask
R-CNN on BaDLAD dataset to extract text box, paragraphs, images and tables
from a document. After training on 20365 document images for 36 epochs in a 3
phase cycle, we achieved a training loss of 0.2125 and a mask loss of 0.19.
Our work extends beyond training, delving into the exploration of potential
enhancement avenues. We investigate the impact of rotation and flip
augmentation, the effectiveness of slicing input images pre-inference, the
implications of varying the resolution of the transformer backbone, and the
potential of employing a dual-pass inference to uncover missed text-boxes.
Through these explorations, we observe a spectrum of outcomes, where some
modifications result in tangible performance improvements, while others offer
unique insights for future endeavors.

###### Index Terms:

Keywords: Document Layout Analysis, ViT, MViTv2, Bengali documents, Data
augmentation, Transformer architecture.

##  I Introduction

In today’s digital age, the exponential growth of textual information has
underscored the critical importance of document processing and understanding.
Document Layout Analysis (DLA), a fundamental task in the field of computer
vision, seeks to unravel the complex structure of documents, enabling
automated information extraction and interpretation. At its core, Document
Layout Analysis involves decomposing a document into its constituent elements,
such as text blocks, paragraphs, images and tables.

However, despite the remarkable strides made in document analysis across
various languages, the Bengali language has remained relatively unexplored in
this realm. The scarcity of labeled data and dedicated resources has hindered
significant advancements in Document Layout Analysis specifically tailored for
Bengali documents. In this respect, BaDLAD (Bengali Document Layout Analysis
Dataset) is a pioneering effort that has the potential to bridge this very gap
and drive the evolution of Bengali document analysis. [1] As we navigate this
landscape, we cast our gaze upon various model architectures that have shaped
the field of Document Layout Analysis.

Traditionally, the realm of computer vision has seen the application of
Convolutional Neural Networks (CNNs) in document layout analysis. These
networks excel at feature extraction from image data, enabling the
identification of key structural elements within documents. This approach has
yielded valuable insights and paved the way for subsequent advancements.

Region-based Convolutional Neural Networks (R-CNNs) extended the capabilities
of CNNs by introducing the concept of region proposals. This enabled more
precise localization of elements, a crucial aspect in Document Layout
Analysis. R-CNNs offered improved accuracy by focusing on the regions of
interest, thereby enhancing the understanding of document structure.

While these approaches demonstrated commendable performance, recent years have
witnessed a paradigm shift in the field, with the ascent of the transformer
architecture. Originally designed for natural language processing tasks,
transformers have proven their versatility by redefining various domains,
including Image Segmentation and Document Layout Analysis. The transformer
architecture’s inherent ability to capture contextual information and long-
range dependencies has revolutionized image segmentation. This architectural
evolution has spurred the development of models such as the MViT transformer,
which has emerged as a state-of-the-art solution in the realm of instance
segmentation as well as a potential candidate for Document Layout Analysis
tasks.

In the context of BaDLAD, a multi-domain Bengali Document Layout Analysis
Dataset, the MViT architecture holds exceptional promise. BaDLAD’s diverse
collection of documents, spanning multiple domains and layouts, aligns
seamlessly with MViT’s capacity to capture intricate structural nuances. This
marriage of data and architecture positions the MViT transformer as a natural
fit for the comprehensive analysis and interpretation of Bengali documents.

##  II Methodology

###  II-A Model Selection

Our pursuit of a robust and adept architecture for DLA led us to select the
MViTv2-B variant, which has exhibited outstanding performance on the highly
regarded COCO dataset. This particular variant, pretrained on IN1k and coupled
with the Cascade Mask R-CNN framework, has yielded compelling results.
Notably, it achieves a remarkable mask Average Precision (AP) score of 47.4
when evaluated on COCO, following a rigorous training regimen spanning 36
epochs.

The MViTv2-B variant outperforms the Swin-B model by a significant margin,
boasting a marked increase of +2.5 and +2.3 in $AP^{box}$ and $AP^{mask}$,
respectively. [2] This remarkable performance enhancement is achieved
alongside lower computational demands and a more compact model size,
signifying an optimal balance between accuracy and resource efficiency.
Hence,we have chosen the MViTv2-B model architecture as the cornerstone of our
Document Layout Analysis framework.

###  II-B Preprocessing

Our preprocessing workflow encompassed several crucial steps to ensure the
quality and consistency of input data for our Document Layout Analysis
framework. Initially, we implemented color normalization using configuration
parameters by aligning pixel mean and standard deviation. To establish
uniformity in image dimensions, we conducted image resizing and padding to a
1024$\times$1024 resolution. However, we refrained from binary colorization to
preserve the diverse color palettes essential for accurate image element
detection.

###  II-C Augmentation

To increase robustness of training we apply several augmentations on the image
inputs. We use random brightness, contrast, saturation and rotation on the
train set. These variations simulated real-world scenarios and variations in
the dataset. Collectively, these preprocessing steps optimized input data
quality, contributing to the reliability and versatility of our Document
Layout Analysis across a broad spectrum of document layouts and content.

###  II-D Training

Our training methodology was designed meticulously, employing a multi-cycle
approach to fully harness the potential of the MViTv2-B model for Document
Layout Analysis (DLA). Leveraging the Detectron2 framework, we meticulously
fine-tuned critical hyperparameters and processes to attain peak performance.
[3]

Our training was strategically organized into three consecutive cycles, each
spanning 12 epochs for a total of 36 epochs. The model’s parameters were
efficiently transferred between training cycles, with the final parameters of
each 12-epoch run serving as the starting point for the subsequent run. This
approach enabled us to explore different training and model parameters and
compare them between training phases.

Optimization was achieved through the AdamW optimizer, with a initial learning
rate of $8*10^{-5}$. The learning rate multiplier scheduler was meticulously
tailored to guide the model’s convergence over different iteration ranges.
During the initial 50 iterations a warmup phase was employed with a warmup
factor of $10^{-3}$, starting with a learning rate of $8*10^{-8}$ and
gradually upto $8*10^{-5}$ after the warmup phase. We started with a slow
learning rate with the intention to avoid overshooting and promote model
stability. Moreover, the learning rate was further decreased by $0.1$ times
and $0.01$ times at about $88\%$ and $97\%$ of the total iterations
respectively to make small adjustments in the final iterations and aid the
model’s convergence.

We structured data loading and processing using a batch size of 16 for
training. During training, crucial metrics were logged every 20 iterations,
and model checkpoints were saved every 2000 iterations to facilitate potential
model recovery.

##  III Results

After a total training of 36 epochs in 3 phases, our model scored a DICE score
of 0.90095 on the public test set and a total loss of 0.2125 and a mask loss
of 0.19. The loss metrics gradually decreased throughout the training.

From figure 1 we can see that the mask loss reached about 0.2 after the first
12 epochs. However, the training loss slowly continued to improve over the
training period.

$1$$5$$10$$15$$20$$25$$30$$35$$0.2$$0.3$$0.4$$0.5$epochloss_mask Figure 1:
Loss mask vs Epoch
$1$$5$$10$$15$$20$$25$$30$$35$$0.2$$0.3$$0.4$$0.5$epochtotal_loss Figure 2:
Total loss vs Epoch

Table 3 summarizes the scores obtained after each phase of training.

Epoch | Training loss | Dice Score
---|---|---
12 | 0.2705 | 0.89904
24 | 0.2322 | 0.90244
36 | 0.2078 | 0.90348
Figure 3: Test Set Scores

##  IV Kaggle Competition Results

In the Kaggle competition ”DL Sprint 2.0,” which focused on Document Layout
Analysis using the BaDLAD Dataset, a total of 94 teams participated. Our team,
named ”Black Quad,” demonstrated exceptional performance and secured the
championship.

Our approach, titled ”Document Layout Analysis on BaDLAD Dataset: A
Comprehensive MViTv2 Based Approach,” yielded remarkable results. We achieved
the highest Dice score in the competition of 0.90396, showcasing the
effectiveness of our method in accurately segmenting document layouts.

Furthermore, our team achieved a mean Average Precision (mAP) score of 56.381,
which stands out as the highest among all participating teams. This
accomplishment underscores the robustness and generalization of our approach
across various document layouts and scenarios.

##  V Discussion

###  V-A Effect of Rotation and Flip

We observed that both the training set and test set contains rotated images.
Initially, in order to accommodate for this case, we introduced random
discreet rotations from the set
$\\{0^{\circ},90^{\circ},180^{\circ},270^{\circ}\\}$. However we observed that
this augmentation as well as horizontal or vertical flips lead to poorer
results. Since rotated images are rare in the test set, we chose to train our
model to primarily focus on upright images. A more comprehensive approach
would be to train a separate model to recognize rotations and preprocess them
during inference.

However, We noticed a much more prevalent pattern of rotations in the dataset.
Since much of the documents are scanned documents, they are slightly tilted at
a small angle. To incorporate this variation we augmented our images using a
random rotation in the range $[-5^{\circ},5^{\circ}]$.

###  V-B Sliced Inference

During our evaluation of the inference of our model both on the train and
public test set we observed that many small features, primarily text-boxes and
paragraphs weren’t recognized with adequate confidence by our model. This
observation initially led us to believe that slicing the input images into
overlapping windows and running inference on each of the slices would improve
our results furthermore.

However, despite a two to four fold increase in inference time, we didn’t
observe any noticeable improvement of the model’s capability of recognizing
smaller instances. Slicing also introduced the problem of recognising larger
features such as tables or images in multiple segments.

###  V-C Resolution of Transformer Backbone

The multiscale vision transformer backbone of the MViTv2 model can work in
different resolutions. [2] The pretrained models are trained on image
resolution of $224\times 224$. We first trained 12 epochs on the pretrained
MViTV2-B model with $224\times 224$ resolution. We then trained the model at
$384\times 384$ resolution, initializing weights from the fine tuned
$224\times 224$ model. We repeated this process for resolution $512\times
512$, using the weights from the previous step. We observed that with same
similar training the $224\times 224$ resolution model performs better.

###  V-D Two pass Inference to Detect Missed Text-boxes

In an attempt to recognize the smaller text-boxes and paragraphs missed during
inference, we designed a two pass inference approach. We noted that
overcrowding of instances played a big factor in the model’s failure to detect
some features. Therefore, to identify those features, we ran inference twice.
The recognised text-boxes and paragraphs, from the first inference, which
didn’t overlap with any images were erased (i.e. replaced with the background
colour). The resulting image was then fed to the model for a second inference.
The text-boxes recognized in this pass were added to the model’s prediction
result. However, this approach was found to perform worse than the single pass
inference on the public test set.

###  V-E Effectiveness of Transformer Model

While most other solutions explored traditional CNN based models including
R50-FPN and yolov8, we explored several transformer based architectures
including maskDINO and MViTv2. We found both models show improved performance
after similar training iterations. The MViTv2-B model gave us a balance of
performance and resource efficiency as noted earlier, increasing accuracy
compared to traditional approaches while not severely increasing inference
time or memory consumption.

##  VI Conclusion and Future Work

We present an effective scheme to fine tune the transfermer based MViTv2 model
for Bengali Document Layout Analysis. Previously traditional CNN based models
were applied on the dataset.[1] Our work demonstrates the viability of the
transformer based Vision Transformer models such as MViTv2 for Bengali
Document Layout Analysis.

As noted before, handling rotation explicitly by training a separate
lightweight model to recognize rotations will increase the model’s capacity to
handle arbitrarily rotated images. Another limitation of the model is it’s
failure to detect small objects, mainly text-boxes. Copy-paste augmentation
techniques have proven to significantly improve a model’s capacity in these
regards[4, 5]. We couldn’t train our model with copy-paste augmentation due to
shortage of time but we believe incorporating this augmentation will further
strengthen our model and increase it’s robustness.

## References

  * [1] M. I. H. Shihab, M. R. Hasan, M. R. Emon, S. M. Hossen, M. N. Ansary, I. Ahmed, F. R. Rakib, S. E. Dhruvo, S. S. Dip, A. H. Pavel _et al._ , “Badlad: A large multi-domain bengali document layout analysis dataset,” _arXiv preprint arXiv:2303.05325_ , 2023.
  * [2] Y. Li, C.-Y. Wu, H. Fan, K. Mangalam, B. Xiong, J. Malik, and C. Feichtenhofer, “Mvitv2: Improved multiscale vision transformers for classification and detection,” in _CVPR_ , 2022.
  * [3] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick, “Detectron2,” https://github.com/facebookresearch/detectron2, 2019.
  * [4] G. Ghiasi, Y. Cui, A. Srinivas, R. Qian, T.-Y. Lin, E. D. Cubuk, Q. V. Le, and B. Zoph, “Simple copy-paste is a strong data augmentation method for instance segmentation,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 2918–2928.
  * [5] M. Kisantal, Z. Wojna, J. Murawski, J. Naruniec, and K. Cho, “Augmentation for small object detection,” _arXiv preprint arXiv:1902.07296_ , 2019.


# Parallel Repetition of $k$-Player Projection Games

Amey Bhangale Department of Computer Science and Engineering, University of
California, Riverside. Supported by the Hellman Fellowship award. Mark
Braverman Department of Computer Science at Princeton University. Supported by
the National Science Foundation under the Alan T. Waterman Award, Grant No.
1933331 Subhash Khot Department of Computer Science, Courant Institute of
Mathematical Sciences, New York University. Supported by the NSF Award
CCF-2130816 and the Simons Investigator Award. Yang P. Liu School of
Mathematics, Institute for Advanced Study, Princeton, NJ. Partially supported
by NSF DMS-1926686. Dor Minzer Department of Mathematics, Massachusetts
Institute of Technology. Supported by NSF CCF award 2227876 and NSF CAREER
award 2239160.

###### Abstract

We study parallel repetition of $k$-player games where the constraints satisfy
the projection property. We prove exponential decay in the value of a parallel
repetition of projection games with value less than $1$.

##  1 Introduction

We study $k$-player one-round games and the effect on the value of the game
when we repeat the game in parallel.

In a $k$-player game $G$, a verifier chooses $k$ questions
$(x^{1},x^{2},\ldots,x^{k})$ from a distribution $\mu$ on the set of questions
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$ and
sends $x^{i}$ to player $i$. Player $i$ responds to the verifier’s question by
sending an answer $a^{i}\in\mathcal{A}_{i}$ without communicating with the
other players. The verifier accepts the answers based on a fixed predicate
$V((x^{1},x^{2},\ldots,x^{k}),(a^{1},a^{2},\ldots,a^{k}))$. The value of the
game, denoted by $\mathbf{val}(G)$, is the maximum, over the players’
strategies, accepting probability of the verifier.

The $n$-fold parallel repetition of $G$, denoted by $G^{\otimes n}$, is
defined as follows. The verifier sends questions
$\vec{x}^{i}=(x^{i}_{1},x^{i}_{2},\ldots,x^{i}_{n})$ to the $k$ players where
for each $j\in[n]$, $(x^{1}_{j},x^{2}_{j},\ldots,x^{k}_{j})$ is sampled from
the original distribution $\mu$ independently. The $i^{th}$ player responds
with answers $\vec{a}^{i}\in\mathcal{A}_{i}^{n}$. The verifier accepts the
answers iff
$V((x^{1}_{j},x^{2}_{j},\ldots,x^{k}_{j}),(a^{1}_{j},a^{2}_{j},\ldots,a^{k}_{j}))=1$
for each $j\in[n]$.

If $\mathbf{val}(G)=1$, then it is easy to observe that
$\mathbf{val}(G^{\otimes n})$ is also $1$. Also, $\mathbf{val}(G^{\otimes
n})\geqslant\mathbf{val}(G)^{n}$ as the players can achieve value
$\mathbf{val}(G)^{n}$ in the game $G^{\otimes n}$ by simply repeating an
optimal strategy for the game $G$ independently in all the $n$ coordinates.
The question of interest is how does the quantity $\mathbf{val}(G^{\otimes
n})$ decay with $n$ if the value of the game $G$ is less than $1$?

Verbitsky [Ver96] showed that for any $k$-player game $G$, if
$\mathbf{val}(G)<1$, then $\mathbf{val}(G^{\otimes
n})\leqslant\frac{1}{\alpha(n)}$ where $\alpha(n)$ is an inverse Ackermann
function. This result uses the Density Hales-Jewett Theorem [FK89, Pol12] as a
black box. For $2$-player games, Raz [Raz98] showed that if
$\mathbf{val}(G)<1$, then $\mathbf{val}(G^{\otimes n})\leqslant
2^{-\Omega_{G}(n)}$, where we use $\Omega_{G}(\cdot)$ to clarify that the
constant depends on the game $G$. There have been many improvements that
improve the constants in the bounds, and even get better bounds based on the
value $\mathbf{val}(G)$ of the initial game [Hol09, Rao11, DS14, BG14]. These
results on parallel repetition of $2$-player games have found many
applications in probabilistically checkable proofs and hardness of
approximation [BGS98, Fei98, Hås01].

Mittal and Raz [MR21] showed that a strong parallel repetition theorem (i.e.,
the value of $G^{\otimes n}$ decays exponentially in $n$ in a certain strong
sense) for a particular class of more than $2$-player games implies super-
linear lower bounds for Turing machines in the non-uniform model. For any
$k\geqslant 2$, Dinur, Harsha, Venkat, and Yuen [DHVY17] showed that for a
large class of $k$-player games, called the connected games, the exponential
decay indeed holds. The class of connected games is defined as follows: define
the graph $H_{G}$, whose vertices are the ordered $k$-tuples of questions to
the $k$-players, and there is an edge between questions $q$ and $q^{\prime}$
if they differ in the question to exactly one of the $k$ players, and are the
same for the remaining $k-1$ players. The game is said to be connected if the
graph $H_{G}$ is connected.

A special $3$-player (non-connected) game, called the GHZ Game [DHVY17], has
received much attention. The GHZ game, first introduced by Greenberger, Horne,
and Zeilinger [GHZ89], is a central game in the study of quantum entanglement.
Holmgren and Raz [HR20] gave the first polynomial decay in the parallel
repetition of the GHZ game. Girish, Holmgren, Mittal, Raz, and Zhan [GHM+21]
later gave a simpler proof of the polynomial decay. Very recently, Braverman,
Khot, and Minzer [BKM22], using a much simpler proof, improved these previous
results and showed an exponential decay in the GHZ game.

Girish, Holmgren, Mittal, Raz, and Zhan [GHM+22] considered the problem of
parallel repetition for $3$-player games with binary questions and answers and
showed polynomial decay for these games. This was later improved by a subset
of the authors [GMRZ22] to all $3$-player games over binary questions and
arbitrary answer lengths. They also study [GHM+22] player-wise connected games
$G$ that are defined as follows. For each player $i$, define the graph
$H_{i}(G)$, whose vertices are the possible questions for player $i$, and two
questions $x$ and $x^{\prime}$ are connected by an edge if there exists a
vector $y$ of questions for all other players, such that both $(x,y)$ and
$(x^{\prime},y)$ are asked by the verifier with non-zero probability. The game
$G$ is player-wise connected if, for every $i$, the graph $H_{i}(G)$ is
connected. Girish et al.  [GHM+22] showed polynomial decay in the value of
$n$-fold parallel repetition of all player-wise connected games. Observe that
the notion of player-wise connectedness is more general than the notion of
connected games defined above.

In this paper, we will study a special type of $k$-player games, that we refer
to as projection games. The formal definition is as follows.

######  Definition 1.1.

For any $k\geqslant 2$, a $k$-player game $G$ is called a projection game if
for every $k$-tuple of question $q=(x^{1},x^{2},\ldots,x^{k})$, there is
$D_{q}\geqslant 1$ and projections
$\sigma^{i}_{q}:\mathcal{A}_{i}\rightarrow[D_{q}]$ for $i\in[k]$, such that
$V((x^{1},x^{2},\ldots,x^{k}),(a^{1},a^{2},\ldots,a^{k}))$ is true iff
$\sigma^{i}_{q}(a^{i})=\sigma^{i^{\prime}}_{q}(a^{i^{\prime}})$ for any $i\neq
i^{\prime}$.

For every question $q=(x^{1},x^{2},\ldots,x^{k})$, consider a $k$-partite
hypergraph $\mathcal{H}_{q}$ on the vertex set
$(\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{k})$ where
$(a^{1},a^{2},\ldots,a^{k})$ is an hyperedge if and only if
$V((x^{1},x^{2},\ldots,x^{k}),(a^{1},a^{2},\ldots,a^{k}))$ is true. Then, the
projection property means that for every $k$-tuple of questions $q$ in the
support of $\mu$, each connected component in $\mathcal{H}_{q}$ is a complete
$k$-partite hypergraph. Note that this definition of projection games is
slightly more general than the usual notion of projection $2$-player games
[Raz98, Rao11] where one of the maps $\sigma^{i}_{q}$ (either $\sigma^{1}_{q}$
or $\sigma^{2}_{q}$) is an injective map.

Our main theorem shows that if the value of a projection game $G$ is less than
$1$, then the value of $n$-fold parallel repetition of $G$ decays
exponentially in $n$.

######  Theorem 1.2.

For any $k\geqslant 2$, a projection $k$-player game $G$ and $\varepsilon>0$,
if $\mathbf{val}(G)=1-\varepsilon$, then $\mathbf{val}(G^{\otimes
n})\leqslant\exp({-\Omega_{\varepsilon,G}(n)})$.

Projection games are a natural subclass of general games. They played a key
role in the development [ALM+98, AS98, FGL+96] of Probabilistically Checkable
Proofs (PCPs). In fact, parallel repetition from $2$-player projection games
had been useful in proving many [GHS02, Kho02a, Kho02b, DGKR05, DRS02] tight
hardness of approximation results, starting with the work of Arora, Babai,
Stern, and Sweedyk [ABSS97], Bellare, Goldreich, and Sudan [BGS98], and Håstad
[Hås01].

Feige [Fei98] used a $k$-player projection game, and parallel repetition of
the game, to show almost tight hardness of approximating the Set-Cover
problem. The decay in the value of a parallel-repeated game, in that case,
follows easily from the parallel-repetition theorem for the $2$-player game,
as the subgame restricted to any two players has a value less than $1$.

There are $k$-player projection games where the decay in the value of a
parallel-repeated game does not trivially follow from the parallel-repetition
theorem for the $2$-player game. To give a concrete example, consider a
simultaneous Max-3-SAT instance problem defined in [BKS15]: the instance
consists of $n$ variables $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ and $k$
instances, $\phi_{1},\phi_{2},\ldots,\phi_{k}$, of Max-3-SAT defined over the
same set of variables $X$. The verifier chooses a variable $x\in X$ at random
and selects clauses $C_{i}\in\phi_{i}$ independently such that $x\in C_{i}$
for all $i\in[k]$. The verifier sends clause $C_{i}$ to player $i$ and expects
a satisfying assignment from $\\{0,1\\}^{3}$ to $C_{i}$ from player $i$. The
verifier checks if the assignments returned by the players agree on $x$.
Consider the scenario when it is possible to satisfy any $(k-1)$ out of $k$
instances of Max-3-SAT simultaneously, but there is no assignment to $X$ that
will satisfy all the $k$ instances. In this case, the value of the game is
less than $1$. For any $k^{\prime}$-player subgame, where $k^{\prime}<k$, the
value of the subgame is $1$. Therefore, we cannot use the parallel repetition
of $2$-player games to conclude that the value of $n$-fold parallel repetition
of projection games decays with $n$.

###  1.1 Proof outline

As mentioned in the introduction, Dinur, Harsha, Venkat, and Yuen [DHVY17]
showed that for any connected $k$-player games $H$ with $\mathbf{val}(H)<1$,
the exponential decay holds for the value of $H^{\otimes n}$. We start with a
$k$-player game $G$ which is not connected to begin with. At a high level, we
transform the game $G$ to another game $H$ where $H$ is connected. While doing
such a transformation, we want to make sure we have the following two
properties.

  1. 1.

If $\mathbf{val}(G)<1$, then $\mathbf{val}(H)<1$.

  2. 2.

There is a way to relate $\mathbf{val}(G^{\otimes n})$ with
$\mathbf{val}(H^{\otimes n})$, possibly with a small loss in the constants in
the exponent.

As $H$ is connected, we have $\mathbf{val}(H^{\otimes
n})=\exp(-\Omega_{H}(n))$ and this will complete the proof.

There is a trivial transformation that makes any game connected – add all
possible $k$-tuple of questions, play the game $G$ on the original questions,
and accept all the newly added questions by default. It is easy to see that if
$\mathbf{val}(G)<1$, then the value of the transformed game is less than $1$.
However, in this case, there does not seem to be an easy way to relate
$\mathbf{val}(G^{\otimes n})$ to the value of $n$-fold parallel repetition of
the transformed game.

In order to overcome the issue, we make the game $G$ connected gradually. More
concretely, we start with a game $G_{0}=G$ and iteratively, we convert the
game $G_{\ell}$ to $G_{\ell+1}$ for $\ell=0,1,\ldots$ with the following three
properties.

  1. 1.

For every $\ell\geqslant 0$, the game $G_{\ell}$ is a $k$-player game with the
questions from the set
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$.

  2. 2.

The game $G_{\ell+1}$ is richer than the game $G_{\ell}$. In our case, we
would be interested in increasing the support of distribution on questions,
i.e., $\mathsf{supp}(\mu(G_{\ell+1}))\supsetneq\mathsf{supp}(\mu(G_{\ell}))$
(unless, of course, $\mathsf{supp}(\mu(G_{\ell})$ is full).

  3. 3.

We can relate the value of the game $G_{\ell}^{\otimes n}$ to the value of the
game $G^{\otimes n}_{\ell+1}$ up to a fixed polynomial factor. Furthermore,
$\mathbf{val}(G_{\ell+1})<1$ if $\mathbf{val}(G_{\ell})<1$.

Let us see that this is enough to prove our main theorem. Using properties $1$
and $2$, for some $t\geqslant 1$, which only depends on the size of the game
$G$, we can conclude that the game $G_{t}$ has full support and hence is
connected. Using property $3$, we have $\mathbf{val}(G^{\otimes
n})\approx\mathbf{val}(G_{t}^{\otimes n})^{C_{t}}$, where $C_{t}>0$ is a
constant that only depends on $t$, and furthermore $\mathbf{val}(G_{t})<1$ if
$\mathbf{val}(G)<1$ to begin with. Finally, using the result by Dinur, Harsha,
Venkat, and Yuen [DHVY17] on connected games, we have,
$\mathbf{val}(G_{t}^{\otimes n})=\exp(-\Omega_{\varepsilon,G_{t}}(n))$, and
hence $\mathbf{val}(G^{\otimes n})=\exp(-\Omega_{\varepsilon,t,G}(n))$ if
$\mathbf{val}(G)<1$.

##### The transformation $G_{\ell}$ to $G_{\ell+1}$.

We illustrate the idea of such a transformation in a $3$-player game
$G_{\ell}$. We start with the game $G_{\ell}$ and let $\mu(G_{\ell})$ be the
distributions on the questions in $G_{\ell}$. For every pair of question-
triples $q=(x,y,z)$ and $q^{\prime}=(x^{\prime},y^{\prime},z^{\prime})$ from
$\mathsf{supp}(\mu(G_{\ell}))$ such that $x=x^{\prime}$, we add a question
triple $\Pi^{3}((q,q^{\prime})):=(x,y,z^{\prime})$ to the game $G_{\ell+1}$.
Note that in this case, we took two question-triples $(q,q^{\prime})$ that
share player 1’s question and generate a question-triple in the new game with
the first two players’ questions from $q$ and player $3$’s question from
$q^{\prime}$. We now state the set of accepting assignments for
$\Pi^{3}((q,q^{\prime}))$ as follows. If $q\neq q^{\prime}$, then accept the
question $\Pi^{3}((q,q^{\prime}))$ by default, otherwise accept
$\Pi^{3}((q,q^{\prime}))$ according to the verifier from the original game
$G_{\ell}$ on the question $q(=q^{\prime})$.111Note that the way the game
$G_{\ell+1}$ is defined, the set of accepting answers for the same question-
triple changes based on the underlying pair of questions $(q,q^{\prime})$, but
we ignore this issue in this proof outline. We call such a transformation
$\mathcal{T}^{1}_{3}$ – the superscript stands for the common player’s
question from $(q,q^{\prime})$ and the subscript $3$ stands for taking player
3’s question from $q^{\prime}$ and rest of the questions from $q$ in
generating the question-triple in the new game. Succinctly, we write
$G_{\ell+1}$ as the game $\mathcal{T}^{1}_{3}(G_{\ell})$. Likewise, we can
define transformations $\mathcal{T}^{i}_{p}$ for any $1\leqslant i,p\leqslant
3$.

We show the following key properties of these transformations.

  1. 1.

If $\mathbf{val}(G_{\ell})<1$, then
$\mathbf{val}(\mathcal{T}^{i}_{p}(G_{\ell}))<1$. Furthermore,
$\mathcal{T}^{i}_{p}(G_{\ell})$ remains a projection game if $G_{\ell}$ is a
projection game.

  2. 2.

For every $n\geqslant 1$, $\mathbf{val}(G_{\ell}^{\otimes
n})\leqslant\mathbf{val}(\mathcal{T}^{i}_{p}(G_{\ell})^{\otimes n})^{1/2}$, if
$G_{\ell}$ is a projection game.

The first property is trivial – in the game $\mathcal{T}^{i}_{p}(G_{\ell})$,
we are still playing the game $G_{\ell}$ as a subgame and hence its value is
less than $1$ if $\mathbf{val}(G_{\ell})<1$. For the furthermore part, we are
either accepting everything by default or using the same predicate as in the
original game and hence this transformation maintains the projection property
of the game.

For the second property, we crucially use the projection property of the game
$G_{\ell}$. We show that for any strategy
$(\alpha^{1},\alpha^{2},\alpha^{3})$, where
$\alpha^{i}:\mathcal{X}_{i}^{n}\rightarrow\mathcal{A}_{i}^{n}$, for the game
$G_{\ell}^{\otimes n}$ with value $\varepsilon$, we show that the same
strategy gives value at least $\varepsilon^{2}$ to the game
$\mathcal{T}^{i}_{p}(G_{\ell})$. We illustrate this for the game
$\mathcal{T}^{1}_{3}(G_{\ell})$. Let $\mu$ be the distribution of questions
from $G_{\ell}$ and $\mu|_{1}$ be the marginal distribution on player 1’s
questions, we have

$\displaystyle\varepsilon^{2}$
$\displaystyle\leqslant\mathop{\mathbf{E}}_{(\mathbf{x},\mathbf{y},\mathbf{z})\sim\mu^{\otimes
n}}[V((\mathbf{x},\mathbf{y},\mathbf{z}),(\alpha^{1}(\mathbf{x}),\alpha^{2}(\mathbf{y}),\alpha^{3}(\mathbf{z})))]^{2}$
$\displaystyle=\left(\mathop{\mathbf{E}}_{\mathbf{v}\in\mu^{\otimes
n}|_{1}}\left[\mathop{\mathbf{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y},\mathbf{z})\sim\mu^{\otimes
n},\\\
\mathbf{x}=\mathbf{v}\end{subarray}}[V((\mathbf{x},\mathbf{y},\mathbf{z}),(\alpha^{1}(\mathbf{x}),\alpha^{2}(\mathbf{y}),\alpha^{3}(\mathbf{z})))\right]\right)^{2}$
$\displaystyle\leqslant\mathop{\mathbf{E}}_{\mathbf{v}\in\mu^{\otimes
n}|_{1}}\left[\mathop{\mathbf{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y},\mathbf{z})\sim\mu^{\otimes
n},\\\
\mathbf{x}=\mathbf{v}\end{subarray}}[V((\mathbf{x},\mathbf{y},\mathbf{z}),(\alpha^{1}(\mathbf{x}),\alpha^{2}(\mathbf{y}),\alpha^{3}(\mathbf{z})))\right]^{2}\quad\quad\quad$
(Cauchy-Schwarz) $\displaystyle=\mathop{\mathbf{E}}_{\mathbf{v}\in\mu^{\otimes
n}|_{1}}\left[\mathop{\mathbf{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y},\mathbf{z})\sim\mu^{\otimes
n},\\\
(\mathbf{x}^{\prime},\mathbf{y}^{\prime},\mathbf{z}^{\prime})\sim\mu^{\otimes
n},\\\
\mathbf{x}=\mathbf{x}^{\prime}=\mathbf{v}\end{subarray}}[V((\mathbf{x},\mathbf{y},\mathbf{z}),(\alpha^{1}(\mathbf{x}),\alpha^{2}(\mathbf{y}),\alpha^{3}(\mathbf{z})))\cdot
V((\mathbf{x}^{\prime},\mathbf{y}^{\prime},\mathbf{z}^{\prime}),(\alpha^{1}(\mathbf{x}^{\prime}),\alpha^{2}(\mathbf{y}^{\prime}),\alpha^{3}(\mathbf{z}^{\prime})))\right]$

Now, if we look at the triple $(\mathbf{x},\mathbf{y},\mathbf{z}^{\prime})$
sampled according to the above distribution, then for each $j\in[n]$, we have
that the triple $(x_{j},y_{j},z^{\prime}_{j})$ is distributed according to the
game $\mathcal{T}^{1}_{3}(G_{\ell})$ independently. In the game,
$\mathcal{T}^{1}_{3}(G_{\ell})$, for any $j\in[n]$ such that
$(x_{j},y_{j},z_{j})\neq(x^{\prime}_{j},y^{\prime}_{j},z^{\prime}_{j})$ the
new verfier is accepting by default. As for $j\in[n]$ such that
$(x_{j},y_{j},z_{j})=(x^{\prime}_{j},y^{\prime}_{j},z^{\prime}_{j})$, the new
verifier is accepting according to the original verifier on the question
$(x_{j},y_{j},z_{j})$. In this case, suppose
$(\alpha^{1}(\mathbf{x})_{j},\alpha^{2}(\mathbf{y})_{j},\alpha^{3}(\mathbf{z})_{j})$
and
$(\alpha^{1}(\mathbf{x}^{\prime})_{j},\alpha^{2}(\mathbf{y}^{\prime})_{j},\alpha^{3}(\mathbf{z}^{\prime})_{j})$
are two satisfying assignments to the same question $(x_{j},y_{j},z_{j})$
according to the original game $G_{\ell}$ with
$\alpha^{1}(\mathbf{x})_{j}=\alpha^{1}(\mathbf{x}^{\prime})_{j}$ (as
$\mathbf{x}=\mathbf{x}^{\prime}$), then because of the projection property of
the game, we have that
$(\alpha^{1}(\mathbf{x})_{j},\alpha^{2}(\mathbf{y})_{j},\alpha^{3}(\mathbf{z}^{\prime})_{j}))$
must be a satisfying assignment for $(x_{j},y_{j},z_{j})$. As in the game
$\mathcal{T}^{1}_{3}(G_{\ell})^{\otimes n}$, we are precisely checking this
for all such $j\in[n]$, we get that the same strategy
$(\alpha^{1},\alpha^{2},\alpha^{3})$ gives

$\mathbf{val}(\mathcal{T}^{1}_{3}(G_{\ell})^{\otimes
n})\geqslant\varepsilon^{2}.$

##### Putting everything together.

Using the above two properties of the transformations $\mathcal{T}^{i}_{p}$,
we conclude that if $\mathbf{val}(G)<1$, then for any $t\geq 1$ and vectors
$\vec{i},\vec{p}\in[3]^{t}$,

$\mathbf{val}(G^{\otimes
n})\leqslant\mathbf{val}(\mathcal{T}^{i_{t}}_{p_{t}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G))))^{\otimes
n})^{1/2^{t}},\mbox{ and
}\mathcal{T}^{i_{t}}_{p_{t}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G)))<1.$

Finally, we show that there exist $t\geq 1$ and vectors
$\vec{i},\vec{p}\in[3]^{t}$, where $t$ depends on the size of the game $G$,
such that the game
$\mathcal{T}^{i_{t}}_{p_{t}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G)))$
is connected (in fact, has full support). This implies that

$\mathbf{val}(G^{\otimes
n})\leqslant\mathbf{val}(\mathcal{T}^{i_{t}}_{p_{t}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G))))^{\otimes
n})^{1/2^{t}}\leqslant\exp(-\Omega_{t,G}(n)),$

where the last inequality follows from the result of a parallel repetition
theorem [DHVY17] on connected games.

##  2 Preliminaries

We start with a few notations. We use $\mu(G)$ to denote the distribution on
the questions in the game $G$. For $i\in[k]$, let $\mu|_{i}$ be the marginal
distribution on the questions to player $i$. For a $k$-tuple of questions
$q=(x^{1},x^{2},\ldots,x^{k})$, we denote the question to player $i$ by
$q|_{i}$, i.e., $q|_{1}=x^{1}$, $q|_{2}=x^{2}$, and so on. For an assignment
$\alpha:=(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$ to the game $G$, where
$\alpha^{i}:\mathcal{X}_{i}\rightarrow\mathcal{A}_{i}$, and any question
$q=(x^{1},x^{2},\ldots,x^{k})$, we use the notation $\alpha|_{q}$ to denote
the assignment-tuple
$(\alpha^{1}(x^{1}),\alpha^{2}(x^{2}),\ldots,\alpha^{k}(x^{k}))$. The size of
the game $G$ is referred to as the quantity $k\cdot
M\cdot\prod_{i=1}^{k}|\mathcal{X}_{i}||\mathcal{A}_{i}|$. Here, the
probability of every atom in $\mathsf{supp}(\mu(G))$ is a multiple of $1/M$,
where $M$ is a finite integer (this we assume for simplicity).

###  2.1 Parallel repetition of connected games

As mentioned earlier, Dinur, Harsha, Venkat, and Yuen [DHVY17] showed that for
a large class of $k$-player games, called connected games, the exponential
decay indeed holds. Here, we define the notion of connected games for
$k$-player games formally.

######  Definition 2.1 (Connected game).

A game $G$ is called connected if for every two question pairs
$(x^{1},x^{2},\ldots,x^{k})$ and $(x^{\prime 1},x^{\prime 2},\ldots,x^{\prime
k})$ from $\mathsf{supp}(\mu(G))$, there is an ordered list of questions from
$\mathsf{supp}(\mu(G))$,
$((x^{1}_{\ell},x^{2}_{\ell},\ldots,x^{k}_{\ell}))_{\ell=1}^{t}$ for some
$t\geqslant 1$, such that the pairs
$((x^{1},x^{2},\ldots,x^{k}),(x^{1}_{1},x^{2}_{1},\ldots,x^{k}_{1}))$,
$((x^{1}_{t},x^{2}_{t},\ldots,x^{k}_{t}),(x^{\prime 1},x^{\prime
2},\ldots,x^{\prime k}))$, and
$((x^{1}_{\ell},x^{2}_{\ell},\ldots,x^{k}_{\ell}),(x^{1}_{\ell+1},x^{2}_{\ell+1},\ldots,x^{k}_{\ell+1}))$
for all $1\leqslant\ell\leqslant t-1$ differ in only one out of the $k$
questions.

We will relate the value of $G^{\otimes n}$, where $G$ is a projection game,
with a value of $n$-fold parallel repetition of another game $H$ that is
connected. The following theorem shows that for connected games with a value
less than $1$, the value of repeated games goes down exponentially in $n$.

######  Theorem 2.2 ([DHVY17]).

For any $k\geqslant 2$ and $\varepsilon>0$, if $H$ is a connected $k$-player
game with $\mathbf{val}(H)=1-\varepsilon$, then $\mathbf{val}(H^{\otimes
n})\leqslant\exp({-\Omega_{\varepsilon,H}(n)})$.

###  2.2 Variants of multiplayer games

In this section, we simplify the class of games that we study. Towards this,
we define the notion of loosely-connected games as follows.

######  Definition 2.3 (Loosely-connected game).

A game on the question set
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$ is
loosely-connected if it is not possible to partition
$\mathcal{X}_{i}=\mathcal{X}^{\prime}_{i}\cup\mathcal{X}^{\prime\prime}_{i}$
for all $i\in[k]$, so that all $k$-tuple of questions from the support of
$\mu(G)$ are in
$\mathcal{X}^{\prime}_{1}\times\mathcal{X}^{\prime}_{2}\times\ldots\times\mathcal{X}^{\prime}_{k}$
or
$\mathcal{X}^{\prime\prime}_{1}\times\mathcal{X}^{\prime\prime}_{2}\times\ldots\times\mathcal{X}^{\prime\prime}_{k}$.

The following lemma states that we can assume without loss of generality that
the game $G$ is loosely-connected.

######  Lemma 2.4.

If the exponential decay in the $k$-player parallel repetition holds for all
projection loosely-connected games, then it also holds for all projection
games.

###### Proof.

We defer the proof of this lemma to the appendix. ∎

We also consider a slight variation in the definition of $k$-player games,
that we call random-predicate $k$-player games, where we allow a verifier to
use a random predicate instead of a fixed predicate during verification.

######  Definition 2.5 (Random-predicate game).

A random-predicate game $G$ is defined as follows. There exists $R\geqslant 1$
such that the verifier chooses the $k$-tuple of questions
$(x^{1},x^{2},\ldots,x^{k})$ according to the distribution $\mu(G)$ on the set
of questions and $r\in[R]$ uniformly at random, sends $x^{i}$ to player $i$.
The player $i$ responds with the answer $a^{i}$. Finally, the verifier accepts
the answers based on a fixed predicate
$V_{r}((x^{1},x^{2},\ldots,x^{k}),(a^{1},a^{2},\ldots,a^{k}))$. We denote such
games by $(G,\mu,[R])$.

The following lemma states that for this variation of connected $k$-player
games $G$ the exponential decay from [DHVY17] still holds.

######  Lemma 2.6.

For any connected random-predicate $k$-player game $H$ and $\varepsilon>0$, if
$\mathbf{val}(H)=1-\varepsilon$, then $\mathbf{val}(H^{\otimes
n})\leqslant\exp({-\Omega_{\varepsilon,H}(n)})$.

###### Proof.

We can think of a random-predicate $k$-player game $H$ as a $(k+1)$-player
game $H^{\prime}$ as follows. In $H^{\prime}$, the verifier selects the
questions $(x^{1},x^{2},\ldots,x^{k})$ from the game $H$ and $r\in[R]$
uniformly at random. The verifier sends $x^{i}$ to players $i$ for $i\in[k]$,
and sends $r$ to player $k+1$. The player $i\in[k+1]$ responds with the answer
$a^{i}$ ($a^{k+1}$ can be anything). The verifier’s predicate in $H^{\prime}$
is
$V((x^{1},x^{2},\ldots,x^{k},r),(a^{1},a^{2},\ldots,a^{k},a^{k+1})):=V_{r}((x^{1},x^{2},\ldots,x^{k}),(a^{1},a^{2},\ldots,a^{k}))$.

It is easy to observe that if the game $H^{\prime}$ is connected then the game
$H$ is connected. Furthermore, we have $\mathbf{val}(H^{\otimes
n})=\mathbf{val}(H^{\prime\otimes n})$ for any $n\geqslant 1$. Using this, the
lemma follows from Theorem 2.2. ∎

In our proof, we will encounter random-predicate games where the choice of the
verifier’s predicate $V_{r}$ is not uniform and may depend on the question
$q$. The following claims says that we can assume that the distribution on
verifier’s predicate is uniform form a set of predicates and independent of
the questions. This transformation preserves the support of the question-
distribution.

######  Claim 2.7.

Suppose $G$ is a random-predicate $k$-player game where on the $k$-tuple of
question
$q\in\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$,
the distribution on the verifier’s predicate $V_{r}$ is sampled according to
some distribution $\nu_{q}$ over $[R]$, then there is another game $H$ with
the same distribution on the questions as in $G$ such that the verifier for
$H$ samples a random predicate $\tilde{V}_{m}$ where $m\in[M]$ is distributed
uniformly over $[M]$, and such that $\mathbf{val}(G^{\otimes
n})=\mathbf{val}(H^{\otimes n})$ for all $n\geqslant 1$. Furthermore, $M$ only
depends on the size of the game $G$.

###### Proof.

Let $M\in\mathbb{Z}^{+}$ be a number such that for every question $q$ from the
game $G$, each atom from $\mathsf{supp}(\nu_{q})$ has probability weight $c/M$
for $1\leqslant c\leqslant M$. In the game $G$, for a question $q$ if
$\nu_{q}(r)=c/M$, then in game $H$, we make $c$ copies
$\tilde{V}_{i_{1}}(q,\cdot),\tilde{V}_{i_{2}}(q,\cdot),\ldots,\tilde{V}_{i_{c}}(q,\cdot)$
of the verifier predicate $V_{r}(q,\cdot)$ for the same question $q$. Thus,
for a given question $q$, the verifier in $H$ samples a random $m\in[M]$ and
decides based on the predicate $\tilde{V}_{m}(q,\cdot)$. ∎

##  3 Proof of Theorem 1.2

Throughout this section, we fix a random-predicate $k$-player projection game
$(G,\mu,[R])$, succinctly written as $G$, on the questions from the set
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$ and
let $\mu(G)$ be the distribution on the questions in $G$. Using Claim 2.7, we
can assume without loss of generality, that along with the $k$-tuple questions
$(x^{1},x^{2},\ldots,x^{k})\sim\mu$, the verifier selects $r\in[R]$ uniformly
at random, and after getting answers $(a^{1},a^{2},\ldots,a^{k})$ from the
players, applies the predicate
$V_{r}((x^{1},x^{2},\ldots,x^{k})),(a^{1},a^{2},\ldots,a^{k}))$.

The key idea is to use the path-trick from [BKM23] to relate the value of the
game $G$ (and $G^{\otimes n}$) to another game $H$ (and $H^{\otimes n}$) which
is connected.

###  3.1 The path-trick and the $i$-links

In this section, we define the notion of a link which is analogous to the
notion of the path-trick [BKM23] that was used in connection to studying
dictatorship tests towards showing hardness of approximation of constraint
satisfaction problems.

Fix a player $i\in[k]$. An $i$-link from a game $G$ is an ordered pair of
original $k$-tuple of questions from $G$ with possible repetition. We will
induce the following distribution on $i$-links from $G$.

  * •

Pick a question $v$ to player $i$ according to the distribution of $\mu|_{i}$
and sample two $k$-tuple of questions $q=(x^{1},x^{2},\ldots,x^{k})$ and
$q^{\prime}=(y^{1},y^{2},\ldots,y^{k})$, independently from $\mu$ but
conditioned on $x^{i}=y^{i}=v$ and output $(q,q^{\prime})$.

We denote the above distribution on the $i$-links with $L_{i}(G)$.

To see the utility of $i$-links, the following claim shows that the
distribution $L_{i}(G^{\otimes n})$ on the $i$-links in $G^{\otimes n}$ is the
same as the product distribution on the $i$-links from $G$.

######  Claim 3.1.

For every game $G$, $i\in[k]$, and $n\geqslant 1$, the following two
distributions are identical.

  1. 1.

The distribution $L_{i}(G^{\otimes n})$.

  2. 2.

The distribution $\mathcal{D}_{i}$ on the $i$-links from $G^{\otimes n}$
defined as follows:

     * •

For each $j\in[n]$, independently sample $(q_{j},q^{\prime}_{j})$ from the
distribution $L_{i}(G)$ where $q_{j}=(x^{1}_{j},x^{2}_{j},\ldots,x^{k}_{j})$
and $q^{\prime}_{j}=(y^{1}_{j},y^{2}_{j},\ldots,y^{k}_{j})$.

     * •

Let $\vec{q}=(q_{1},q_{2},\ldots,q_{n})$ and
$\vec{q^{\prime}}=(q^{\prime}_{1},q^{\prime}_{2},\ldots,q^{\prime}_{n})$.
Output $(\vec{q},\vec{q^{\prime}})$.

###### Proof.

Note that $\vec{q}$ and $\vec{q^{\prime}}$, sampled from $\mathcal{D}_{i}$,
are the following $k$-tuple of questions

$\displaystyle\begin{array}[]{cc}(x^{1}_{1},x^{1}_{2},\ldots,x^{1}_{n})&(y^{1}_{1},y^{1}_{2},\ldots,y^{1}_{n})\\\
(x^{2}_{1},x^{2}_{2},\ldots,x^{2}_{n})&(y^{2}_{1},y^{2}_{2},\ldots,y^{2}_{n})\\\
\vdots&\vdots\\\
\underbrace{(x^{k}_{1},x^{k}_{2},\ldots,x^{k}_{n})}_{\vec{q}}&\underbrace{(y^{k}_{1},y^{k}_{2},\ldots,y^{k}_{n})}_{\vec{q^{\prime}}}\\\
\end{array}$

For each $j\in[n]$, the pair of $k$-tuple of questions
$(x^{1}_{j},x^{2}_{j},\ldots,x^{k}_{j})$ and
$(y^{1}_{j},y^{2}_{j},\ldots,y^{k}_{j})$ share a common pivot question
$p_{j}=x^{i}_{j}=y^{i}_{j}$. This means that the question-pair
$(\vec{q},\vec{q^{\prime}})$ share a common $n$-tuple question $\vec{p}$ from
player $i$, where we think of $\vec{q},\vec{q^{\prime}}$ as questions from the
game $G^{\otimes n}$. This precisely corresponds to the distribution
$L_{i}(G^{\otimes n})$. ∎

Consider the game $G$ the assignments
$\alpha^{i}:\mathcal{X}_{i}\rightarrow\mathcal{A}_{i}$ for $i\in[k]$. We say
that the link $(q,q^{\prime})$ from the game $G$ is $r$-consistent with
respect to the global assignments $(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$
if $q$ as well as $q^{\prime}$ are satisfied by the predicate $V_{r}$ on the
assignments $(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$.

######  Claim 3.2.

Let $n\geqslant 1$, $(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$ be a strategy
for $(G,\mu,[R])$ with $\mathbf{val}(G)\geqslant\varepsilon$. Then with
probability at least $\varepsilon^{2}$, the link $(q,q^{\prime})$ is
$r$-consistent with the assignments
$(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$, where the probability is over
$(q,q^{\prime})$ sampled according to $L_{i}(G)$ and $r\in[R]$ uniformly at
random.

###### Proof.

Fix the provers’ strategies
$\alpha^{i}:\mathcal{X}_{i}\rightarrow\mathcal{A}_{i}$ for $i\in[k]$ with
value at least $\varepsilon$. We have,

$\mathop{\mathbf{E}}_{\begin{subarray}{c}(x^{1},x^{2},\ldots,x^{k})\sim\mu,\\\
r\in[R]\end{subarray}}[V_{r}((x^{1},x^{2},\ldots,x^{k}),(\alpha^{1}(x^{1}),\alpha^{2}(x^{2}),\ldots,\alpha^{k}(x^{k})))]\geqslant\varepsilon.$

Using the Cauchy-Schwarz inequality, we have,

$\displaystyle\varepsilon^{2}$
$\displaystyle\leqslant\mathop{\mathbf{E}}_{\begin{subarray}{c}(x^{1},x^{2},\ldots,x^{k})\sim\mu,\\\
r\in[R]\end{subarray}}[V_{r}((x^{1},x^{2},\ldots,x^{k}),(\alpha^{1}(x^{1}),\alpha^{2}(x^{2}),\ldots,\alpha^{k}(x^{k})))]^{2}$
$\displaystyle=\left(\mathop{\mathbf{E}}_{\begin{subarray}{c}v\in\mu|_{i}\\\
r\in[R]\end{subarray}}\left[\mathop{\mathbf{E}}_{\begin{subarray}{c}(x^{1},x^{2},\ldots,x^{k})\sim\mu\\\
x^{i}=v\end{subarray}}[V_{r}((x^{1},x^{2},\ldots,x^{k}),(\alpha^{1}(x^{1}),\alpha^{2}(x^{2}),\ldots,\alpha^{k}(x^{k})))\right]\right)^{2}$
$\displaystyle\leqslant\mathop{\mathbf{E}}_{\begin{subarray}{c}v\in\mu|_{i}\\\
r\in[R]\end{subarray}}\left[\mathop{\mathbf{E}}_{\begin{subarray}{c}(x^{1},x^{2},\ldots,x^{k})\sim\mu\\\
x^{i}=v\end{subarray}}[V_{r}((x^{1},x^{2},\ldots,x^{k}),(\alpha^{1}(x^{1}),\alpha^{2}(x^{2}),\ldots,\alpha^{k}(x^{k})))]\right]^{2}\quad\quad\quad$
(Cauchy-Schwarz)
$\displaystyle=\mathop{\mathbf{E}}_{\begin{subarray}{c}v\in\mu|_{i}\\\
r\in[R]\end{subarray}}\left[\mathop{\mathbf{E}}_{\begin{subarray}{c}(x^{1},x^{2},\ldots,x^{k})\sim\mu,\\\
(y^{1},y^{2},\ldots,y^{k})\sim\mu,\\\
x^{i}=y^{i}=v\end{subarray}}\left[\begin{array}[]{c}V_{r}((x^{1},x^{2},\ldots,x^{k}),(\alpha^{1}(x^{1}),\alpha^{2}(x^{2}),\ldots,\alpha^{k}(x^{k})))\cdot\\\
V_{r}((y^{1},y^{2},\ldots,y^{k}),(\alpha^{1}(y^{1}),\alpha^{2}(y^{2}),\ldots,\alpha^{k}(y^{k})))\end{array}\right]\right].$

The expression inside the expectation above is precisely the probability that
the $i$-link $((x^{1},x^{2},\ldots,x^{k}),$ $(y^{1},y^{2},\ldots,y^{k}))$
sampled from the distribution $L_{i}(G)$ is $r$-consistent with respect to the
assignments $(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$. This shows that

$\Pr_{\begin{subarray}{c}(q,q^{\prime})\sim L_{i}(G)\\\
r\in[R]\end{subarray}}\left[(q,q^{\prime})\mbox{ is $r$-consistent with
respect to the assignments
}(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})\right]\geqslant\varepsilon^{2},$

and this completes the proof. ∎

###  3.2 The transformations $\mathcal{T}^{i}_{p}$

We are now ready to define the transformation on the game $G$ that was alluded
to at the beginning of this section. We denote the transformed games by
$\mathcal{T}^{i}_{p}(G)$ for $1\leqslant i,p\leqslant k$.

The distribution on the $k$-tuple of questions in the game
$\mathcal{T}^{i}_{p}(G)$ is over
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$ which
is defined as follows.

  1. 1.

The verifier samples a link $(q,q^{\prime})\sim L_{i}(G)$ where
$q=(x^{1},x^{2},\ldots,x^{k})$ and $q^{\prime}=(y^{1},y^{2},\dots,y^{k})$

  2. 2.

The verifier constructs a $k$-tuple of question by taking $x^{p}$ from $q$ and
$(y^{1},\ldots,y^{p-1},y^{p+1},\dots,y^{k})$ from $q^{\prime}$. Succinctly, we
denote this operation as
$(y^{1},\ldots,y^{p-1},x^{p},y^{p+1},\ldots,y^{k}):=\Pi^{p}((q,q^{\prime}))$
(the $p$ stands for taking player $p$’s question from the first question and
the remaining players’ questions from the second question).

Before we define the set of satisfying assignments in the transformed game, we
first define the set of $r$-consistent assignments, where $r\in[R]$, to an
$i$-link. An assignment to a link $(q,q^{\prime})$ is an assignment to both
$q$ and $q^{\prime}$ (note that each $k$-tuple of question receives a separate
assignment from
$\mathcal{A}_{1}\times\mathcal{A}_{2}\times\ldots\times\mathcal{A}_{k}$). For
an $i$-link $(q,q^{\prime})$, we define the set of $r$-consistent assignments
to $(q,q^{\prime})$ as follows. An $r$-consistent assignment to an $i$-link
$(q,q^{\prime})$ is an assignment $\sigma$ to the link such that

  * •

the verifier accepts $\sigma|_{q}$ on $q$ and $\sigma|_{q^{\prime}}$ on
$q^{\prime}$ according to the predicate $V_{r}$, and

  * •

$\sigma|_{q|_{i}}=\sigma|_{q^{\prime}|_{i}}$, i.e., $\sigma$ gives the same
value to the common question $v$ to the player $i$ from $q$ and $q^{\prime}$.

Note that an $i$-link $(q,q^{\prime})$ may share more than one common question
to the players, but the $r$-consistency only cares about the question to
player $i$.

We now define the set of accepting assignments for a $k$-tuple of questions in
the random-predicate transformed game. The verifier chooses $r\in[R]$
uniformly at random. Suppose a $k$-tuple of questions
$\tilde{q}=(z^{1},z^{2},\ldots,z^{k})$ is coming from an $i$-link
$(q,q^{\prime})$, i.e., $\tilde{q}=\Pi^{p}((q,q^{\prime}))$, then

  * •

Case 1: If $q\neq q^{\prime}$, then accept by default.

  * •

Case 2: If $q=q^{\prime}$, then $\tilde{q}=q$. In this case, accept according
to the verifier’s predicate $V_{r}$ from the game $G$ on question $\tilde{q}$.

Note that the game $\mathcal{T}^{i}_{p}(G)$ is a random-predicate $k$-player
game (the accepting answers for a question $\tilde{q}$ depends on the
underlying sampled link as well as the sampled $r\in[R]$), and as described,
the distribution on the underlying predicate is not uniform among the set of
predicates. However, using Claim 2.7, without loss of generality, we can
assume that the underlying distribution on the predicate that the verifier
applies in $\mathcal{T}^{i}_{p}(G)$ is uniform from a set of predicates (and
independent of the questions). We need this as we will be applying a series of
these transformations on the original game, and the transformation above is
only defined on games where the verifier’s predicate is uniform and
independent of the question $q$.

In the transformed game, the verifier either accepts all the answers or
accepts answers based on the predicates from the original game $G$. We have
the following simple, but important, fact.

######  Fact 3.3.

If $G$ is a random-predicate $k$-player projection game, then for every
$i,p\in[k]$, the game $\mathcal{T}^{i}_{p}(G)$ is also a random-predicate
projection game.

####  3.2.1 Properties of the transformations $\mathcal{T}^{i}_{p}$

We start with the first claim that shows that the value of the transformed
games is less than $1$ if the value of $G$ is less than $1$.

######  Claim 3.4.

Fix any $k$-player game $(G,\mu,[R])$. For every $\varepsilon\in(0,1)$ and
$i,p\in[k]$, if $\mathbf{val}(G)=1-\varepsilon$, then
$\mathbf{val}(\mathcal{T}^{i}_{p}(G))=1-\varepsilon^{\prime}$ where
$\varepsilon^{\prime}>0$ that depends on $\varepsilon$ and the size of the
game $G$.

###### Proof.

First, observe that for every question-tuple $q=(x^{1},x^{2},\ldots,x^{k})$
from the game $G$, the $i$-link $(q,q)$ is present in the support of
$L_{i}(G)$. Therefore, for every question-tuple $q=(x^{1},x^{2},\ldots,x^{k})$
from the game $\mathcal{T}^{i}_{p}(G)$ that is given by the $i$-link $(q,q)$,
the verifier of the transformed game selects $r\in[R]$ uniformly at random and
uses the predicate $V_{r}$. Therefore, the transformed game
$\mathcal{T}^{i}_{p}(G)$ is a convex combination of the original game $G$ and
another game $G^{\prime}$. Let $\tilde{\mu}$ be the distribution on question-
tuples in $\mathcal{T}^{i}_{p}(G)$, then it can be written as
$\tilde{\mu}=\delta\mu+(1-\delta)\mu^{\prime}$, where $\mu^{\prime}$
corresponds to the distribution of questions from game $G^{\prime}$ and
$\delta\in(0,1]$ that depends on the size of the game $G$. Thus,

$\mathbf{val}(\mathcal{T}^{i}_{p}(G))\leqslant\delta\cdot\mathbf{val}(G)+(1-\delta)=\delta(1-\varepsilon)+(1-\delta)=1-\varepsilon\delta<1.$

∎

The following claim relates the value of the original game with the value of
the transformed games. This claim crucially uses the fact that the original
game $G$ is a projection game.

######  Claim 3.5.

For any $k$-player projection game $(G,\mu,[R])$, $n\geqslant 1$, and
$i,p\in[k]$, $\mathbf{val}(\mathcal{T}^{i}_{p}(G)^{\otimes
n})\geqslant\mathbf{val}(G^{\otimes n})^{2}$.

###### Proof.

As the statement of the claim is symmetric with respect to $p\in[k]$, we prove
the claim when $p=1$. For other $p$, the proof is similar.

Using Claim 3.1, the game $\mathcal{T}^{i}_{1}(G)^{\otimes n}$ can be
described as follows: Sample an $i$-link $(\vec{q},\vec{q}^{\prime})$ from the
distribution $L_{i}(G^{\otimes n})$, sample $\vec{r}\in[R]^{n}$ uniformly at
random, and for every $j\in[n]$ such that $q_{j}=q^{\prime}_{j}$, apply the
predicate $V_{r_{j}}$ for the question $\Pi^{1}((q_{j},q_{j}))$.

Let’s fix the players’ strategy
$\alpha:=(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$ for the game $G^{\otimes
n}$ that gives the value $\mathbf{val}(G^{\otimes n})$. For an $i$-link
$(\vec{q},\vec{q}^{\prime})$ from $G^{\otimes n}$, consider the assignments
$\alpha|_{\vec{q}}$ and $\alpha|_{\vec{q}^{\prime}}$ to the link
$(\vec{q},\vec{q}^{\prime})$. Using Claim 3.2, for a random
$\vec{r}\in[R]^{n}$ and a randomly selected $i$-link
$(\vec{q},\vec{q}^{\prime})$, $(\vec{q},\vec{q}^{\prime})$ is
$\vec{r}$-consistent with respect to the global assignment $\alpha$ with
probability at least $\mathbf{val}(G^{\otimes n})^{2}$. When this happens, we
show that the assignment $\alpha$ satisfies the constraint on
$\Pi^{1}((\vec{q},\vec{q}^{\prime}))$ from the game
$\mathcal{T}^{i}_{1}(G)^{\otimes n}$. Indeed, pick any $j\in[n]$ such that the
$j^{th}$ coordinate of the link $(\vec{q},\vec{q}^{\prime})$ is
$(q_{j},q_{j})$ (i.e, the same question-tuple). Here, the verifier is using
the predicate $V_{r_{j}}$ on the question $q_{j}$ in the game
$\mathcal{T}^{i}_{1}(G)^{\otimes n}$. If the link
$(\vec{q},\vec{q}^{\prime})$, is $\vec{r}$-consistent with respect to the
global assignment $\alpha$, then we have the following

$V_{r_{j}}((q_{j}|_{1},q_{j}|_{2},\ldots,q_{j}|_{k}),(\alpha^{1}(\vec{q}|_{1})_{j},\alpha^{2}(\vec{q}|_{2})_{j},\ldots,\alpha^{k}(\vec{q}|_{k})_{j}))=1,$
$V_{r_{j}}((q_{j}|_{1},q_{j}|_{2},\ldots,q_{j}|_{k}),(\alpha^{1}(\vec{q^{\prime}}|_{1})_{j},\alpha^{2}(\vec{q^{\prime}}|_{2})_{j},\ldots,\alpha^{k}(\vec{q^{\prime}}|_{k})_{j}))=1.$

In game $\mathcal{T}^{i}_{1}(G)^{\otimes n}$, the verifier is checking the
following condition in the coordinate $j$.

$V_{r_{j}}((q_{j}|_{1},q_{j}|_{2},\ldots,q_{j}|_{k}),(\alpha^{1}(\vec{q}|_{1})_{j},\alpha^{2}(\vec{q^{\prime}}|_{2})_{j},\ldots,\alpha^{k}(\vec{q^{\prime}}|_{k})_{j}))=1.$

Because $G$ and the predicates $V_{r}$ satisfy the projection property, and
$\vec{q}|_{i}=\vec{q^{\prime}}|_{i}$ because $(\vec{q},\vec{q^{\prime}})$ is
an $i$-link, we see that if
$(\alpha^{1}(\vec{q}|_{1})_{j},\alpha^{2}(\vec{q}|_{2})_{j},\ldots,\alpha^{k}(\vec{q}|_{k})_{j})$
and
$(\alpha^{1}(\vec{q^{\prime}}|_{1})_{j},\alpha^{2}(\vec{q^{\prime}}|_{2})_{j},\ldots,\alpha^{k}(\vec{q^{\prime}}|_{k})_{j})$
are the accepting answers for a question according to the predicate
$V_{r_{j}}$, then
$(\alpha^{1}(\vec{q}|_{1})_{j},\alpha^{2}(\vec{q^{\prime}}|_{2})_{j},\ldots,\alpha^{k}(\vec{q^{\prime}}|_{k})_{j})$
is also an accepting answer for the same question according to the same
predicate $V_{r_{j}}$. This shows that the assignment $\alpha$ passes the
verifier’s check on all $j\in[n]$ such that the $j^{th}$ coordinate of the
link $(\vec{q},\vec{q}^{\prime})$ is $(q_{j},q_{j})$. For the other
coordinates, the game $\mathcal{T}^{i}_{1}(G)$ always accepts.

Hence the same players’ strategy $\alpha$ gives
$\mathbf{val}(\mathcal{T}^{i}_{1}(G)^{\otimes
n})\geqslant\mathbf{val}(G^{\otimes n})^{2}$. ∎

Finally, we compose these transformations to get a connected game, starting
with a loosely-connected game. Towards this, for any string
$\beta\in([k]\times[k])^{m}$, where
$\beta_{j}=(\beta^{1}_{j},\beta^{2}_{j})\in[k]\times[k]$, define the
transformation $\mathcal{T}^{\beta}(G)$ as the following transformation

$\mathcal{T}^{\beta^{1}_{m}}_{\beta^{2}_{m}}(\ldots(\mathcal{T}^{\beta^{1}_{2}}_{\beta^{2}_{2}}(\mathcal{T}^{\beta^{1}_{1}}_{\beta^{2}_{1}}(G)))).$

For a string $\beta$ of length $m$, define a string $\beta^{T}$ as a $T$
repeated copy of $\beta$. We have the following claim.

######  Claim 3.6.

Let $\beta$ be any permutation of the set $[k]\times[k]$. For large enough
$T\geqslant 1$, the game $\mathcal{T}^{\beta^{T}}(G)$ is connected (in fact,
has full support) if $G$ is loosely-connected to begin with. Furthermore,
$T\leqslant\prod_{i=1}^{k}|\mathcal{X}_{i}|$ which only depends on the size of
the game $G$.

###### Proof.

First, any transformation $\mathcal{T}^{i}_{p}$ does not shrink the support of
the questions of the previous game. By looking closely at the transformation
$\mathcal{T}^{i}_{p}$, we conclude the following: if
$(x^{1},x^{2},\ldots,x^{k})$ and $(y^{1},y^{2},\ldots,y^{k})$ are both in the
support of $\mu(G)$ with $x^{i}=y^{i}$, then the following question
$(y^{1},\dots,y^{p-1},x^{p},y^{p+1},\ldots,y^{k})$ will be in the support of
$\mu(\mathcal{T}^{i}_{p}(G))$. Using this, we also observe that if we start
with any game $H$ with the property that the series of transformations
$\mathcal{T}^{\beta}(H)$ does not change the support of the questions, then no
future transformations will change the support on the questions (as $\beta$
contains every possible transformation $\mathcal{T}^{i}_{p}$).

From the above discussion, we conclude that after some finite (only depends on
the size of the game $G$) series of such transformations
$\mathcal{T}^{\beta^{T}}(.)$, the support of the questions does not increase
after another series of transformations $\mathcal{T}^{\beta}$. We denote the
saturated game by $G_{\mathsf{final}}:=\mathcal{T}^{\beta^{T}}(G)$ and the
underlying distribution on the questions by $\mu_{\mathsf{final}}$. We show
that $\mu_{\mathsf{final}}$ has full support on
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\ldots\times\mathcal{X}_{k}$.

Suppose towards a contradiction, the support of $\mu_{\mathsf{final}}$ is not
full. For any tuple $q$ of length $k$ and $S\subseteq[k]$, define the tuple
$q|_{S}$ by taking the $S$ entries from $q$. Take the smallest $i\in[k]$ such
that there is an $i$-tuple $(z^{1},z^{2},\ldots,z^{i})$ where
$(z^{1},z^{2},\ldots,z^{i})\neq q|_{[i]}$ for any
$q\in\mathsf{supp}(\mu_{\mathsf{final}})$. Let
$z^{\star}:=(z^{1},z^{2},\ldots,z^{i-1})$. For each $i\leqslant\ell\leqslant
k$, define the following sets.

$\mathcal{S}_{\ell}=\\{x\in\mathcal{X}_{\ell}\mid\exists
q\in\mathsf{supp}(\mu_{\mathsf{final}})\mbox{ s.t.
}(z^{\star},x)=q|_{[i-1]\cup\\{\ell\\}}\\}.$

In other words, $\mathcal{S}_{\ell}$ is a set of all $x\in\mathcal{X}_{\ell}$
that $(z^{\star},x)$ can be extended to a valid question tuple from the game
$G_{\mathsf{final}}$. Note that by the definition of $z^{\star}$,
$\mathcal{S}_{i}\subsetneq\mathcal{X}_{i}$ and furthermore
$\mathcal{S}_{i^{\prime}}\neq\emptyset$ for any $i^{\prime}\geqslant i$, as by
the minimality of $i$, there is a valid question $q$ in $G_{\mathsf{final}}$
such that $q|_{[i-1]}=z^{\star}$, and hence
$q|_{i^{\prime}}\in\mathcal{S}_{i^{\prime}}$ for all $i^{\prime}\geqslant i$.

######  Claim 3.7.

There is no $q\in\mathsf{supp}(\mu_{\mathsf{final}})$ such that
$q|_{i}\in\overline{\mathcal{S}_{i}}$ and for some $i^{\prime}>i$,
$q|_{i^{\prime}}\in\mathcal{S}_{i^{\prime}}$.

###### Proof.

Suppose there is such a question $q\in\mathsf{supp}(\mu_{\mathsf{final}})$
such that $q|_{i}\in\overline{\mathcal{S}_{i}}$ and for some $i^{\prime}>i$,
$q|_{i^{\prime}}\in\mathcal{S}_{i^{\prime}}$. Consider a question
$q^{\prime}=(z^{1},z^{2},\ldots,z^{i-1},*,*,\ldots)$ where
$q^{\prime}|_{i^{\prime}}=q|_{i^{\prime}}$. Note that such a $q^{\prime}$ is
in the $\mathsf{supp}(\mu_{\mathsf{final}})$ from the definition of the set
$\mathcal{S}_{i^{\prime}}$. Furthermore, $(q,q^{\prime})$ is an
$i^{\prime}$-link in the game $G_{\mathsf{final}}$. Therefore, the question
$\Pi^{i}((q,q^{\prime}))$ will be present in the game
$\mathcal{T}^{i^{\prime}}_{i}(G_{\mathsf{final}})$. Recall that
$\Pi^{i}((q,q^{\prime}))=(z^{1},z^{2},\ldots,z^{i-1},q|_{i},*,\ldots)$.
However, the question $(z^{1},z^{2},\ldots,z^{i-1},q|_{i},*,\ldots)$ is not in
$\mathsf{supp}(\mu_{\mathsf{final}})$ as
$q|_{i}\in\overline{\mathcal{S}_{i}}$. This means that the game
$G_{\mathsf{final}}$ is not saturated, which is a contradiction. ∎

This claim implies that
$\mathcal{S}_{i^{\prime}}\subsetneq\mathcal{X}_{i^{\prime}}$ for all
$i^{\prime}>i$ . Indeed, if
$\mathcal{S}_{i^{\prime}}=\mathcal{X}_{i^{\prime}}$ for some $i^{\prime}>i$,
then the above claim shows that every question
$q\in\mathsf{supp}(\mu_{\mathsf{final}})$, $q|_{i}\in\mathcal{S}_{i}$. Hence,
$G_{\mathsf{final}}$ (and hence $G$) is not a loosely-connected game.

This claim also implies that for every question
$q\in\mathsf{supp}(\mu_{\mathsf{final}})$ such that
$q|_{i}\in\overline{\mathcal{S}_{i}}$, we have
$q|_{i^{\prime}}\in\overline{\mathcal{S}_{i^{\prime}}}$ for every
$i^{\prime}>i$. Consider the partition of the players’ question sets
$\mathcal{X}_{\ell}=\mathcal{X}^{\prime}_{\ell}\cup\mathcal{X}^{\prime\prime}_{\ell}$
such that

  * •

For all $\ell\leqslant i-1$, $\mathcal{X}^{\prime}_{\ell}=\\{z^{\ell}\\}$, and
$\mathcal{X}^{\prime\prime}_{\ell}=\mathcal{X}_{\ell}\setminus\mathcal{X}^{\prime}_{\ell}$,

  * •

for all $t\geqslant\ell$, $\mathcal{X}^{\prime}_{\ell}=\mathcal{S}_{\ell}$,
and
$\mathcal{X}^{\prime\prime}_{\ell}=\mathcal{X}_{\ell}\setminus\mathcal{X}^{\prime}_{\ell}$.

Because $G$ (and hence $G_{\mathsf{final}}$) is loosely connected, there must
be a question $q\in\mathsf{supp}(\mu_{\mathsf{final}})$ such that
$q|_{i^{\prime}}\in\overline{\mathcal{S}_{i^{\prime}}}$ for every
$i^{\prime}\geqslant i$ and $q|_{t}=z^{t}$ for some $1\leqslant t\leqslant
i-1$. Consider a question $q^{\prime}=(z^{1},z^{2},\ldots,z^{i-1},*,*,\ldots)$
such that $q^{\prime}$ is in the $\mathsf{supp}(\mu_{\mathsf{final}})$. Now,
the pair of questions $(q^{\prime},q)$ is an $t$-link in the game
$G_{\mathsf{final}}$, furthermore, for a questions
$q^{\prime\prime}:=\Pi^{i}((q,q^{\prime}))$, we have
$q^{\prime\prime}=(z^{1},z^{2},z^{3},\ldots,z^{i-1},q|_{i},\ldots)$ where
$q|_{i}\in\overline{\mathcal{S}_{i}}$. As $G_{\mathsf{final}}$ is saturated,
$q^{\prime\prime\prime}\in\mathsf{supp}(\mu_{\mathsf{final}})$ but this
contradicts the definition of $\mathcal{S}_{i}$. ∎

###  3.3 Finishing the proof

Let us see why these claims above are enough to prove Theorem 1.2.

##### Proof of Theorem 1.2.

We start with a projection game $G$ with $\mathbf{val}(G)=1-\varepsilon$ for
some $\varepsilon>0$. First, using Lemma 2.4, we can assume without loss of
generality that $G$ is loosely-connected. Let
$(\vec{i},\vec{p})\in([k]\times[k])^{Tk^{2}}$ with
$(\vec{i},\vec{p})=\beta^{T}$, i.e., $(i_{t},p_{t})$ is the $t^{th}$ entry
from the string $\beta^{T}$, where $\beta$ and $T$ are from Claim 3.6. Let
$T^{\prime}=T\cdot k^{2}$.
Using Claim 3.5 on the projection game $G$ with $i_{1},p_{1}\in[k]$, we have

$\mathbf{val}(G^{\otimes
n})\leqslant\mathbf{val}(\mathcal{T}^{i_{1}}_{p_{1}}(G)^{\otimes n})^{1/2}.$

Fact 3.3 shows that $\mathcal{T}^{i_{1}}_{p_{1}}(G)$ is a projection game, and
hence applying Claim 3.5 on the projection game
$\mathcal{T}^{i_{1}}_{p_{1}}(G)$ with $i_{2},p_{2}\in[k]$, we get

$\mathbf{val}(\mathcal{T}^{i_{1}}_{p_{1}}(G)^{\otimes
n})\leqslant\mathbf{val}(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G))^{\otimes
n})^{1/2}.$

Repeating this process $T^{\prime}$ times, we get

$\mathbf{val}(G^{\otimes
n})\leqslant\mathbf{val}(\mathcal{T}^{i_{T^{\prime}}}_{p_{T^{\prime}}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G))))^{\otimes
n})^{1/2^{T^{\prime}}}.$

Using Claim 3.4 repeatedly, we have

$\mathbf{val}(\mathcal{T}^{i_{T^{\prime}}}_{p_{T^{\prime}}}(\ldots(\mathcal{T}^{i_{2}}_{p_{1}}(\mathcal{T}^{i_{1}}_{p_{1}}(G)))))\leqslant
1-\varepsilon^{\prime},$

where $\varepsilon^{\prime}>0$, that only depends on $\varepsilon$,
$T^{\prime}$, and the size of the game $G$. Finally, using Claim 3.6, we have
that the game
$\mathcal{T}^{i_{T^{\prime}}}_{p_{T^{\prime}}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G))))$
is connected and hence by Lemma 2.6,

$\mathbf{val}(\mathcal{T}^{i_{T^{\prime}}}_{p_{T^{\prime}}}(\ldots(\mathcal{T}^{i_{2}}_{p_{2}}(\mathcal{T}^{i_{1}}_{p_{1}}(G))))^{\otimes
n})\leqslant\exp(-\Omega_{\varepsilon,T,G}(n)).$

Overall, we get $\mathbf{val}(G^{\otimes
n})\leqslant\exp(-\Omega_{\varepsilon,T,G}(n))$ and the proof is completed as
$T$ only depends on the size of the original game $G$.

##### Acknowledgement.

We thank Kunal Mittal for helpful discussions at the early stage of this work.

## References

  * [ABSS97] Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk.  The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations.  Journal of Computer and System Sciences, 54(2):317–331, April 1997\.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  Journal of the ACM (JACM), 45(3):501–555, 1998.
  * [AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  Journal of the ACM (JACM), 45(1):70–122, 1998.
  * [BG14] Mark Braverman and Ankit Garg.  Small value parallel repetition for general games.  Electronic Colloquium on Computational Complexity (ECCC), 21:95, 2014.  To appear in STOC 2015.
  * [BGS98] Mihir Bellare, Oded Goldreich, and Madhu Sudan.  Free bits, PCPs, and nonapproximability—towards tight results.  SIAM Journal on Computing, 27(3):804–915, 1998.
  * [BKM22] Mark Braverman, Subhash Khot, and Dor Minzer.  Parallel Repetition for the GHZ Game: Exponential Decay.  arXiv preprint arXiv:2211.13741, 2022.
  * [BKM23] Amey Bhangale, Subhash Khot, and Dor Minzer.  On Approximability of Satisfiable k-CSPs: II.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 632–642, New York, NY, USA, 2023. Association for Computing Machinery.
  * [BKS15] Amey Bhangale, Swastik Kopparty, and Sushant Sachdeva.  Simultaneous Approximation of Constraint Satisfaction Problems.  In International Colloquium on Automata, Languages, and Programming, pages 193–205. Springer, 2015.
  * [DGKR05] Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev.  A new multilayered PCP and the hardness of hypergraph vertex cover.  SIAM Journal on Computing, 34(5):1129–1146, 2005.
  * [DHVY17] Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen.  Multiplayer Parallel Repetition for Expanding Games.  In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 37:1–37:16, Dagstuhl, Germany, 2017.
  * [DRS02] I Dinur, O Regev, and C Smyth.  The hardness of 3-uniform hypergraph coloring.  In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 33–40. IEEE, 2002.
  * [DS14] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624–633, 2014.
  * [Fei98] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM (JACM), 45(4):634–652, 1998.
  * [FGL+96] Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy.  Interactive proofs and the hardness of approximating cliques.  Journal of the ACM (JACM), 43(2):268–292, 1996.
  * [FK89] Hillel Furstenberg and Yitzhak Katznelson.  A density version of the Hales-Jewett theorem for k= 3.  In Annals of Discrete Mathematics, volume 43, pages 227–241. Elsevier, 1989.
  * [GHM+21] Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan.  Parallel Repetition for the GHZ Game: A Simpler Proof.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 62:1–62:19, Dagstuhl, Germany, 2021.
  * [GHM+22] Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan.  Parallel repetition for all 3-player games over binary alphabet.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 998–1009, 2022.
  * [GHS02] Venkatesan Guruswami, Johan Håstad, and Madhu Sudan.  Hardness of approximate hypergraph coloring.  SIAM Journal on Computing, 31(6):1663–1686, 2002.
  * [GHZ89] Daniel M Greenberger, Michael A Horne, and Anton Zeilinger.  Going beyond Bell’s theorem.  In Bell’s theorem, quantum theory and conceptions of the universe, pages 69–72. Springer, 1989.
  * [GMRZ22] Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan.  Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2022.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM (JACM), 48(4):798–859, 2001.
  * [Hol09] Thomas Holenstein.  Parallel Repetition: Simplification and the No-Signaling Case.  Theory of Computing, 5(1):141–172, 2009.
  * [HR20] Justin Holmgren and Ran Raz.  A parallel repetition theorem for the GHZ game.  arXiv preprint arXiv:2008.05059, 2020.
  * [Kho02a] Subhash Khot.  Hardness results for approximate hypergraph coloring.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 351–359. ACM, 2002.
  * [Kho02b] Subhash Khot.  Hardness results for coloring 3-colorable 3-uniform hypergraphs.  In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 23–32. IEEE, 2002.
  * [MR21] Kunal Mittal and Ran Raz.  Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines.  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [Pol12] DHJ Polymath.  A new proof of the density Hales-Jewett theorem.  Annals of Mathematics, pages 1283–1327, 2012.
  * [Rao11] Anup Rao.  Parallel Repetition in Projection Games and a Concentration Bound.  SIAM J. Comput., 40(6):1871–1891, 2011.
  * [Raz98] Ran Raz.  A Parallel Repetition Theorem.  SIAM Journal on Computing, 27(3):763–803, 1998.
  * [Ver96] Oleg Verbitsky.  Towards the Parallel Repetition Conjecture.  Theor. Comput. Sci., 157(2):277–282, May 1996.

##  Appendix A Proof of Lemma 2.4

Let $G$ be any projection game that is not loosely-connected with
$\mathbf{val}(G)=1-\varepsilon$ for some $\varepsilon>0$. Without loss of
generality, we can assume that there are partitions
$\mathcal{X}_{i}=\mathcal{X}^{\prime}_{i}\cup\mathcal{X}^{\prime\prime}_{i}$
for all $i\in[k]$ such that all the questions from the support of $\mu(G)$ are
from
$\mathcal{X}^{\prime}_{1}\times\mathcal{X}^{\prime}_{2}\times\ldots\times\mathcal{X}^{\prime}_{k}$
or
$\mathcal{X}^{\prime\prime}_{1}\times\mathcal{X}^{\prime\prime}_{2}\times\ldots\times\mathcal{X}^{\prime\prime}_{k}$,
and furthermore, the game restricted to
$\mathcal{X}^{\prime}_{1}\times\mathcal{X}^{\prime}_{2}\times\ldots\times\mathcal{X}^{\prime}_{k}$
(call it $G^{\prime}$) and
$\mathcal{X}^{\prime\prime}_{1}\times\mathcal{X}^{\prime\prime}_{2}\times\ldots\times\mathcal{X}^{\prime\prime}_{k}$
(call it $G^{\prime\prime})$ are loosely-connected individually. The
verifier’s distribution $\mu(G)$ on the question-tuples can be thought of as
$\mu=(1-\delta)\mu^{\prime}+\delta\mu^{\prime\prime}$ where the support of
$\mu^{\prime}$ is from
$\mathcal{X}^{\prime}_{1}\times\mathcal{X}^{\prime}_{2}\times\ldots\times\mathcal{X}^{\prime}_{k}$
and the support of $\mu^{\prime\prime}$ is from
$\mathcal{X}^{\prime\prime}_{1}\times\mathcal{X}^{\prime\prime}_{2}\times\ldots\times\mathcal{X}^{\prime\prime}_{k}$.

Now, since the value of the game $G$ is at most $1-\varepsilon$, we have
$\min\\{\mathbf{val}(G^{\prime}),\mathbf{val}(G^{\prime\prime})\\}\leqslant
1-\varepsilon$. Without loss of generality, suppose we have
$\mathbf{val}(G^{\prime})\leqslant 1-\varepsilon$. Let the value of
$G^{\otimes n}$ be $\eta$. We will show that the value of the game
$G^{\prime\otimes n^{\prime}}$ is also at least $\eta-2^{-\Omega_{\delta}(n)}$
for some $n^{\prime}=\Omega_{\delta}(n)$. This will finish the proof of the
lemma as we have $\mathbf{val}(G^{\prime\otimes
n^{\prime}})\leqslant\exp(-\Omega_{\varepsilon}(n^{\prime}))$ using the fact
that $G^{\prime}$ is a loosely-connected projection game.

Fix a strategy $(\alpha^{1},\alpha^{2},\ldots,\alpha^{k})$ for $G^{\otimes n}$
with value $\eta$. The $k$-tuple questions from $G$ can be alternatively
sampled as follows. First sample a set $T\subseteq[n]$ by adding $i\in T$
independently with probability $(1-\delta)$. Then for each $i\in T$, sample a
$k$-tuple question from the distribution $\mu^{\prime}$ independently.
Similarly, for each $i\notin T$, sample a $k$-tuple question from the
distribution $\mu^{\prime\prime}$ independently. We have,

$\mathop{\mathbf{E}}_{\begin{subarray}{c}T\subseteq_{1-\delta}[n]\\\
(\vec{x}^{1}|_{\overline{T}},\vec{x}^{2}|_{\overline{T}},\ldots,\vec{x}^{k}|_{\overline{T}})\sim\mu^{\prime\prime\otimes|\overline{T}|}\end{subarray}}\mathop{\mathbf{E}}_{(\vec{x}^{1}|_{T},\vec{x}^{2}|_{T},\ldots,\vec{x}^{k}|_{T})\sim\mu^{\prime\otimes|T|}}\left[V((\vec{x}^{1},\vec{x}^{2},\ldots,\vec{x}^{k}),(\alpha^{1}(\vec{x}^{1}),\alpha^{2}(\vec{x}^{2}),\ldots,\alpha^{k}(\vec{x}^{k})))\right]=\eta.$

From this, by the Chernoff Bound and an averaging argument, it follows that
there exists $T\subseteq[n]$ such that $|T|\geqslant(1-\delta)n/2$ and
$(\vec{y}^{1},\vec{y}^{2},\ldots,\vec{y}^{k})\sim\mu^{\prime\prime\otimes|\overline{T}|}$
such that

$\displaystyle\mathop{\mathbf{E}}_{(\vec{x}^{1},\vec{x}^{2},\ldots,\vec{x}^{k})\sim\mu^{\prime\otimes|T|}}\left[V(((\vec{y}^{1},\vec{x}^{1}),(\vec{y}^{2},\vec{x}^{2}),\ldots,(\vec{y}^{k},\vec{x}^{k})),(\alpha^{1}((\vec{y}^{1},\vec{x}^{1})),\alpha^{2}((\vec{y}^{2},\vec{x}^{2})),\alpha^{k}((\vec{y}^{k},\vec{x}^{k}))))\right]$
$\displaystyle\geqslant\eta-2^{-\Omega_{\delta}(n)}.$

Here, the string $(\vec{y},\vec{x})$ is formed by plugging $\vec{y}$ in the
coordinates $\overline{T}$ and $\vec{x}$ in the coordinates $T$. The
distribution on the questions in the expectation above precisely corresponds
to the game $G^{\prime\otimes|T|}$. Thus, the strategy $\alpha^{\prime
i}(\vec{x}):=\alpha^{i}(\vec{y},\vec{x})$ for all $i\in[k]$ gives the value at
least $\eta-2^{-\Omega_{\delta}(n)}$ for the game $G^{\prime\otimes|T|}$.