# What Makes Good Examples for Visual In-Context Learning?

Yuanhan Zhang  Kaiyang Zhou  Ziwei Liu

###### Abstract

Large-scale models trained on broad data have recently become the mainstream
architecture in computer vision due to their strong generalization
performance. In this paper, the main focus is on an emergent ability in large
vision models, known as in-context learning, which allows inference on unseen
tasks by conditioning on in-context examples (a.k.a. prompt) without updating
the model parameters. This concept has been well-known in natural language
processing but has only been studied very recently for large vision models. We
for the first time provide a comprehensive investigation on the impact of in-
context examples in computer vision, and find that the performance is highly
sensitive to the choice of in-context examples. To overcome the problem, we
propose a prompt retrieval framework to automate the selection of in-context
examples. Specifically, we present (1) an unsupervised prompt retrieval method
based on nearest example search using an off-the-shelf model, and (2) a
supervised prompt retrieval method, which trains a neural network to choose
examples that directly maximize in-context learning performance. The results
demonstrate that our methods can bring non-trivial improvements to visual in-
context learning in comparison to the commonly-used random selection. The code
and models are available at https://github.com/ZhangYuanhan-
AI/visual_prompt_retrieval.

Machine Learning, ICML

##  1 Introduction

Figure 1:  (a) Different choices of in-context examples (outlined in green)
often lead to significantly different results. Here we show 30 random query
images (x-axis) from Pascal-$5^{i}$ (Shaban et al., 2017) split 0, and measure
the performance range using 50 different in-context examples. (b) We propose a
prompt retrieval framework aiming to automate the selection of in-context
examples. We provide two implementations of the idea: one is unsupervised
while the other is supervised, both outperforming random selection by a clear
margin.

In recent years, large-scale models have emerged in computer vision: they have
enormous parameter size and are pre-trained on broad data to gain wide-ranging
knowledge. These models have demonstrated remarkable generalization
performance and have great potential for numerous downstream applications
(Bommasani et al., 2021). However, due to the large model size and the
potentially proprietary data used for training, entities able to develop
large-scale models typically only provide users with APIs, known as Model-as-
a-Service (Maas). Representative examples include the prominent text-to-image
generation models, DALL$\cdot$E (Ramesh et al., 2021) and Imagen (Saharia et
al., 2022), and OpenAI’s powerful language models like GPT-3/ChatGPT (Radford
et al., 2021). As a result, users are unable to apply full fine-tuning or some
parameter-efficient tuning techniques, such as prompt learning (Li & Liang,
2021; Lester et al., 2021; Zhou et al., 2022c, b; Zhang et al., 2022; Pan et
al., 2022), for model adaptation, largely limiting downstream performance.

In-context learning, which is a “hidden” capability originally found in large
autoregressive language models (Radford et al., 2021), has recently been
investigated for large vision models (Bar et al., 2022), and more importantly,
has the potential to become the mainstream approach for MaaS applications in
the near future. Without the need to update any parameter for previously
unseen tasks, in-context learning simply prepends some domain-specific input-
output pairs, called in-context examples or prompt,111These two terms are used
interchangeably in this paper. to a test example, which together guide the
model to produce an ideal result. For instance, in natural language processing
one could prepend a French-English sentence pair to a French sentence, and the
model would produce an English translation of the French sentence. In computer
vision, Bar et al. (2022) pre-trained a neural network to fill missing patches
in grid-like images, which allows the model to perform in-context learning for
unseen tasks like image segmentation (see the grid images in Fig. 1(a)
bottom).

In this work, we focus on visual in-context learning, a relatively new concept
with little existing research regarding how to better apply it in practice. We
for the first time conduct a comprehensive investigation on the impact of in-
context examples for large vision models, and identify a critical issue:
downstream performance is highly sensitive to the choice of in-context
examples. This is evidenced by the large variances observed for a variety of
test examples shown in Fig. 1(a) top. By visualizing the results in Fig. 1(a)
bottom, it seems to suggest that the closer the in-context example to the
query, the better the result. For example, the best prompt image is closer to
the query as they are similar in object pose and background; on the other
hand, the worst prompt image has a drastically different style than the query
image, which might explain why the predicted mask focuses on the wrong region,
i.e., the white pillar instead of the cat.

Clearly, designing a proper prompt containing the optimal in-context
example(s) by hand would be extremely difficult. To overcome the problem, we
propose a prompt retrieval framework where the core component is a score
function, which aims to give each source instance a score to indicate the
level of suitability for being included in the prompt. Once the scoring
process is done, we can simply pick one or multiple examples with the highest
score(s) to construct a prompt. An overview of our framework is depicted in
Fig. 1(b).

We provide two implementations for the prompt retrieval framework, both
interpreting the score as the cosine distance measuring similarity between a
query and a source example. The first is an unsupervised method based on
nearest example search using an off-the-shelf model. The second is a
supervised method, which learns a neural network to choose examples that
directly maximize in-context learning performance. Since there is no ground-
truth score to be used as the supervisory signal, we resort to a contrastive
learning paradigm: source examples that result in better (or worse) in-context
learning performance should get closer (or farther) to the query in feature
space.

Our contributions and the main findings are summarized as follows. (1) We
present the first comprehensive study concerning how to select good examples
for the emerging visual in-context learning, and reveal a critical issue that
the choice of in-context examples has a huge impact on performance. (2) From
the technical perspective, we present a prompt retrieval framework that can
automate the prompt selection process, and provide two simple implementations:
an unsupervised method and a supervised method. (3) By conducting extensive
experiments on three visual in-context learning tasks (which have not been
seen during pre-training), namely foreground segmentation, single object
detection and image colorization, we share valuable insights with the
community on how to find good visual in-context examples, e.g., the supervised
method performs the best and often finds examples that are both semantically
close and spatially similar to a query.

##  2 Methods

###  2.1 Visual In-Context Learning

Figure 2: Overview of the supervised prompt retrieval method. The main idea is
to compute the in-context learning result for each source example, and pick
those with the highest/lowest results to form a positive/negative set for
contrastive learning.

In-context learning is a new paradigm that originally emerged from large
autoregressive language models pre-trained on broad data, such as GPT-3 (Brown
et al., 2020). Unlike traditional learning methods, in-context learning does
not require any parameter update and instead conditions prediction on some in-
context examples in the form of input-output pairs. For example, in natural
language processing one might give a French-English sentence pair and a test
French sentence as input to the model, which then produces the English version
of the sentence. In computer vision, such a paradigm has only been studied
very recently. For example, Bar et al. (2022) trained a neural network to fill
missing patches in grid-like images, which in turn allows the model to perform
in-context learning on unseen tasks.

Formally, given a dataset $\mathcal{D}=\\{(x_{n},y_{n})\\}_{n=1}^{N}$
containing $N$ image-label pairs (e.g., an image and its segmentation mask), a
query example $x_{q}$, and a model $g_{\tau}$, in-context learning can be
formulated as:

$y_{q}=g_{\tau}(\mathcal{P},x_{q}),$ (1)

where $\mathcal{P}$ is called a prompt, which consists of $K$ input-output
pairs,
$\mathcal{P}=\\{x_{c_{1}},y_{c_{1}},...,x_{c_{K}},y_{c_{K}}\\}\subset\mathcal{D}$.
In particular, the prompt $\mathcal{P}$ provides some context for guiding the
model to produce the ideal $y_{q}$ for $x_{q}$ without updating the large
model’s parameters $\tau$.

##### Problem.

The most common approach for designing the prompt $\mathcal{P}$ in the vision
domain is (within-class) random selection proposed by Bar et al. (2022): one
or multiple image-label pairs (with the same label as the test example) are
randomly chosen from the training dataset. As illustrated in Fig. 1(a), the
performance is highly sensitive to the selection of in-context examples—the
gap between the best and worst prompt could reach over 70% mIoU. Below we
propose two automatic prompt selection methods to tackle this problem.

###  2.2 Prompt Retrieval

Our goal is to automatically select the most suitable example(s) from the
training dataset for a query $x_{q}$. To this end, we propose a prompt
retrieval framework in the following form,

$x^{*}=\arg\max_{x_{n}\in\mathcal{D}}f_{\theta}(x_{n},x_{q}),$ (2)

where $f_{\theta}$ is a function parameterized by $\theta$, aiming to produce
a score for a pair of $x_{n}$ and $x_{q}$. When $K=1$, we choose the optimal
example pair as the prompt, $\mathcal{P}=\\{x^{*},y^{*}\\}$. When $K>1$, we
rank the training examples by their scores and choose the top-$K$ example
pairs. An overview of our methods is provided in Fig. 1(b).

In this work, we implement $f_{\theta}$ as a combination of a neural network
for feature extraction and the cosine distance function for measuring
similarity between two feature vectors.

####  2.2.1 Unsupervised Prompt Retrieval

Our first method is unsupervised prompt retrieval where the key idea is to use
an off-the-shelf feature extractor for extracting image features so that we
can compare the cosine distance between the query $x_{q}$ and each training
example $x_{n}\in\mathcal{D}$. In this case, the parameters $\theta$ for the
score function $f_{\theta}$ correspond to the off-the-shelf feature extractor,
which are kept fixed.

####  2.2.2 Supervised Prompt Retrieval

The unsupervised method discussed above is not explicitly optimized for in-
context learning; instead, it relies on how the feature extractor was pre-
trained and the objective (function) used in pre-training may well not align
with that of in-context learning. We propose a second method based on
supervised prompt retrieval where we assume the source data contains labels.
The goal is to directly optimize the score function $f_{\theta}$ such that the
chosen in-context example(s) can maximize the log-likelihood,

$\max_{\mathcal{P}}\quad\log p(y_{q}|\mathcal{P},x_{q}).$ (3)

In this work, we present a simple implementation for the supervised method,
which simply turns the unsupervised method into a supervised one by making the
feature extractor learnable. In other words, we directly optimize Eq. 3 with
respect to the feature extractor. Below we explain in detail how we train the
feature extractor (see Fig. 2 for an overview).

##### Data.

Recall that we interpret the score $f_{\theta}(\cdot,\cdot)$ as the cosine
distance between two images in feature space. We would like to learn a space
such that an image pair $(x_{n},x_{q})$ with high in-context learning
performance is close to each other, or far away from each other if the
performance is low. Since there is no label defining how close a distance
should be, we resort to contrastive learning for training the feature
extractor. The goal is then to find a positive and a negative set for each
training example $x_{n}\in\mathcal{D}$ treated as a query. Specifically, for
each example $x_{n}$ we compute the prediction
$\hat{y}_{n}=g_{\tau}((x_{m},y_{m}),x_{n})$ where $g_{\tau}$ is the large
vision model defined in Sec. 2.1 and $x_{m}\in\mathcal{D}$ but $x_{m}\neq
x_{n}$. Since we have the ground truth $y_{n}$ for $x_{n}$, we can measure the
performance by comparing the prediction $\hat{y}_{n}$ with the ground truth
$y_{n}$. Then, for each $x_{n}$ we choose the top-5 examples with the
highest/lowest performance to form a positive/negative set.

##### Training.

Let $z_{n}$ denote the features of $x_{n}$ extracted by the neural network we
aim to optimize. At each iteraction, we sample a mini-batch $\mathcal{B}$ from
the training dataset. Then, for each example in $\mathcal{B}$, we sample one
example from the top-5 positive and negative sets, respectively. The
contrastive loss is computed as

$\ell=-\frac{1}{|\mathcal{B}|}\sum_{x_{n}\sim\mathcal{B}}\log\frac{e^{cos(z_{n},z_{n}^{+})}}{e^{cos(z_{n},z_{n}^{+})}+\sum\limits_{z_{n}^{-}\in\mathcal{N}}e^{cos(z_{n},z_{n}^{-})}},$
(4)

where $cos(\cdot,\cdot)$ is the cosine distance function, $z_{n}^{+}$ denotes
the feature representation of a positive example, and $z_{n}^{-}$ denotes the
feature representation of a negative example. It is worth noting that for
mini-batch training, the negative set $\mathcal{N}$ contains a negative
example of $x_{n}$ sampled from the top-5 negative set and other examples
within the same mini-batch.

##  3 Experiments

In this section we conduct a comprehensive evaluation using different prompt
selection methods (Sec. 3.1) and compare their robustness to distribution
shifts (Sec. 3.2). We also provide extensive quantitative and qualitative
analyses in Sec. 3.3 to help understand why our methods work and how to better
apply them in practice. Source code will be released to the community for
reproducing the full experiments.

##### Methods.

All experiments are based on the image inpainting model pre-trained by Bar et
al. (2022) on a dataset consisting of academic
figures.222https://github.com/amirbar/visual_prompting We mainly compare the
following methods: (1) Random, the baseline method that randomly samples in-
context examples from the source training dataset; (2) Unsupervised prompt
retrieval (UnsupPR), our first proposed method that uses off-the-shelf
features for nearest example search. The main experiments are based on CLIP’s
vision encoder (Radford et al., 2021), which was pre-trained using multimodal
contrastive learning; (3) Supervised prompt retrieval (SupPR), our second
proposed method that fine-tunes CLIP’s vision encoder by directly optimizing
in-context learning performance on downstream datasets. A variety of backbones
are evaluated in Sec. 3.3.

##### Training details for the supervised model.

The supervised model is trained for 200 epochs using SGD. The initial learning
rate is set to 0.005, decayed by the cosine annealing rule.

Table 1:  Main results. The two prompt retrieval methods outperform random selection, and the supervised method achieves the best performance.  |  Seg. (mIoU) $\uparrow$ | Det. (mIoU) $\uparrow$ | Color. (mse) $\downarrow$
---|---|---|---
| Split-0 | Split-1 | Split-2 | Split-3 | Avg
Random | 28.66 | 30.21 | 27.81 | 23.55 | 27.56 | 25.45 | 0.67
UnsupPR | 34.75 | 35.92 | 32.41 | 31.16 | 33.56 | 26.84 | 0.63
SupPR | 37.08 | 38.43 | 34.40 | 32.32 | 35.56 | 28.22 | 0.63

###  3.1 Main Results

##### Setup.

Following Bar et al. (2022), we evaluate our methods on three computer vision
tasks, which have not been seen during the training of the image inpainting
model. We provide the details about the datasets used for these tasks as
follows. (1) Foreground segmentation: We use Pascal-$5^{i}$ (Shaban et al.,
2017), which has four non-overlapping splits each containing five categories.
The results are averaged over all splits. (2) Single object detection: The
experiments are done on Pascal VOC (Everingham et al., 2015). (3)
Colorization: We use ImageNet-2012 (Russakovsky et al., 2015), where the
original validation set containing 50,000 images is used as our test set. The
training data used to learn our supervised prompt retrieval model is created
by randomly sampling 50,000 images from ImageNet’s 1.2M training set. For all
experiments, in-context examples come from the training set.

##### Results.

Table 1 shows the results on the three benchmarks covering foreground
segmentation, single object detection, and colorization. We summarize our
findings as follows. First, prompt retrieval clearly outperforms random
selection. In particular, the improvements of prompt retrieval over random
selection are significant in foreground segmentation and single object
detection: more than 6% on the former and 1% on the latter. However, the gains
on colorization are only marginal (0.63 vs. 0.67), suggesting that the image
inpainting model is probably weak at image colorization. Second, the
supervised prompt retrieval method performs the best. This is not surprising
as the supervised method optimizes in-context learning performance concerning
the prompt selection module. In contrast, the unsupervised method relies more
on the off-the-shelf feature extractor. Overall, the results well justify the
design of the prompt retrieval framework, which can serve as a strong baseline
for future research.

###  3.2 Experiments on Distribution Shifts

Table 2:  Results on distribution shifts (from Pascal to MSCOCO). Despite being a learning-based approach, SupPR shows stronger robustness than UnsupPR and Random, which do not require any training.  |  Seg. (mIoU) $\uparrow$
---|---
| Split-0 | Split-1 | Split-2 | Split-3 | Avg
Random | 12.17 | 18.47 | 20.55 | 15.94 | 16.78
UnsupPR | 12.67 | 19.62 | 21.33 | 18.44 | 18.02
SupPR | 13.62 | 21.25 | 24.46 | 20.44 | 19.95

##### Setup.

Distribution shifts are commonly seen in real-world applications, and
therefore AI models need to be robust to distribution shifts (Zhou et al.,
2022a). To test this ability in visual in-context learning, we create a new
protocol focusing on foreground segmentation where the source dataset is
Pascal while the target dataset is MSCOCO (Lin et al., 2014). Specifically, we
follow the design of Pascal-$5^{i}$ and create MSCOCO-$5^{i}$, which also has
four splits, each having the same set of categories as in the corresponding
split in Pascal-$5^{i}$. Note that such a shift mainly affects the supervised
prompt retrieval method that requires training but not the unsupervised
UnsupPR and Random.

##### Results.

The results are shown in Table 2. First of all, the unsupervised prompt
retrieval method beats the random selection method by a clear margin. By
comparing the two prompt retrieval methods, we find that the supervised method
again performs better than the unsupervised one despite being a learning-based
approach—this is an exciting finding as it means the supervised method does
not have the overfitting problem here. Nonetheless, we observe that the gains
achieved by the prompt retrieval methods here are generally smaller than the
gains achieved on the standard foreground segmentation benchmark: here SupPR
is only around 3% better on average than Random (19.95% vs. 16.78%) while the
improvement in Table 1 reaches 8% (35.56% vs. 27.56%). One potential solution
to reduce the gap might be to improve the image inpainting model, which is
beyond the scope of this paper.

Figure 3: In-context examples retrieved by UnsupPR and SupPR. In each grid, the first row contains the prompt while the second row contains the query and prediction. The in-context examples found by SupPR are more similar than those found by UnsupPR to the queries in a numer of ways: semantics (e.g., (e)), background (e.g., (a)), object pose (e.g., (b), object appearance (e.g., (i)), viewpoint (e.g., (k)), etc. More examples can be found in the supplementary.  Figure 4:  (Left) Impact of the size of retrieval set. (Right) Ablation study on distance metric used to compute the score function in Eq. 2. It can be observed that different metrics perform similarly.  Table 3: Comparison between different backbones pre-trained using different methods: multimodal contrastive learning for CLIP, self-supervised learning for EVA, and supervised learning for ViT. Overall, the performance is insensitive to the choice of different backbones. |  |  Seg. (mIoU) $\uparrow$
---|---|---
|  | Split-0 | Split-1 | Split-2 | Split-3 | Avg
UnsupPR | CLIP | 34.75 | 35.92 | 32.41 | 31.16 | 33.56
EVA | 34.75 | 36.09 | 32.11 | 31.61 | 33.64
ViT | 35.10 | 37.37 | 32.05 | 30.80 | 33.83
SupPR | CLIP | 37.08 | 38.43 | 34.40 | 32.32 | 35.56
EVA | 36.11 | 39.14 | 34.31 | 33.30 | 35.71
ViT | 36.80 | 39.70 | 34.71 | 33.25 | 36.12
Table 4: Impact of the order of in-context examples.  |  Seg. (mIoU) $\uparrow$
---|---
| Split-0 | Split-1 | Split-2 | Split-3 | Avg
Random |  17.93 $\pm$ 0.20 |  25.48 $\pm$ 0.27 |  21.34 $\pm$ 0.73 |  21.12 $\pm$ 0.53 |  21.46 $\pm$ 0.43
UnsupPR |  20.22 $\pm$ 0.31 |  27.58 $\pm$ 0.40 |  22.42 $\pm$ 0.38 |  23.36 $\pm$ 0.42 |  23.39 $\pm$ 0.37
SupPR |  20.74 $\pm$ 0.40 |  28.19 $\pm$ 0.37 |  23.09 $\pm$ 0.34 |  24.22 $\pm$ 0.48 |  24.06 $\pm$ 0.40

###  3.3 Further Analysis

##### What are good in-context examples?

To answer this question, we visualize the in-context examples found by UnsupPR
and SupPR in Fig. 3. We focus on foreground segmentation and choose two
categories from Pascal (person and cow).333The results of the remaining
categories of Pascal and the results on other tasks are provided in the
supplementary. In each grid, the first row corresponds to the retrieved in-
context example (i.e., an input-output pair) while the second row contains the
query and model prediction. By comparing the in-context examples picked by
UnsupPR and those picked by SupPR, we find the reason why SupPR performs
better than UnsupPR: the examples found by SupPR are more similar to the
queries in terms of semantics (e.g., Fig. 3(e)), background (e.g., Fig. 3(a)),
object pose (e.g., Fig. 3(b), object appearance (e.g., Fig. 3(i)), viewpoint
(e.g., Fig. 3(k)), and so on. We also observe similar patterns in other
categories/tasks (please refer to the supplementary).

##### Backbone.

To understand if using a different backbone than CLIP would make a big
difference, we further evaluate our prompt retrieval methods, UnsupPR and
SupPR, on the foreground segmentation benchmark using two other backbones: EVA
(Fang et al., 2022) pre-trained using self-supervised learning (i.e., masked
image modeling) and ViT (Dosovitskiy et al., 2020) pre-trained using
supervised learning. The results are reported in Table 3. Although these three
backbones perform differently on image recognition under the fine-tuning
setting—EVA performed the best—the gap between them for both UnsupPR and SupPR
is less than 1%. Therefore, we can conclude that the backbone for visual in-
context learning does not matter much.

##### Size of retrieval set.

Recall that in-context examples are sampled from the training dataset, namely
the retrieval set. We are interested to know whether the size has any impact
on performance, especially for the supervised prompt retrieval method. To this
end, we build seven subsets for each split in Pascal-$5^{i}$, which cover a
wide range of sizes (see the x-axis in Fig. 4 left). The results are plotted
in Fig. 4 left. For random selection, the size does not matter at all. In
contrast, the two prompt retrieval methods clearly benefit from a bigger size.
But their performance plateaus when the size reaches a certain level. It is
worth noting that for the supervised method, 20% of the total data is
sufficient for achieving a decent performance.

##### Number of in-context examples.

We follow Bar et al. (2022) and create a large grid enough to fit 8 examples
at maximum (as shown in Fig. 5 right). By varying the number of in-context
examples from 1 to 7, we obtain a set of results and plot them in Fig. 5 left.
Clearly, more in-context examples lead to better performance for all three
methods, including SupPR, UnsupPR, and Random. This is probably because in-
context examples can be viewed as “training data”, and having more training
data typically benefits performance—in visual in-context learning, more
training data gives a more comprehensive “context.” We show a few example
cases in Fig. 5 right to explain this observation.

##### Order of in-context examples.

To understand if changing the order of in-context examples makes a difference,
we fix the number of in-context examples to 3, evaluate all possible
combinations, and compute the mean and standard deviation. As shown in Table
4, the standard deviation is generally small, so the order is not a concern as
long as good examples are chosen.

##### Distance metric.

We use the cosine distance by default to compute the score function in Eq. 2.
Here we evaluate other design choices including Euclidean distance and
Manhattan distance. As shown in Fig. 4 right, the results are very similar for
different distance metrics.

Figure 5: (Left) Impact of the number of in-context examples. (Right) More in-
context examples can lead to better performance. The query in each grid is
shown in the bottom right.

##  4 Related Work

###  4.1 In-Context Learning

In-context learning is a novel paradigm that emerged in large language models,
such as GPT-3 (Brown et al., 2020). It allows an autoregressive language model
to perform inference on unseen tasks by conditioning the input on some target-
specific input-output pairs serving as “context.” Such a powerful paradigm
allows users to customize a model’s output according to their downstream
datasets without changing the internal model parameters, which are often
inaccessible. Recent research in natural language processing has shown that
in-context learning can be applied to numerous language tasks, such as machine
translation (Garcia & Firat, 2022), sentiment analysis (Min et al., 2021), and
question answering (Press et al., 2022).

In computer vision, in-context learning is still a relatively new concept. One
of the earliest works tackling in-context learning is Flamingo (Alayrac et
al., 2022), a large visual language model taking language as instruction and
allowing the processing of both images and videos. More relevant to our work
is a pure vision model developed by Bar et al. (2022), which was pre-trained
to fill missing patches in images made of academic figures and infographics.
Bar et al. (2022) found that such an image inpainting model can solve problems
unseen during training, like foreground segmentation and image colorization.

Our work follows Bar et al. (2022) but studies visual in-context learning from
a different dimension: how to find good visual in-context examples that
benefit downstream performance.

###  4.2 Prompt Retrieval in NLP

The natural language processing community has found that the choice of in-
context examples has a huge impact on performance (Agrawal et al., 2022; Liu
et al., 2021). Moreover, the way how in-context examples, also called prompts,
are constructed can also affect performance, e.g., prompt length and the order
of in-context examples, as reported in the literature (Agrawal et al., 2022).
These findings prompted the community to study how to find good in-context
examples for large language models, which has inspired our research.

Liu et al. (2021) assumed that good in-context examples should be semantically
close to query sentences, based on which they proposed to select nearest
neighbors in the training set measured by a sentence encoder like RoBERTa (Liu
et al., 2019). Rubin et al. (2021) first used an unsupervised method to
retrieve some candidates, among which top examples were chosen using a
supervised prompt retriever to maximize downstream performance.

##  5 Discussion and Conclusion

Our research presents a timely study on an emergent ability termed in-context
learning for large vision models. We systematically investigate how the choice
of in-context examples impacts downstream performance, exposing a critical
issue that different in-context examples could lead to drastically different
results. We then propose an effective prompt retrieval framework for visual
in-context learning, with two simple implementations provided: one based on
unsupervised learning and the other based on supervised learning. Our methods
obtain significant improvements over random selection under various problem
settings, showing the potential of using prompt retrieval in vision
applications with a Model-as-a-Service (MaaS) business structure.

Our research also unveils some intriguing phenomena. For instance, we show
that a good in-context example should be semantically similar to the query and
closer in context, e.g., viewpoint, background, and appearance. As such,
state-of-the-art vision models like CLIP would not be sufficient because these
models often emphasize semantics but not other elements critical to finding
good visual in-context examples. A model that can better balance spatial and
semantic closedness in feature space would be more ideal for visual in-context
learning. We hope the insights presented in this work could pave the way for
developing more effective prompt retrieval methods.

Our experiments show that our methods are not strong enough to cope with
distribution shifts. Though our methods outperform random selection under
distribution shifts, the gap is much smaller than that on a standard
benchmark, suggesting huge room for improvement.

## References

  * Agrawal et al. (2022) Agrawal, S., Zhou, C., Lewis, M., Zettlemoyer, L., and Ghazvininejad, M.  In-context examples selection for machine translation.  _arXiv preprint arXiv:2212.02437_ , 2022.
  * Alayrac et al. (2022) Alayrac, J.-B., Donahue, J., Luc, P., Miech, A., Barr, I., Hasson, Y., Lenc, K., Mensch, A., Millican, K., Reynolds, M., et al.  Flamingo: a visual language model for few-shot learning.  _arXiv preprint arXiv:2204.14198_ , 2022.
  * Bar et al. (2022) Bar, A., Gandelsman, Y., Darrell, T., Globerson, A., and Efros, A. A.  Visual prompting via image inpainting.  _arXiv preprint arXiv:2209.00647_ , 2022.
  * Bommasani et al. (2021) Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems (NeurIPS)_ , 33:1877–1901, 2020.
  * Dosovitskiy et al. (2020) Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Everingham et al. (2015) Everingham, M., Eslami, S., Van Gool, L., Williams, C. K., Winn, J., and Zisserman, A.  The pascal visual object classes challenge: A retrospective.  _International journal of computer vision (ICCV)_ , 111(1):98–136, 2015.
  * Fang et al. (2022) Fang, Y., Wang, W., Xie, B., Sun, Q., Wu, L., Wang, X., Huang, T., Wang, X., and Cao, Y.  Eva: Exploring the limits of masked visual representation learning at scale.  _arXiv preprint arXiv:2211.07636_ , 2022.
  * Garcia & Firat (2022) Garcia, X. and Firat, O.  Using natural language prompts for machine translation.  _arXiv preprint arXiv:2202.11822_ , 2022.
  * Lester et al. (2021) Lester, B., Al-Rfou, R., and Constant, N.  The power of scale for parameter-efficient prompt tuning.  _arXiv preprint arXiv:2104.08691_ , 2021.
  * Li & Liang (2021) Li, X. L. and Liang, P.  Prefix-tuning: Optimizing continuous prompts for generation.  _arXiv preprint arXiv:2101.00190_ , 2021.
  * Lin et al. (2014) Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., and Zitnick, C. L.  Microsoft coco: Common objects in context.  In _European conference on computer vision (ECCV)_ , pp. 740–755. Springer, 2014.
  * Liu et al. (2021) Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W.  What makes good in-context examples for gpt-$3$?  _arXiv preprint arXiv:2101.06804_ , 2021.
  * Liu et al. (2019) Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Min et al. (2021) Min, S., Lewis, M., Zettlemoyer, L., and Hajishirzi, H.  Metaicl: Learning to learn in context.  _arXiv preprint arXiv:2110.15943_ , 2021.
  * Pan et al. (2022) Pan, J., Lin, Z., Zhu, X., Shao, J., and Li, H.  St-adapter: Parameter-efficient image-to-video transfer learning for action recognition.  _arXiv preprint arXiv:2206.13559_ , 2022.
  * Press et al. (2022) Press, O., Zhang, M., Min, S., Schmidt, L., Smith, N. A., and Lewis, M.  Measuring and narrowing the compositionality gap in language models.  _arXiv preprint arXiv:2210.03350_ , 2022.
  * Radford et al. (2021) Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning (ICML)_ , pp. 8748–8763. PMLR, 2021.
  * Ramesh et al. (2021) Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M., and Sutskever, I.  Zero-shot text-to-image generation.  In _International Conference on Machine Learning (ICML)_ , pp. 8821–8831. PMLR, 2021.
  * Rubin et al. (2021) Rubin, O., Herzig, J., and Berant, J.  Learning to retrieve prompts for in-context learning.  _arXiv preprint arXiv:2112.08633_ , 2021.
  * Russakovsky et al. (2015) Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3):211–252, 2015.  doi: 10.1007/s11263-015-0816-y.
  * Saharia et al. (2022) Saharia, C., Chan, W., Saxena, S., Li, L., Whang, J., Denton, E., Ghasemipour, S. K. S., Ayan, B. K., Mahdavi, S. S., Lopes, R. G., et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _arXiv preprint arXiv:2205.11487_ , 2022.
  * Shaban et al. (2017) Shaban, A., Bansal, S., Liu, Z., Essa, I., and Boots, B.  One-shot learning for semantic segmentation.  _british machine vision conference (BMVC)_ , 2017.
  * Zhang et al. (2022) Zhang, Y., Zhou, K., and Liu, Z.  Neural prompt search.  _arXiv preprint arXiv:2206.04673_ , 2022.
  * Zhou et al. (2022a) Zhou, K., Liu, Z., Qiao, Y., Xiang, T., and Loy, C. C.  Domain generalization: A survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)_ , 2022a.
  * Zhou et al. (2022b) Zhou, K., Yang, J., Loy, C. C., and Liu, Z.  Conditional prompt learning for vision-language models.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022b.
  * Zhou et al. (2022c) Zhou, K., Yang, J., Loy, C. C., and Liu, Z.  Learning to prompt for vision-language models.  _International Journal of Computer Vision (IJCV)_ , 2022c.

##  Appendix A Illustration of In-context Examples

In the supplementary material, we illustrate more in-context learning results
of foreground segmentation, single object detection, and colorization tasks.

###  A.1 Foreground Segmentation

Figure 6: In-context examples, which are from the foreground segmentation
task, retrieved by UnsupPR and SupPR. These grids show examples from the
train, tv, and bus categories.  Figure 7: In-context examples, which are from
the foreground segmentation task, retrieved by UnsupPR and SupPR. These grids
show examples from the bottle, sheep, and bird categories.  Figure 8: In-
context examples, which are from the foreground segmentation task, retrieved
by UnsupPR and SupPR. These grids show examples from the boat, airplane, and
bicycle categories.  Figure 9: In-context examples, which are from the
foreground segmentation task, retrieved by UnsupPR and SupPR. These grids show
examples from the car, cat, and chair categories.  Figure 10: In-context
examples, which are from the foreground segmentation task, retrieved by
UnsupPR and SupPR. These grids show examples from the dog, horse, and
motorbike categories.  Figure 11: In-context examples, which are from the
foreground segmentation task, retrieved by UnsupPR and SupPR. These grids show
examples from the table, plant, and sofa categories.

The main paper presents the in-context examples from the person and cow
categories. In the supplementary, as shown in Fig. 6-11, we present examples
from the remained 18 categories in Pascal-5i.

###  A.2 Single Object Detection

Figure 12: In-context examples, which are from the single object detection
task, retrieved by UnsupPR and SupPR. We find the examples found by SupPR are
more similar to the queries in terms of object pose (e.g., (f)), viewpoint
(e.g., (r))  Figure 13: In-context examples, which are from the single object
detection task, retrieved by UnsupPR and SupPR. We find the examples found by
SupPR are more similar to the queries in terms of object pose (e.g., (l)),
viewpoint (e.g., (m))

As shown in Fig. 12-13, we illustrate the in-context examples from the single
object detection task. By comparing the in-context examples picked by UnsupPR
and those picked by SupPR, we find the examples found by SupPR are more
similar to the queries in terms of object pose (e.g., Fig. 12(f)), viewpoint
(e.g., Fig. 12(r).

###  A.3 Coloralization

As shown in Fig. 14-15, we illustrate the in-context examples from the
colorization task. This task aims to map a gray-scale image to a color image.
By comparing the in-context examples picked by UnsupPR and those picked by
SupPR, we find the ground truth images of examples found by SupPR are more
similar to that of the queries in terms of image style, e.g. the background
color (e.g., Fig. 14(g)(h)).

Figure 14: In-context examples, which are from the colorization task,
retrieved by UnsupPR and SupPR. We also show the ground truth of the query
image. The query image is the gray-scale version of its ground truth. The
ground truth images of the in-context examples found by SupPR are more similar
than those found by UnsupPR to the ground truth images of queries in terms of
image style, e.g. the background color (g).  Figure 15: In-context examples,
which are from the colorization task, retrieved by UnsupPR and SupPR. We also
show the ground truth of the query image. The query image is the gray-scale
version of its ground truth. The ground truth images of the in-context
examples found by SupPR are more similar than those found by UnsupPR to the
ground truth images of queries in terms of image style, e.g. the background
color (h).


# An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with
Applications to LIS

Jaehyun Koo
MIT
<EMAIL_ADDRESS>
###### Abstract

We present an $O(1)$-round fully-scalable deterministic massively parallel
algorithm for computing the min-plus matrix multiplication of unit-Monge
matrices. We use this to derive a $O(\log n)$-round fully-scalable massively
parallel algorithm for solving the exact longest increasing subsequence (LIS)
problem. For a fully-scalable MPC regime, this result substantially improves
the previously known algorithm of $O(\log^{4}n)$-round complexity, and matches
the best algorithm for computing the $(1+\epsilon)$-approximation of LIS.

##  1 Introduction

The longest increasing subsequence (LIS) problem is a fundamental problem in
computer science. A celebrated $O(n\log n)$ sequential algorithm of Fredman
[Fre75] has been known for decades, and the result is tight in the comparison
model [Ram97]. On the other hand, in the MPC literature, our understanding of
the LIS problem is somewhat limited. Although we’ve recently seen a lot of
advances in this area, all known algorithms still require either
approximations, scalability restrictions, a large number of rounds, or
combinations of them.

One possible approach for this problem is to use the concept of unit-Monge
matrices introduced by Tiskin [Tis07]. Tiskin’s framework has a highly
desirable property of decomposability, where the LIS problem is decomposed
into $O(n)$ multiplication of the unit-Monge matrix, which can be processed in
$O(\log n)$ rounds in the MPC model. For the problem of LIS, Tiskin’s
framework was used to obtain new algorithms in various computing models
[Tis07, KT10b, KT10a, CHS23, KS21], hinting its possible application for the
MPC model as well. We note that Tiskin’s framework was also used in new
algorithms for the longest common subsequence (LCS) problem [Tis07, Rus12,
Tis08], another fundamental problem closely connected to the LIS problem.

In this work, we present an $O(1)$-round fully-scalable MPC algorithm for the
multiplication of unit-Monge matrix. This result implies an $O(\log n)$ round
algorithm to the exact LIS problem in the MPC model, which substantially
improves the previously known algorithm of $O(\log^{4}n)$ round complexity
[CHS23] and matching the best approximation algorithm in the fully-scalable
MPC regime [IMS17]. We hope this result could illustrate the power of the
unit-Monge framework and be a bridge for closing the gap on the LIS problem in
the MPC model.

###  1.1 The MPC Model

The Massively Parallel Computation (MPC) model was first introduced in
[KSV10], and later refined in [BKS17, ANOY14, GSZ11]. Our description of the
model closely follows that of [ANOY14].

In the MPC model, we have $m$ machines with space $s$, where $n$ is the size
of the input, $m=O(n^{\delta})$ and $s=\tilde{O}(n^{1-\delta})$ for a
parameter $\delta$ (here $\tilde{O}$ hides the poly-log factor). The parameter
$\delta$ is generally assumed to be any constant such that $0<\delta<1$. If an
MPC algorithm works for any such $\delta$, it is called fully scalable. All
our results here will be fully-scalable.

In the beginning, the input data is distributed across the machines. Then, the
computation proceeds in rounds. In each round, a machine performs local
computation on its data (of size $s$) and then sends messages to other
machines for the next round. The total amount of communication sent or
received by a machine is bounded by $s$, its space. In the next round, each
machine treats the received messages as the input for the round.

In the MPC model, the primary complexity measure is the number of rounds $R$
required to solve a problem, corresponding to a span in the parallel algorithm
literature.

###  1.2 Previous works

#### Subunit-Monge Matrix Multiplication

The seminal work of Tiskin [Tis07] revealed an intriguing structural fact
about the Subunit-Monge matrix, its application to the LIS and LCS problem,
and an efficient centralized algorithm. Following this work, Krusche and
Tiskin [KT10b] designed a parallel algorithm that achieves an $O(1)$ superstep
subunit-Monge matrix multiplication in a BSP model introduced by Valiant
[Val90]. For a BSP algorithm to be applicable in the standard MPC model, it
should achieve a fully-scalable communication and memory as defined in [KT10a]
(one should not confuse this with the fully-scalable MPC algorithm). Formally,
a BSP algorithm with $p$ machine should achieve $\tilde{O}(\frac{n}{p})$
communication cost and memory cost. Unfortunately, their algorithm requires
$\Omega(\frac{n}{\sqrt{p}})$ memory and communication for $p$ machine, which
makes it not fully scalable and is not applicable for an MPC model.

The following work from Krusche and Tiskin [KT10a] achieves an $O(\log n)$
superstep BSP algorithm with fully scalable communication and memory. While
this work does translate to an MPC algorithm with $O(\log n)$ rounds, their
algorithm has a restriction of $p<n^{1/3}$ as their communication and memory
cost is $\tilde{O}(\frac{n}{p}+p^{2})$ to be precise. Hence, their algorithm
is applicable for an MPC model only in a range of $0<\delta<\frac{1}{3}$, and
also does not achieve a $O(1)$ round complexity.

Recently, Cao, Huang, and Su [CHS23] obtained an algorithm in an EREW PRAM
model with $O(\log^{3}n)$ span. This result also implies an MPC algorithm for
$O(\log^{3}n)$ round complexity. While this is the best algorithm that
satisfies the fully scalable property, we note that the round complexity is
much larger than the optimal algorithm.

#### Longest Increasing Subsequence

Tiskin’s work [Tis07] reveals the connection between the subunit-Monge Matrix
Multiplication and the Longest Increasing Subsequence (LIS) problem. They show
an equivalence relation between the length of LIS and the multiple of $n$
subunit-Monge matrices of total size $O(n)$. Due to this, in most parallel
models, an $S(n)$ round algorithm for subunit-Monge matrix multiplication
implies an $O(S(n)\log n)$ round algorithm for the length of LIS using the
standard divide-and-conquer method. Most of the recent works concerning the
exact computation of LIS in the parallel model use this framework - they start
by obtaining an efficient subunit-Monge matrix multiplication algorithm and
use it to obtain the length of LIS or the actual certificate with a cost of
$O(\log n)$ multiplicative factor on rounds. We note that our algorithm for
subunit-Monge matrix multiplication can be applied in the same way, and the
result from the paper implies an $O(\log n)$ round for the exact computation
of LIS length.

In the approximate regime, the paper from Im, Moseley, Sun [IMS17] showed an
$O(1)$-round algorithm for computing the $(1+\epsilon)$-approximate LIS.
Unfortunately, their approach is not fully scalable: The usage of large DP
tables in the computation restricts the algorithm to only work in the range
$0<\delta\leq\frac{1}{4}$. To date, the best fully-scalable algorithm for
$(1+\epsilon)$-approximate LIS has $O(\log n)$ round complexity [IMS17], which
is matched by our exact LIS algorithm.

#### Longest Common Subsequence

Hunt and Szymanski [HS77] introduced a simple reduction from the LCS problem
to the LIS problem: For two string
$S=\\{s_{1},s_{2},\ldots,s_{n}\\},T=\\{t_{1},t_{2},\ldots,t_{n}\\}$, list all
matching pairs of $(i,j)$ with $s_{i}=t_{j}$ in lexicographical order. In this
sequence, a subsequence of pairs where $j$ is strictly increasing corresponds
to each common subsequence of $S$ and $T$. As long as one can hold all
matching pairs across the machines, the efficient solution to the LIS problem
implies an efficient solution to the LCS problem. For example, [CHS23] implies
an $O(\log^{4}n)$-span parallel algorithm for the LCS problem, given that one
can afford $\tilde{O}(n^{2})$ total work and the space.

For $\tilde{O}(n^{2})$ total space, Apostolico, Atallah, Larmore, and McFaddin
provided an $O(\log^{2}n)$-span CREW PRAM parallel algorithm with $O(n^{2})$
space [AALM90], which also translates to an $O(\log^{2}n)$-round MPC
algorithm. On the other hand, the problem gets significantly more difficult
with more stringent space restrictions. No exact algorithm with $o(n)$-round
is known for subquadratic total space. Moreover, no constant-factor
approximation algorithm with $o(n)$-round is known for the general MPC model
with near-linear total space. We note that the framework of [IMS17] also does
not apply to the LCS problem as it has no decomposability and monotonicity
properties. Recently, there was progress on the MPC algorithms in a model that
allows constant approximation and super-linear total space. [HSS, BS19,
BEG+21]

Reference | Number of Rounds | Scalability | Approximation
---|---|---|---
[KT10a] | $O(\log^{2}n)$ | $\delta<\frac{1}{3}$ | Exact
[IMS17] | $O(\log n)$ | Fully-scalable | $(1+\epsilon)$
[IMS17] | $O(1)$ | $\delta<\frac{1}{4}$ | $(1+\epsilon)$
[CHS23] | $O(\log^{4}n)$ | Fully-scalable | Exact
This paper. | $O(\log n)$ | Fully-scalable | Exact
Table 1:  Summary of known results for massively parallel LIS algorithms.

###  1.3 Our contribution

Our main result is the constant-round algorithm for the unit-Monge
multiplication of two unit-Monge matrices.

######  Theorem 1.1 (Main Theorem).

Given two permutation matrices $P_{A}$, $P_{B}$ represented by the indices of
their nonzero entries, there is a fully-scalable deterministic MPC algorithm
for computing the implicit unit-Monge matrix multiplication
$P_{C}=P_{A}\boxdot P_{B}$ represented as the indices of their nonzero entries
in $O(1)$ rounds.

Note that the (sub-)permutation matrices are the equivalent representation of
(sub)unit-Monge matrices. The exact connection between these two objects will
be made clear in the Preliminaries section.

Following Theorem 1.1, we show how to generalize this result using the
techniques from [Tis07]. The only difference from the Theorem 1.1 is that it
allows subunit-Monge matrices.

######  Theorem 1.2.

Given two sub-permutation matrices $P_{A}$, $P_{B}$ represented by the indices
of their nonzero entries, there is a fully-scalable deterministic MPC
algorithm for computing the implicit subunit-Monge matrix multiplication
$P_{C}=P_{A}\boxdot P_{B}$ represented as the indices of their nonzero entries
in $O(1)$ rounds.

The result of Theorem 1.2 has various implications as many problems can be
represented as a min-plus multiplication of several subunit-Monge matrices.
The first and the most notable result is the following:

######  Theorem 1.3.

Given a sequence of $n$ numbers $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$, there is a
fully-scalable MPC algorithm for computing the length of the LIS of $A$ in
$O(\log n)$ rounds.

Using the observation provided by Hunt and Szymanski [HS77], we can also
derive the following:

######  Corollary 1.3.1.

Given two sequences $A,B$ of $n$ numbers, there is a fully-scalable MPC
algorithm for computing the length of the LCS of $A$ and $B$ in $O(\log n)$
rounds, given that we have $m=n^{1+\delta}$ machines and
$s=\tilde{O}(n^{1-\delta})$ space for any $0<\delta<1$.

In a case where each machine has $O(n)$ memory, the classical dynamic
programming on a single machine suffices. Previously, only
$O(\log^{2}n)$-round algorithms were known in this setting [AALM90]. Note that
Corollary 1.3.1 do not fit in our definition of the MPC model since the total
required space is $\tilde{O}(n^{2})$. On the other hand, as we noted earlier,
no known algorithms use near-linear total space and have $o(n)$ round
complexity, even if we allow constant-factor approximation.

Finally, the structure we used to compute the length of LIS can be used to
solve the generalized version of semi-local LIS and LCS problem [Tis07,
CHS23]. In the semi-local LCS problem, given two strings $S$ and $T$, the
algorithm should compute the LCS between $S$ and every subsegment of $T$,
where a subsegment of $T$ is an array of form $[T_{i},T_{i+1},\ldots,T_{j}]$
for some $1\leq i\leq j\leq|T|$. In the semi-local LIS problem, the algorithm
should compute the LIS for all subsegments of $T$.

######  Corollary 1.3.2.

Given a sequence of $n$ numbers $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$, there is a
fully-scalable MPC algorithm for computing the semi-local LIS of $A$ in
$O(\log n)$ rounds.

######  Corollary 1.3.3.

Given two sequences $A,B$ of $n$ numbers, there is a fully-scalable MPC
algorithm for computing the semi-local LCS of $A$ and $B$ in $O(\log n)$
rounds, given that we have $m=n^{1+\delta}$ machines and
$s=\tilde{O}(n^{1-\delta})$ space for any $0<\delta<1$.

###  1.4 Technical Overview

Warmup: An $O(\log n)$-round algorithm for unit-Monge matrix multiplication.
In the Section 3.1 of [CHS23], they identified the following core problem:
Given two permutation $P_{1},P_{2}$ of size $n$, we define $f(i)$ to be the
smallest integer $k$ such that $\sum_{j<i}\mathbb{I}[P_{1}[j]<k]>\sum_{j\geq
i}\mathbb{I}[P_{2}[j]\geq k]$. The problem is to find all $f(i)$ for $0\leq
i\leq n$, and [CHS23] provides an $O(\log^{2}n)$-span divide-and-conquer
algorithm to do this, which implies an $O(\log^{3}n)$-span algorithm for
subunit-Monge matrix multiplication. Indeed, we provide an $O(1)$-round MPC
algorithm to compute $f(i)$, which implies an $O(\log n)$-round algorithm for
subunit-Monge matrix multiplication.

First, let’s start from an $O(\log n)$-round algorithm to compute the $f(i)$.
Using binary search, we can reduce the problem into the computation of
$\sum_{j<i}\mathbb{I}[P_{1}[j]<f(i)]-\sum_{j\geq i}\mathbb{I}[P_{2}[j]\geq
f(i)]$ in $O(1)$ rounds.

To compute this, we construct a binary tree over $P_{1}$ and $P_{2}$, where
each node contains a sorted list of all leaves in the subtree. Intuitively,
this can be considered as a memoization of merge sort procedure on each
sequence, where each node takes a sorted sequence of two child nodes and
merges them as in the merge sort algorithm. This tree can be constructed in
$O(\log n)$ rounds as sorting takes $O(1)$ rounds (Lemma 2.5). As our problem
can be described as counting a value in a range that is smaller than the
threshold, we can compute the desired quantity by identifying $O(\log n)$
relevant nodes and doing a rank search in parallel (Lemma 2.6). Hence, each
binary search takes $O(1)$ rounds.

To optimize this procedure, we need to optimize the tree structure
construction and the binary search. First, we flatten the tree in a way such
that each non-leaf node has $H=n^{(1-\delta)/10}$ child instead of two. Since
the tree now has a depth of $O(1)$, the construction of the tree takes $O(1)$
rounds.

Next, rather than eliminating binary search, we adapt the search to take
advantage of this new tree structure. Let’s build a tree over the inverse
permutation $P_{1}^{-1},P_{2}^{-1}$ instead of the original permutation: This
effectively creates a transposed version of the tree where for each element
$P_{1}[i]$, the index is $P_{1}[i]$, and the corresponding value is $i$ (and
respectively for $P_{2}$). We will maintain two pointers, one for the tree
over $P_{1}^{-1}$ and another for $P_{2}^{-1}$, and descend to one of $H$
child by counting the value less (or greater than $j$) and descending toward
the leftmost child that satisfies the predicate.

This procedure ultimately yields $O(1)$ rounds for each query, but there is a
catch - in each round, we are doing $O(n^{1+(1-\delta)/10})$ binary searches,
which exceeds our memory capacity. Hence, we have to limit our query locations
to indices that are a multiple of $G=n^{1-\delta}$.

Given that we found an $O(1)$-round algorithm on finding $f(iG)$ for all
$0\leq i\leq\frac{n}{G}$, we need to use this information to compute all
$f(i)$. The function $f(i)$ is monotonically decreasing, and what we’ve found
could be visualized as an intercept of axis-parallel polyline formed by
$(i,f(i))$ and $\frac{n}{G}+1$ axis-parallel lines $x=0,G,2G,\ldots,n$. By
taking a transpose of the permutation $P_{1},P_{2}$, we can also compute the
same intercepts for lines $y=0,G,2G,\ldots,n$. These lines form
$(\frac{n}{G})^{2}$ boxes of size $G\times G$ \- As our polyline is monotone,
there are at most $\frac{n}{G}$ boxes that our polylines intersect. Inside
these boxes, we can compute the inner route of the polylines with $O(G)$-sized
information, which is enough for each machine to compute in a single round.

Shaving off the $O(\log n)$-factor. The above algorithm essentially combines
two subproblems in $O(1)$ rounds, which is the reason for its $O(\log n)$
round complexity. Our strategy is simple - we will combine
$H=n^{(1-\delta)/10}$ subproblems in $O(1)$ rounds, which will solve the
entire problem in $O(1)$ round complexity. This is our main technical
obstacle.

The actual meaning of the core problem in [CHS23] is that it computes the
demarcation line between the cells that takes its optimum from the first
subproblem and the second subproblem: A cell $(x,y)$ in the result matrix will
take its value from the first subproblem if $y<f(x)$, and the other if $y\geq
f(x)$. For $poly(n)$ subproblems, we prove a similar argument: There exist
$q-1$ monotone demarcation lines, where the $i$-th line divides the matrix
into the parts where it takes its value from the first $i$ subproblems or the
last $q-i$ subproblems. In Section 3.1, we describe several definitions and
useful lemmas to use this monotonicity property.

Intuitively, these demarcation lines look easy to compute since we can compare
the $i$-th subproblem and the $i+1$-th subproblem. However, this approach is
incorrect. Consider two cells $(x,y)$ and $(x,y+1)$, where the first cell
takes its optimum from the $2$-nd subproblem and the second cell takes its
optimum from the $6$-th subproblem. While it seems that for all $2\leq i\leq
5$, the $i$-th subproblem should be better for $(x,y)$ compared to $i+1$-th
and vice versa, it is not necessarily true, and indeed, all except one can be
false. To solve this issue, we instead take the demarcating polyline for all
pairs of subproblems using a procedure similar to the Warmup algorithm. Then,
for each axis-parallel grid line where its $x$-coordinate (or $y$-coordinate)
is a multiple of $G$, we compute the intercept solely based on the
abovementioned information. We describe these procedures in detail on Section
3.2.

Now, the final piece is to compute the inner route of the polylines using
these intercepts. In the Warmup section, a straightforward way based on the
definition yields a total of $O(n)$ memory usage. However, since the number of
polylines is large, directly applying this algorithm requires
$O(n^{1+(1-\delta)/10})$ total memory. In Section 3.3, we use several clever
observations to reduce the total memory requirements from
$O(n^{1+(1-\delta)/10})$ to $O(n)$.

##  2 Preliminaries

###  2.1 Notations

We follow the notations used in the prior work [CHS23]. For integers $i$ and
$j$, we use $[i:j]$ to denote set $\\{i,i+1,\ldots,j\\}$ and $[i:j)$ to denote
set $\\{i,i+1,\ldots,j-1\\}$. The set $[1:i]$ is represented short as $[i]$.
We denote the half-integer set
$\\{i+\frac{1}{2},i+\frac{3}{2},\ldots,j-\frac{1}{2}\\}$ by $\langle
i:j\rangle$. For brevity, we may denote $[1:i]$ as $[i]$, and $\langle
0:i\rangle$ as $\langle i\rangle$. For an integer variable $i$, the
corresponding half-integer variables are denoted by $\hat{i}$, and they have a
value of $i+\frac{1}{2}$. Some matrices in this paper are indexed using half-
integers. For a set $X$ and $Y$, we denote their Cartesian product as $X\times
Y$.

Given a matrix $M$ of size $m\times n$ which is indexed by half-integers of
range $\langle 0:i\rangle\times\langle 0:j\rangle$, its distribution matrix
$M^{\Sigma}$ is defined as

$\displaystyle M^{\Sigma}(i,j)=\sum_{(\hat{i},\hat{j})\in\langle
i:m\rangle\times\langle 0:j\rangle}M(\hat{i},\hat{j})$

for all $i\in[0:m]$ and $j\in[0:n]$.

A $n\times n$ matrix $P$ is a sub-permutation matrix if and only if

  * •

Each element in $P$ is either $0$ or $1$.

  * •

There is at most one element equal to $1$ in each row and each column of $P$.

Similarly, a $n\times n$ matrix $P$ is a permutation matrix if and only if

  * •

Each element in $P$ is either $0$ or $1$.

  * •

There is exactly one element equal to $1$ in each row and each column of $P$.

In our algorithm, we represent them as an array of size $n$, where each index
$i$ represents the index of the column of the nonzero element in row $\hat{i}$
when the row $\hat{i}$ is nonzero.

The distribution matrix $P^{\Sigma}$ of a (sub-)permutation matrix $P$ is
called a (sub)unit-Monge matrix. Given two (sub-)permutation matrices
$P_{A},P_{B}$, the implicit (sub)unit-Monge matrix multiplication problem is
to find a (sub-)permutation matrix $P_{C}$ that satisfies
$P_{C}^{\Sigma}(i,k)=\min_{j}(P_{A}^{\Sigma}(i,j)+P_{B}^{\Sigma}(j,k))$, or a
$(\text{min},+)$-product of (sub)unit-Monge matrix $P_{A}^{\Sigma}$ and
$P_{B}^{\Sigma}$. Tiskin [Tis07] proved the following:

######  Lemma 2.1.

For any permutation matrix $P_{A},P_{B}$, there exists a permutation matrix
$P_{C}$ such that
$P_{C}^{\Sigma}(i,k)=\min_{j}(P_{A}^{\Sigma}(i,j)+P_{B}^{\Sigma}(j,k))$.

######  Lemma 2.2.

For any sub-permutation matrix $P_{A},P_{B}$, there exists a sub-permutation
matrix $P_{C}$ such that
$P_{C}^{\Sigma}(i,k)=\min_{j}(P_{A}^{\Sigma}(i,j)+P_{B}^{\Sigma}(j,k))$

Since a distribution matrix uniquely defines a sub-permutation matrix, $P_{C}$
is unique. We use $\boxdot$ to represent the implicit subunit-Monge matrix
multiplication. In other words, we denote such $P_{C}$ as $P_{C}=P_{A}\boxdot
P_{B}$.

###  2.2 Basic tools

In this section, we list some basic tools which we will repeatedly invoke in
the following sections.

######  Lemma 2.3 (Inverse Permutation).

Given a permutation $p:[n]\rightarrow[n]$, we can compute the inverse
permutation $p^{-1}$ in $O(1)$ rounds.

###### Proof.

Each machine does the following: For all permutation elements it contains,
send the pair $(i,p_{i})$ to the machine responsible for the $p_{i}$-th
element. ∎

We use the results from [GSZ11] in the following lemmas.

######  Lemma 2.4 (Prefix Sums).

Given $n$ numbers, there is a deterministic algorithm to compute a prefix sum
of the numbers. [GSZ11]

######  Lemma 2.5 (Sorting).

Given $n$ numbers, there is a deterministic algorithm to sort them in $O(1)$
rounds. [GSZ11]

In this paper, we define the offline rank searching on array as the following:
Given an array of numbers $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ and queries
$Q=\\{q_{1},q_{2},\ldots,q_{k}\\}$, we should compute the length-$k$ array
$R=\\{r_{1},r_{2},\ldots,r_{k}\\}$ where $r_{i}$ is equal to the number of
elements in $A$ which is smaller than $q_{i}$. Using the lemmas above, we can
solve the offline rank-searching problem in $O(1)$ rounds.

######  Lemma 2.6 (Offline Rank Searching).

Given $n$ numbers and $k$ query points, there is a deterministic algorithm to
solve the offline rank searching problem in $O(1)$ rounds.

###### Proof.

Duplicate all numbers and query points and sort them in a nondecreasing order
of values. If two elements have the same value, ties are broken so that the
query point precedes the number. By Lemma 2.5 this takes $O(1)$ rounds. Now,
when we consider each number as a point of value $1$ and queries as a point of
value $0$, the answer $r_{i}$ corresponds to a prefix sum of such values in a
given query point. Computing a prefix sum can be done in $O(1)$ rounds by
Lemma 2.4. ∎

##  3 Proof of the Main Theorem

In this section, we prove the following main theorem:

See 1.1

###  3.1 Preliminaries

Let $G=n^{(1-\delta)}$ and $H=n^{(1-\delta)/10}$. We will split $P_{A}$ into
$H$ matrices of size $n\times\frac{n}{H}$ in parallel to columns, and $P_{B}$
into $H=n^{(1-\delta)/10}$ matrices of size $\frac{n}{H}\times n$ in parallel
to rows. We assume $n\geq G=H^{10}$ as we can do all computations locally
otherwise. We also assume $n$ to be the multiple of $H$, but this condition is
unnecessary and only serves to simplify the explanation. We will denote the
splitted matrices of $P_{A}$ as $P_{A,1},P_{A,2},\ldots,P_{A,H}$ from left-to-
right order, and $P_{B}$ as $P_{B,1},P_{B,2},\ldots,P_{B,H}$ from top-to-
bottom order. Let $P_{C,i}=P_{A,i}\boxdot P_{B,i}$ for all $i\in[H]$. For all
$i\in[H]$ $P_{C,i}$ is a $n\times n$ matrix.

We need to remove the empty rows of $P_{A,i}$ and columns of $P_{B,i}$ to make
them compact enough for recursion, which we will denote as $P^{\prime}_{A,i}$
and $P^{\prime}_{B,i}$. For this, we sort the nonzero row index of each
submatrix $P_{A,i}$ and relabel the row accordingly by the rank of their index
in the sorted indices. Both requires $O(1)$ round by Lemma 2.3 and Lemma 2.5.
After the procedure, we can create a mapping $M_{A}:\langle
n\rangle\rightarrow[H]\times\langle\frac{n}{H}\rangle$ that takes the row
index $\hat{i}$ of $P_{A}$ and returns the pair
$M_{A}(\hat{i})=(M_{A}(\hat{i})_{sub},M_{A}(\hat{i})_{idx})$, which indicates
that the $\hat{i}$-th row is in $M_{A}(\hat{i})_{sub}$-th subproblem and is
indexed as $M_{A}(\hat{i})_{idx}$-th row there. We also define the inverse of
such mapping $M_{A}^{-1}=[H]\times\langle\frac{n}{H}\rangle\rightarrow\langle
n\rangle$. We proceed identically for the columns of $P_{B}$, creating a
mapping $M_{B}:\langle n\rangle\rightarrow[H]\times\langle\frac{n}{H}\rangle$
and the inverse
$M_{B}^{-1}=[H]\times\langle\frac{n}{H}\rangle\rightarrow\langle n\rangle$.

As each $P^{\prime}_{A,i}$ and $P^{\prime}_{B,i}$ are of size
$\frac{n}{H}\times\frac{n}{H}$, we can recursively compute
$P^{\prime}_{C,i}=P^{\prime}_{A,i}\boxdot P^{\prime}_{B,i}$ for each
$i\in[H]$. By the method we constructed, we can derive a relation between
$P_{C,i}$ and $P^{\prime}_{C,i}$ as
$P_{C,i}(\hat{x},\hat{y})=P^{\prime}_{C,i}(M_{A}(\hat{x})_{idx},M_{B}(\hat{y})_{idx})$
for $\hat{x},\hat{y}$ with $M_{A}(\hat{x})_{sub}=M_{B}(\hat{y})_{sub}=i$, and
$0$ otherwise.

Given the result of subproblem $P_{C,i}$ and the mapping
$M_{A},M_{A}^{-1},M_{B},M_{B}^{-1}$, we need to combine them to the whole
subproblem. Ideally, we want a formula representing $P_{C}$ only using the
$P_{C,i}$. We show that this is possible.

######  Lemma 3.1.

For all $0\leq i,k\leq n,1\leq q\leq H$, it holds that

$\displaystyle\min_{0\leq
j\leq\frac{n}{H}}(P_{A}^{\Sigma}(i,(q-1)\frac{n}{H}+j)+P_{B}^{\Sigma}((q-1)\frac{n}{H}+j,k))$
$\displaystyle=\sum_{1\leq x\leq
q-1}P_{C,x}^{\Sigma}(i,n)+P^{\Sigma}_{C,q}(i,k)+\sum_{q+1\leq x\leq
H}P_{C,x}^{\Sigma}(0,k)$

###### Proof.

From the definition, we obtain

$\min_{0\leq
j\leq\frac{n}{H}}(P_{A}^{\Sigma}(i,(q-1)\frac{n}{H}+j)+P_{B}^{\Sigma}((q-1)\frac{n}{H}+j,k))\\\
=\sum_{1\leq x\leq q-1}P_{A,x}^{\Sigma}(i,\frac{n}{H})+\min_{0\leq
j\leq\frac{n}{H}}(P_{A,q}^{\Sigma}(i,j)+P_{B,q}^{\Sigma}(j,k))\\\
+\sum_{q+1\leq x\leq H}P_{B,x}^{\Sigma}(0,k)$

We show that $P_{A,x}^{\Sigma}(i,\frac{n}{H})=P_{C,x}^{\Sigma}(i,n)$ for all
$x\in[H]$. If we expand the term by definition, we have

$\displaystyle P^{\Sigma}_{C,x}(i,n)=\min_{0\leq j\leq
n/H}(P^{\Sigma}_{A,x}(i,j)+P^{\Sigma}_{B,x}(j,n))$

Since the rows of $P_{B,x}$ sums to $1$, we have
$P^{\Sigma}_{B,x}(j,n)=\frac{n}{H}-j$. On the other hand, we have
$P^{\Sigma}_{A,x}(i,j+1)-P^{\Sigma}_{A,x}(i,j)\leq 1$. Thus the RHS is
monotonically decreasing over $j$, and the minimum is attained in
$j=\frac{n}{H}$. The part $P_{B,x}^{\Sigma}(0,k)=P_{C,x}^{\Sigma}(0,k)$ can be
proved in an identical way. $P_{C,q}(i,k)=\min_{0\leq j\leq
n/H}(P_{A,q}(i,j)+P_{B,q}(j,k))$ follows from the definition
$P_{C,q}=P_{A,q}\boxdot P_{B,q}$. ∎

######  Lemma 3.2.

For $1\leq q\leq H$ and $0\leq i,j\leq n$, let $F_{q}(i,j)$ be

$\displaystyle F_{q}(i,j)=\sum_{1\leq x\leq
q-1}P_{C,x}^{\Sigma}(i,n)+P^{\Sigma}_{C,q}(i,j)+\sum_{q+1\leq x\leq
H}P_{C,x}^{\Sigma}(0,j)$

For all $0\leq i,j\leq n$, it holds that $P_{C}^{\Sigma}(i,j)=\min_{1\leq
q\leq H}F_{q}(i,j)$.

###### Proof.

Follows from Lemma 3.1 ∎

Lemma 3.2 shows that we can simply take a pointwise minimum of $F_{q}(i,j)$ to
obtain a distribution matrix. Using such an approach directly requires a lot
of space for each machine. Instead, let’s define $opt(i,j)$ be the minimum
integer in $[q]$ such that $F_{opt(i,j)}(i,j)=\min_{1\leq q\leq H}F_{q}(i,j)$.
We will show that $opt(i,j)$ is monotonic on $i$ and $j$ and derive several
nice properties that simplify its computation and representation. Then, we
will show that we don’t need the value $F_{q}(i,j)$, and the monotonic table
$opt(i,j)$ is enough to produce the resulting permutation matrix $P_{C}$.

For $1\leq q<r\leq H$ and $0\leq i,j\leq n$, let
$\delta_{q,r}(i,j)=F_{q}(i,j)-F_{r}(i,j)$, which in a more explicit form:

$\displaystyle\delta_{q,r}(i,j)=P^{\Sigma}_{C,q}(i,j)+\sum_{q+1\leq x\leq
r}P_{C,x}^{\Sigma}(0,j)-\sum_{q\leq x\leq
r-1}P_{C,x}^{\Sigma}(i,n)-P^{\Sigma}_{C,r}(i,j)$

We will prove two lemmas related to the monotonicity of $\delta_{q,r}$.

######  Lemma 3.3.

For all $1\leq q<r\leq H$ and $0\leq i\leq n,0\leq j\leq n-1$, we have
$0\leq\delta_{q,r}(i,j+1)-\delta_{q,r}(i,j)\leq 1$.

###### Proof.

We have

$\displaystyle\delta_{q,r}(i,j+1)-\delta_{q,r}(i,j)=(P^{\Sigma}_{C,q}(i,j+1)-P^{\Sigma}_{C,q}(i,j))$
$\displaystyle+\sum_{q+1\leq x\leq
r}(P_{C,x}^{\Sigma}(0,j+1)-P_{C,x}^{\Sigma}(0,j))$
$\displaystyle-(P^{\Sigma}_{C,r}(i,j+1)-P^{\Sigma}_{C,r}(i,j))$

The value of RHS only depends on the point in the column $\hat{j}$. We divide
the cases by $M_{B}(\hat{j})_{sub}$:

  * •

if $M_{B}(\hat{j})_{sub}<q$, the RHS is $0$.

  * •

if $M_{B}(\hat{j})_{sub}=q$, the RHS is $1$ if the corresponding point has a
row index of at least $i$ and $0$ otherwise.

  * •

if $q<M_{B}(\hat{j})_{sub}<r$, the RHS is $1$.

  * •

if $M_{B}(\hat{j})_{sub}=r$, the RHS is $1$ if the corresponding point has a
row index of at most $i$ and $0$ otherwise.

  * •

if $r<M_{B}(\hat{j})_{sub}$, the RHS is $0$.

Hence, for all cases, it is either $0$ or $1$. ∎

######  Lemma 3.4.

For all $1\leq q<r\leq H$ and $0\leq i\leq n-1,0\leq j\leq n$, we have
$0\leq\delta_{q,r}(i+1,j)-\delta_{q,r}(i,j)\leq 1$.

###### Proof.

We have

$\displaystyle\delta_{q,r}(i+1,j)-\delta_{q,r}(i,j)=-(P^{\Sigma}_{C,q}(i,j)-P^{\Sigma}_{C,q}(i+1,j))$
$\displaystyle+\sum_{q\leq x\leq
r-1}(P_{C,x}^{\Sigma}(i,n)-P_{C,x}^{\Sigma}(i+1,n))$
$\displaystyle+(P^{\Sigma}_{C,r}(i,j)-P^{\Sigma}_{C,r}(i+1,j))$

The value of RHS only depends on the point in the row $\hat{i}$. We divide the
cases by $M_{A}(\hat{i})_{sub}$:

  * •

if $M_{A}(\hat{i})_{sub}<q$, the RHS is $0$.

  * •

if $M_{A}(\hat{i})_{sub}=q$, the RHS is $1$ if the corresponding point has a
column index of at least $j$ and $0$ otherwise.

  * •

if $q<M_{A}(\hat{i})_{sub}<r$, the RHS is $1$.

  * •

if $M_{A}(\hat{i})_{sub}=r$, the RHS is $1$ if the corresponding point has a
column index of at most $j$ and $0$ otherwise.

  * •

if $r<M_{A}(\hat{i})_{sub}$, the RHS is $0$.

Hence, for all cases, it is either $0$ or $1$. ∎

From Lemma 3.3 and Lemma 3.4, we can observe that $\delta_{q,r}(i,j)$ is an
increasing function over $i$ and $j$. Hence, two areas with
$\delta_{q,r}(i,j)<0$ and $\delta_{q,r}(i,j)\geq 0$ are divided by a monotone
chain that starts from $(n,0)$ and ends at $(0,n)$ while moving in an upper-
right direction.

We can derive the following from Lemma 3.3 and Lemma 3.4.

######  Lemma 3.5.

For all $0\leq i\leq n-1,0\leq j\leq n$, we have $opt(i,j)\leq opt(i+1,j)$.

###### Proof.

Suppose $opt(i,j)>opt(i,j+1)$. Let $k_{1}=opt(i,j+1),k_{2}=opt(i,j)$, we have
$\delta_{k_{1},k_{2}}(i,j+1)\leq 0$ and $\delta_{k_{1},k_{2}}(i,j)>0$, which
contradicts Lemma 3.3. ∎

######  Lemma 3.6.

For all $0\leq i\leq n,0\leq j\leq n-1$, we have $opt(i,j)\leq opt(i,j+1)$.

###### Proof.

Apply the proof of Lemma 3.5, this time using Lemma 3.4 instead. ∎

To give the complete characterization of points with
$P_{C}(\hat{i},\hat{j})=1$ by only using the table of $opt$, we derive several
lemmas.

######  Lemma 3.7.

For all $0\leq i,j\leq n-1$, if $opt(i,j)\neq opt(i,j+1)$ and
$P_{C,q}(\hat{i},\hat{j})=0$ for all $q$, it holds that
$P_{C}(\hat{i},\hat{j})=0$.

###### Proof.

Let $a=opt(i,j),b=opt(i,j+1),c=opt(i+1,j),d=opt(i+1,j+1)$. By Lemma 3.5 and
Lemma 3.6, we have $a<b,a\leq c,c\leq d,b\leq d$.

We first prove $F_{b}(i,j+1)=F_{d}(i,j+1)$. If $b=d$, this is evident. Suppose
that $b\neq d$. Since $b<d$, we have that $\delta_{b,d}(i,j+1)\leq 0$ and
$\delta_{b,d}(i+1,j+1)>0$. By Lemma 3.4, the only possible choice of value is
$\delta_{b,d}(i,j+1)=0,\delta_{b,d}(i+1,j+1)=1$. This means that
$F_{b}(i,j+1)=F_{d}(i,j+1)$. With the same procedure, this time using Lemma
3.3, we can also prove $F_{c}(i+1,j)=F_{d}(i+1,j)$ as well.

Now we prove $F_{a}(i,j)=F_{d}(i,j)$. Since $a<b$, we have that
$\delta_{a,b}(i,j)\leq 0$ and $\delta_{a,b}(i,j+1)>0$. By Lemma 3.3, the only
possible choice of value is $\delta_{a,b}(i,j)=0,\delta_{a,b}(i,j+1)=1$. Since
$F_{b}(i,j+1)=F_{d}(i,j+1)$, we have $\delta_{a,d}(i,j+1)=1$. By Lemma 3.3,
$\delta_{a,d}(i,j)\geq 0$, and we can’t have $\delta_{a,d}(i,j)>0$ as that
will make $a$ not a minimum. Hence we have $\delta_{a,b}(i,j)=0$ and
$F_{a}(i,j)=F_{d}(i,j)$. Summing this up, we have:

$\displaystyle P_{C}^{\Sigma}(i,j)=F_{d}(i,j)$ $\displaystyle
P_{C}^{\Sigma}(i,j+1)=F_{d}(i,j+1)$ $\displaystyle
P_{C}^{\Sigma}(i+1,j)=F_{d}(i+1,j)$ $\displaystyle
P_{C}^{\Sigma}(i+1,j+1)=F_{d}(i+1,j+1)$

By Lemma 3.2, we have $P_{C}(\hat{i},\hat{j})=P_{C,d}(\hat{i},\hat{j})$, and
since the RHS is $0$, the LHS is $0$ as well. ∎

######  Lemma 3.8.

For all $0\leq i,j\leq n-1$, if $opt(i,j)\neq opt(i+1,j)$ and
$P_{C,q}(\hat{i},\hat{j})=0$ for all $q$, it holds that
$P_{C}(\hat{i},\hat{j})=0$.

###### Proof.

Proceed as in Lemma 3.2. ∎

######  Lemma 3.9.

For all $0\leq i,j\leq n-1$, if $opt(i,j)=opt(i+1,j),opt(i,j)=opt(i,j+1)$ and
$opt(i,j)\neq opt(i+1,j+1)$, it holds that $P_{C}(\hat{i},\hat{j})=1$.

###### Proof.

Let $a=opt(i,j)=opt(i+1,j)=opt(i,j+1)$ and $b=opt(i+1,j+1)$. By Lemma 3.3, we
have $a<b$. By the statement we have that $\delta_{a,b}(i+1,j)\leq 0$ and
$\delta_{a,b}(i+1,j+1)>0$. By Lemma 3.3, the only possible choice of value is
$\delta_{a,b}(i+1,j)=0,\delta_{a,b}(i+1,j+1)=1$. Hence, we have:

$\displaystyle P_{C}^{\Sigma}(i,j)=F_{a}(i,j)$ $\displaystyle
P_{C}^{\Sigma}(i,j+1)=F_{a}(i,j+1)$ $\displaystyle
P_{C}^{\Sigma}(i+1,j)=F_{a}(i+1,j)$ $\displaystyle
P_{C}^{\Sigma}(i+1,j+1)=F_{a}(i+1,j+1)+1$

By Lemma 3.2, we have $P_{C}(\hat{i},\hat{j})=P_{C,a}(\hat{i},\hat{j})+1$.
Since $P_{C,a}(\hat{i},\hat{j})$ is either $0$ or $1$, this leaves the only
option of $P_{C}(\hat{i},\hat{j})=1$.

∎

######  Lemma 3.10.

For all $0\leq i,j\leq n-1$, if $opt(i,j)=opt(i+1,j)$, $opt(i,j)=opt(i,j+1)$,
$opt(i,j)=opt(i+1,j+1)$, then $P_{C}(\hat{i},\hat{j})=1$ holds if and only if
$P_{C,opt(i,j)}(\hat{i},\hat{j})=1$.

###### Proof.

Let $a=opt(i,j)$, we have:

$\displaystyle P_{C}^{\Sigma}(i,j)=F_{a}(i,j)$ $\displaystyle
P_{C}^{\Sigma}(i,j+1)=F_{a}(i,j+1)$ $\displaystyle
P_{C}^{\Sigma}(i+1,j)=F_{a}(i+1,j)$ $\displaystyle
P_{C}^{\Sigma}(i+1,j+1)=F_{a}(i+1,j+1)$

Hence by Lemma 3.2, we have $P_{C}(\hat{i},\hat{j})=P_{C,a}(\hat{i},\hat{j})$.
∎

Lemma 3.7, 3.8, 3.9, 3.10 gives a sufficient characterization for all points
with $P_{C}(\hat{i},\hat{j})=1$. Except the points added in the procedure of
Lemma 3.9, for all points in $P_{C}(\hat{i},\hat{j})=1$ there exists a point
in some $q$ where $P_{C,q}(\hat{i},\hat{j})=1$. Hence, the algorithm can start
by simply taking all points characterized by Lemma 3.9 and then fill the
remaining points from the permutation matrix $\sum_{q=1}^{H}P(C,q)$.

###  3.2 Computing the $opt(i,j)$ for selected lines

For the first $n^{\delta}+1$ machines indexed as $j=0,1,\ldots,n^{\delta}$, we
will devise an algorithm that computes $opt(*,jG)$ in each machines. As the
tables can be large, they won’t be stored explicitly but rather as a set of
$H$ intervals where the $k$-th interval denotes the set of $i$ with
$opt(i,jG)=k$.

To this end, for each $1\leq q<r\leq H$, we will try to find the first $i$
where $\delta_{q,r}(i,jG)>0$. Let $cmp(jG,q,r)$ be such $i$ ($n+1$ if there is
no such $i$). If we compute all such $O(H^{2})$ values, we can determine the
$opt(i,jG)$ for all possible $j$ alongside the possible location where this
minimum might change. By directly trying all possibilities, we can compute the
desired intervals, and since $H^{2}\leq G$, this does not violate the space
condition.

Let $p$ be a permutation on $\langle n\rangle$ created by taking a union of
all points in each $P_{C,i}$. In other words, for all $i,\hat{x},\hat{y}$,
$P_{C,i}(\hat{x},\hat{y})=1$, then $p(\hat{x})=\hat{y}$. Additionally, to
record the origin of each point, we say $p(\hat{x})$ is of color $i$ if
$P_{C,i}(\hat{x},\hat{y})=1$.

We will construct a $H$-ary tree structure $T$, where each node at the $i$-th
level represents $H^{i}$ consecutive element in the permutation $p_{i}$. For
example, each nodes at $0$-th level represents one element, such as
$\\{p(\hat{0})\\},\\{p(\hat{1})\\}$ and so on. In the $1$-th level, each nodes
represent $\\{p(\hat{0}),p(\hat{1}),\ldots,p(\hat{H}-1)\\}$,
$\\{p(\hat{H}),p(\hat{H}+1),\ldots,p(\hat{2H}-1)\\}$ and so on. This tree has
a height of $\frac{1}{1-\frac{\delta}{10}}=O(1)$. We denote $h(T)$ to be the
height of the tree, hence $h(T)=\frac{1}{1-\frac{\delta}{10}}$. If two nodes
in an adjacent level share an element, the node in the lower level is the
child of the higher level. We say some child is left or right to the other
child if it points to an interval with lower or higher indices.

For each node $v$ of $T$, we associate it to $H$ arrays where the $i$-th array
$arr(v,i)$ contains all elements of node $v$ with color $i$, sorted in the
increasing order of $p_{i}$. $T$ can be constructed in $O(1)$ round. First, we
create the leaf nodes. Then, the construction proceeds in phases. We do the
following in the $i$-th phase ($1\leq i\leq h(T)$):

  * •

Each node at $i-1$-th level clones itself.

  * •

Each node $v$ at $i$-th level collects all cloned information from the
$i-1$-th level. It identifies each $arr(w,i)$ for all children $w$ of $v$ and
sorts them all together to create $arr(v,i)$, which can be done in $O(1)$
round by Lemma 2.5.

For the space usage, we need to analyze two parts: The size of the node itself
and the total length of arrays associated with each node. For the second part,
note that the sum of size of $arr(v,i)$ is $n$ for all $0\leq i\leq h(T)$.
Hence, the size of the arrays fits the near-linear space usage. For the first
part, the total space usage is super-linear as each node contains $H$ pointers
toward the arrays, and we have $O(n)$ nodes. To this end, we implicitly
represent the lower $10$ levels without constructing a tree since each
$H^{10}=G$ element consisting of the level-$10$ nodes of the tree can fit in a
single machine. We do not create an actual tree for these single machines, and
we process all the potential queries solely based on the information over the
$H^{10}$ elements it contains.

After constructing the tree $T$, we will search the value $cmp(jG,q,r)$ by
descending the tree $T$ in parallel. Specifically, the algorithm operates in
$h(T)$ phases. Let $V(jG,q,r)$ be the current node of $T$, where we know that
$cmp(jG,q,r)$ is in the interval that node represents. At each phase,
$V(jG,q,r)$ descends to one of the children while satisfying one invariant:
Let $\langle l:r\rangle$ be the range of index the node is representing, then
$V(jG,q,r)$ is the rightmost node with $\delta_{q,r}(l,jG)\leq 0$ among all
nodes of same level. Note that this invariant holds at the beginning of the
phases because $\delta_{q,r}(0,j)\leq 0$ for all choices of $q<r$, $j$.
Additionally, we also store the value $\delta_{q,r}(l,jG)$ for each search of
$(jG,q,r)$.

Recall the following formula for $\delta_{q,r}(i,j)$:

$\displaystyle\delta_{q,r}(i,j)=P^{\Sigma}_{C,q}(i,j)+\sum_{q+1\leq x\leq
r}P_{C,x}^{\Sigma}(0,j)$ $\displaystyle-\sum_{q\leq x\leq
r-1}P_{C,x}^{\Sigma}(i,n)-P^{\Sigma}_{C,r}(i,j)$

To simulate one phase, we do the following. For each search $(jG,q,r)$, let’s
say its child represents the index $\langle p_{0}:p_{1}\rangle,\langle
p_{1}:p_{2}\rangle,\ldots,\langle p_{H-1}:p_{H}\rangle$. To find the rightmost
child while adhering to invariant, it suffices to compute
$\delta_{q,r}(p_{i+1},jG)-\delta_{q,r}(p_{i},jG)$ for all $0\leq i\leq H-1$.
Hence, for each query of $cmp(jG,q,r)$, we try to retrieve the following
package of information:

  * •

For all childs $w$ of $V(jG,q,r)$ and each color $d\in[H]$, the number of
elements in $arr(w,d)$. This corresponds to the term
$P^{\Sigma}_{C,d}(p_{i+1},n)-P^{\Sigma}_{C,d}(p_{i},n)$.

  * •

For all childs $w$ of $V(jG,q,r)$ and each color $d\in[H]$, the number of
elements in $arr(w,d)$ with value at most $jG$. This corresponds to the term
$P^{\Sigma}_{C,d}(p_{i+1},jG)-P^{\Sigma}_{C,d}(p_{i},jG)$.

Each package is of size $O(H^{2})$, and we need $O(H^{2})$ search to retrieve
each package. As there are $H^{2}$ candidates of $q,r$, we need to process
$\frac{nH^{4}}{G}$ total rank search queries for retrieving this information.
As $\frac{nH^{4}}{G}$ is sublinear, all queries fit the total space, and we
can apply Lemma 2.6 to compute all packages in $O(1)$ rounds. From the
packages, we can compute $\delta_{q,r}(p_{i},j)$ for all $0\leq i\leq H$. If
$\delta_{q,r}(p_{H},j)\leq 0$, we say $cmp(jG,q,r)=p_{H}+1$ and the search is
done. Otherwise, we take the maximum $i$ with $\delta_{q,r}(p_{i},j)\leq 0$
and descend the $(i+1)$-th child from the left. Since all
$\delta_{q,r}(p_{i},j)$ are known, the value $\delta_{q,r}(l,j)$ can be
appropriately updated.

After $h(T)$ phases of such iteration, all searches are either finished or
$V(jG,q,r)$ points to a leaf node. If a leaf node represents $p(\hat{i})$,
then we can state that $cmp(jG,q,r)=i+1$.

Finally, we need a small technical detail to proceed to the later stage of the
algorithm. For all $i$ where $opt(i,jG)\neq opt(i+1,jG)$, we compute, for each
$opt(i,jG)\leq k\leq opt(i+1,jG)$, the value $\delta_{k,k+1}(i,jG)$. To
compute this, note that the interval $\langle i,n\rangle$ can be decomposed
into at most $B\times h(T)$ disjoint intervals where each interval corresponds
to a node in a tree. We can find these intervals (set of nodes) by descending
the tree $T$ in $h(T)=O(1)$ rounds. Then, we can use Lemma 2.6 to retrieve the
values from these nodes in $O(1)$ rounds. The reason for computing this
information will be soon evident in Section 3.3.

This concludes the descriptions of the computation of $opt(*,jG)$ for all $j$
in $O(1)$ round.

We take a transpose of $P_{C}$ by taking an inverse permutation as in Lemma
2.3 and also compute all $opt(iG,*)$ for all $i$ in $O(1)$ rounds.

###  3.3 Computing the remaining $opt(i,j)$ locally

Before proceeding to this step, we present some definitions. For each $1\leq
q\leq H-1$, we define a demarcation line $q$ as the line demarcating the area
with $opt(i,j)\leq q$ and $opt(i,j)>q$. Due to Lemma 3.3, 3.4, each
demarcation line is a monotone chain connecting the lower-left and upper-right
areas. We visualize the demarcation line as a polyline connecting the half-
integer points $(\hat{i},\hat{j})$. Specifically, a point $(\hat{i},\hat{j})$
is pierced by demarcation line $q$ if the demarcation line passes through
$(\hat{i},\hat{j})$. This happens, if not all of
$[opt(i,j),opt(i+1,j),opt(i,j+1),opt(i+1,j+1)]$ are at most $q$, or at least
$q+1$. In this sense, a demarcation line $q$ connects each adjacent pierced
point. A subgrid $(i,j)$ contains all cells in $\langle
iG,(i+1)G\rangle\times\langle jG,(j+1)G\rangle$. A point $(\hat{i},\hat{j})$
is interesting if $opt(i,j)=opt(i+1,j)$, $opt(i,j)=opt(i,j+1)$, $opt(i,j)\neq
opt(i+1,j+1)$. Recall that from Lemma 3.7, 3.8, 3.9, 3.10, it suffices to find
and mark all interesting points.

Our first observation is that there are at most $O(\frac{nH}{G})$ subgrids of
interest:

######  Lemma 3.11.

There exists at most $O(\frac{nH}{G})$ subgrid which contains at least one
interesting point.

###### Proof.

Each demarcation line intersects at most $\frac{2n}{G}$ subgrids, as each
movement either increases the column number or decreases the row number.
Hence, at most $\frac{2nH}{G}$ subgrids are intersected by at least one
demarcation line. If any demarcation line does not intersect a subgrid, every
point in the subgrid shares the same $opt(i,j)$ value. Hence, there are no
interesting points. ∎

Now, we demonstrate the algorithm for the subgrid $(i,j)$, which contains at
least one interesting point. We will compute all $opt(r,c)$ in increasing
order of rows and decreasing order of columns. As an invariant, we maintain
the following information before computing the $opt(r,c)$ for some
$iG<r\leq(i+1)G,jG\leq c<(j+1)G$. Let $chain(r,c)$ be the ordered sequence of
cells
$\\{(r-1,jG),(r-1,jG+1),\ldots,(r-1,c),(r-1,c+1),(r,c+1),(r,c+2),\ldots,(r,(j+1)G),(r+1,(j+1)G),\ldots,((i+1)G,(j+1)G)\\}$.
We have

  * •

The value $opt(r^{\prime},c^{\prime})$ for each $(r^{\prime},c^{\prime})\in
chain(r,c)$. Note that all points in $chain(r,c)$ are in nondecreasing order
of rows and columns, and the value $opt(r^{\prime},c^{\prime})$ are also
nondecreasing.

  * •

Suppose that for two adjacent cell $(r_{1},c_{1})$ and $(r_{2},c_{2})$ in
$chain(r,c)$ has $opt(r_{1},c_{1})\neq opt(r_{2},c_{2})$. For all
$opt(r_{1},c_{1})\leq k<opt(r_{2},c_{2})$, we store
$\delta_{k,k+1}(r_{1},c_{1})$.

We will refer to this information as invariant information.

We will compute the value $opt(r,c)$. Since we have $opt(r-1,c)\leq
opt(r,c)\leq opt(r,c+1)$, if $opt(r-1,c)=opt(r,c+1)$, we can say
$opt(r,c)=opt(r-1,c)$, and it is straightforward to maintain the invariants as
well. Suppose $opt(r-1,c)<opt(r,c+1)$. We need to know, for each
$opt(r-1,c)\leq k<opt(r,c+1)$, the value of $\delta_{k,k+1}(r,c)$. Here, since
$\delta_{p,q}(r,c)=\sum_{i=p}^{q-1}\delta_{i,i+1}(r,c)$, this information is
enough to determine the best subproblem. By the invariant, we either know
$\delta_{k,k+1}(r-1,c)$ or $\delta_{k,k+1}(r-1,c+1)$, and we want to transform
them into $\delta_{k,k+1}(r,c)$.

The proof of Lemma 3.3, 3.4 reveals the necessary information required to
obtain $\delta_{p,q}(i,j+1)-\delta_{p,q}(i,j)$ and
$\delta_{p,q}(i+1,j)-\delta_{p,q}(i,j)$. From these, we can conclude that the
additional information other than invariant required to acquire
$\delta_{k,k+1}(r,c)$ is:

  * •

Whether the point in row $\hat{r}-1$ is of color range
$[opt(r-1,c),opt(r,c+1)]$, and if it is, the color and column index of such
point.

  * •

Whether the point in column $\hat{c}$ is of color range
$[opt(r-1,c),opt(r,c+1)]$, and if it is, the color and row index of such
point.

We will refer to this information as non-invariant information.

Given the non-invariant information, we can determine the value
$\delta_{k,k+1}(r,c)$ and $opt(r,c)$ in turn. Then we use the value
$\delta_{k,k+1}(r,c)$ or $\delta_{k,k+1}(r-1,c)$ to maintain the invariant,
which is enough. Note that, when determining $opt(r,c)$, we also have the
information $opt(r-1,c),opt(r-1,c+1),opt(r,c+1)$ as well, so we can also mark
all interesting points as well.

This concludes the description of the algorithm for computing all interesting
points. Now, let’s check whether we can supply all information within our
space restrictions and construct an algorithm that does it.

We will define subgrid instance as a set of invariant / non-variant
information necessary to determine all interesting points. From Lemma 3.11, we
have at most $O(\frac{nH}{G})$ subgrid instances to prepare.

To prepare the invariant information, we can use the results of Section 3.2,
which is of size $O(H)$ for each subgrid instance.

One naive way to prepare the non-invariant information is to add all points in
row $r\in\langle iG:(i+1)G\rangle$ and column $c\in\langle jG:(j+1)G\rangle$
to the subgrid instances, but this is of $O(G)$ size for each subgrid
instances which does not sum to near-linear total size. However, we present a
simple variation of this naive method that can yield a near-linear total
space.

For each demarcating line $q$ and the subgrid it intersects, let
$(\hat{r_{1}},\hat{c_{1}})$ be the lower-leftmost pierced point and
$(\hat{r_{2}},\hat{c_{2}})$ be the upper-rightmost pierced point. Then, for
all points in row $\langle r_{1}:(r_{2}+1)\rangle$ with color $q$ or $q+1$, we
add such points to that subgrid instance. Similarly, for all points in column
$\langle c_{2}:(c_{1}+1)\rangle$ with color $q$ or $q+1$, we add such points
to that subgrid instance. The following lemma asserts that this procedure had
added at most $O(n)$ points in total:

######  Lemma 3.12.

The above procedure adds one point into at most $4$ subgrid instances.

###### Proof.

Suppose we add a point with color $c$ into some subgrid instances. The
demarcating line should either have an index $c-1$ or $c$. For a demarcating
line to add a point, the row/column interval induced by two extreme pierced
points should contain the point. Since each demarcating line is monotone, only
two cases exist (one row, one column) in which the interval can contain a
point. ∎

We show that the subgrid instance populated by the above procedure has all
non-invariant information. If $opt(r-1,c)<opt(r,c+1)$, then for all
$opt(r-1,c)\leq k<opt(r,c+1)$, the demarcating line $k$ pierces the point
$(\hat{r}-1,\hat{c})$. If a demarcating line $k$ pierces the point
$(\hat{r}-1,\hat{c})$, and the point in the row $\hat{r}-1$ or column
$\hat{c}$ has a color $k$ or $k+1$, then it is added to the subgrid instance.
As a result, if the point in row $\hat{r}-1$ is of color range
$[opt(r-1,c),opt(r,c+1)]$, the demarcating line adds such point to the subgrid
instance. The same goes for the column $\hat{c}$.

Now, we will present the actual algorithm. We first compute the size of each
subgrid instance by tracing the demarcation lines in parallel. Given the size
of each subgrid instance, we can sort them in the order of decreasing sizes
and use greedy packing to assign the respective machines. We then retrace each
demarcation line to populate the subgrid instance with non-invariant
information. We also populate them with the invariant information as well.
Finally, each machine solves the subgrid instance independently and reports
all interesting points to complete the permutation $P_{C}$.

##  4 Applications

###  4.1 Extension to the sub-permutation case

In this section, we prove Theorem 1.2 from Theorem 1.1. The following proof is
inspired by Tiskin’s proof [Tis07] on proving that all subunit-Monge matrices
are closed under $\boxdot$ operation.

See 1.2

###### Proof.

For any row $i$ in $P_{A}$, which is zero, we can see that the row $i$ of
$P_{A}\times P_{B}$ is also zero. Hence, we can delete this row and recover it
from the resulting $P_{C}$ outputted by Theorem 1.1. Likewise, for any column
$j$ in $P_{B}$, which is zero, the column $j$ of $P_{A}\times P_{B}$ is also
zero. Hence, using sorting in $O(1)$ rounds (Lemma 2.5), one can assume that
all rows of $P_{A}$ and all columns of $P_{B}$ are nonzero. Let
$n_{1},n_{2},n_{3}$ be an integer such that $P_{A}$ is an $n_{1}\times n_{2}$
matrix, and $P_{B}$ is an $n_{2}\times n_{3}$ matrix. We can see that
$n_{1}\leq n_{2},n_{2}\geq n_{3}$.

We will extend matrix $P_{A}$ and $P_{B}$ to a square $n_{2}\times n_{2}$
matrix by appending $n_{2}-n_{1}$ rows in the front of $P_{A}$, and
$n_{3}-n_{1}$ columns in the back of $P_{B}$. In other words, we have

$\displaystyle P^{\prime}_{A}=\begin{bmatrix}*\\\
P_{A}\end{bmatrix},P^{\prime}_{B}=\begin{bmatrix}P_{B}&*\end{bmatrix},$

Then we can see, as long as $P_{A}^{\prime}$ and $P_{B}^{\prime}$ remains as a
permutation matrix, the content of $*$ are irrelevent, and we can recover
$P_{C}$ by the following:

$\displaystyle\begin{bmatrix}*&*\\\ P_{C}&*\end{bmatrix}=\begin{bmatrix}*\\\
P_{A}\end{bmatrix}\times\begin{bmatrix}P_{B}&*\end{bmatrix}$

We have to add rows appropriately to make $P_{A}$ a permutation matrix. For
this end, do the following: Initialize a length $n_{2}$ arrays $A$ filled with
$1$ and mark all nonzero columns with $0$. Then, we shift the existing columns
by $n_{2}-n_{1}$, and for each element with $A[i]=1$, we add $\sum_{j\leq
i}A[j]$-th row where the column $i$ is marked. As we can compute the prefix
sum in $O(1)$ round [GSZ11], this procedure takes $O(1)$ round. The case of
$P_{B}$ is just a transpose of the above procedure.

As a result, we can convert the $P_{A}$ and $P_{B}$ into a permutation matrix
$P^{\prime}_{A},P^{\prime}_{B}$ in $O(1)$ rounds. By Theorem 1.1, their
multiplication takes $O(1)$ rounds. After the multiplication, we can simply
ignore the upper $n_{2}-n_{1}$ and right $n_{3}-n_{1}$ columns to obtain
$P_{C}$ in $O(1)$ rounds. ∎

###  4.2 Proof of Theorem 1.3

In this section, we prove Theorem 1.3 using Theorem 1.2. Note that this is a
rather typical step for the LIS algorithm that uses the unit-Monge matrix
multiplication, and Section 4 of [CHS23] already well explains how this is
done. In this paper, we delegate most of the explanation to [CHS23] and will
only visit MPC-specific details.

###### Proof.

We proceed identically as the proof of Theorem 1.2 in [CHS23], with only the
following difference: After the splitting of $A$ into two halves
$A=A_{lo}\circ A_{hi}$, we can relabel $A_{lo}$ and $A_{hi}$ in $O(1)$ rounds,
since the sorting and inverse permutation can be computed in $O(1)$ rounds due
to Lemma 2.3, 2.5. ∎

##  5 Discussion

This paper presents an $O(1)$-round fully-scalable MPC algorithm for computing
the subunit-Monge matrix multiplication. This result implies a $O(\log
n)$-round fully-scalable MPC algorithm for computing the exact length of the
longest increasing subsequences. Our results are deterministic, and improves
all currently known algorithms of [IMS17, CHS23], only except the $O(1)$-round
algorithm of [IMS17] which is approximate and is not fully-scalable.

One important question to address in future work is whether we can apply a
similar approach to obtain an $O(1)$-round algorithm for the longest
increasing subsequences. Since the crux of our work is to devise an algorithm
for merging $poly(n)$ subproblems instead of two subproblems, it is natural to
wonder if we can multiply $poly(n)$ matrices at once instead of two. Indeed,
such an algorithm will likely yield an $O(1)$-round algorithm. However, our
method of multiplying two matrices (at least so far as we understand the
problem) requires divide-and-conquer with heavy technical details. We do not
see or expect a solution that would make this work for a polynomial number of
matrices. Rather, we believe there should be an $\Omega(\log n)$ conditional
hardness result for the exact LIS problem, of which we currently do not have
proof. Finding a very efficient $O(1)$-round algorithm or proving that such
does not exist under popular conjectures will be an interesting challenge.

## References

  * [AALM90] Alberto Apostolico, Mikhail J. Atallah, Lawrence L. Larmore, and Scott McFaddin.  Efficient parallel algorithms for string editing and related problems.  SIAM Journal on Computing, 19(5):968–988, 1990.
  * [ANOY14] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev.  Parallel algorithms for geometric graph problems.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 574–583, New York, NY, USA, 2014. Association for Computing Machinery.
  * [BEG+21] Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi, and Saeed Seddighin.  Approximating edit distance in truly subquadratic time: Quantum and mapreduce.  J. ACM, 68(3), may 2021.
  * [BKS17] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  J. ACM, 64(6), oct 2017.
  * [BS19] Mahdi Boroujeni and Saeed Seddighin.  Improved mpc algorithms for edit distance and ulam distance.  In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’19, page 31–40, New York, NY, USA, 2019. Association for Computing Machinery.
  * [CHS23] Nairen Cao, Shang-En Huang, and Hsin-Hao Su.  Nearly optimal parallel algorithms for longest increasing subsequence.  In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 249–259, New York, NY, USA, 2023. Association for Computing Machinery.
  * [Fre75] Michael L. Fredman.  On computing the length of longest increasing subsequences.  Discrete Mathematics, 11(1):29–35, 1975.
  * [GSZ11] Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang.  Sorting, searching, and simulation in the mapreduce framework.  In Proceedings of the 22nd International Conference on Algorithms and Computation, ISAAC’11, page 374–383, Berlin, Heidelberg, 2011. Springer-Verlag.
  * [HS77] James W. Hunt and Thomas G. Szymanski.  A fast algorithm for computing longest common subsequences.  Commun. ACM, 20(5):350–353, may 1977.
  * [HSS] MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun.  Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence, pages 1654–1672.
  * [IMS17] Sungjin Im, Benjamin Moseley, and Xiaorui Sun.  Efficient massively parallel methods for dynamic programming.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 798–811, New York, NY, USA, 2017. Association for Computing Machinery.
  * [KS21] Tomasz Kociumaka and Saeed Seddighin.  Improved dynamic algorithms for longest increasing subsequence.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 640–653, New York, NY, USA, 2021. Association for Computing Machinery.
  * [KSV10] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for mapreduce.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, page 938–948, USA, 2010. Society for Industrial and Applied Mathematics.
  * [KT10a] Peter Krusche and Alexander Tiskin.  New algorithms for efficient parallel string comparison.  In Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’10, page 209–216, New York, NY, USA, 2010. Association for Computing Machinery.
  * [KT10b] Peter Krusche and Alexander Tiskin.  Parallel longest increasing subsequences in scalable time and memory.  In Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, and Jerzy Wasniewski, editors, Parallel Processing and Applied Mathematics, pages 176–185, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [Ram97] Prakash V. Ramanan.  Tight $\omega$(n lg n) lower bound for finding a longest increasing subsequence.  Int. J. Comput. Math., 65:161–164, 1997.
  * [Rus12] Luís M.S. Russo.  Monge properties of sequence alignment.  Theoretical Computer Science, 423:30–49, 2012.
  * [Tis07] Alexander Tiskin.  Semi-local string comparison: Algorithmic techniques and applications.  Mathematics in Computer Science, 1:571–603, 2007.
  * [Tis08] Alexander Tiskin.  Semi-local longest common subsequences in subquadratic time.  Journal of Discrete Algorithms, 6(4):570–581, 2008.  Selected papers from the 1st Algorithms and Complexity in Durham Workshop (ACiD 2005).
  * [Val90] Leslie G. Valiant.  A bridging model for parallel computation.  Commun. ACM, 33(8):103–111, aug 1990.