# mRobust04: A Multilingual Version of the TREC Robust 2004 Benchmark

Vitor Jeronymo, Mauricio Nascimento, Roberto Lotufo and Rodrigo Nogueira
NeuralMind, Brazil
FEEC, UNICAMP, Brazil

###### Abstract

Robust 2004 is an information retrieval benchmark whose large number of
judgments per query make it a reliable evaluation dataset. In this paper, we
present mRobust04, a multilingual version of Robust04 that was translated to 8
languages using Google Translate. We also provide results of three different
multilingual retrievers on this dataset. The dataset is available at
https://huggingface.co/datasets/unicamp-dl/mrobust

##  1 Introduction

A key ingredient in the development of information retrieval algorithms are
reusable evaluation datasets [7, 19, 20]. For English, there are a number of
such datasets. For other languages, there are initiatives such TREC CLIR [17],
CLEF [13, 4, 5, 6], FIRE [12, 11], NTCIR [16] and more recently HC4 [9]. A
common problem with these multilingual IR datasets is their low number of
judgments per query, that is, the number of documents marked as relevant or
not relevant per query. For example, in the multilingual datasets mMARCO [3]
and Mr.Tydi [21], there is only one or two documents manually marked as
relevant per query. These "sparse" annotations, we argue, prevent correct
evaluations of retrieval methods. For example, the RM3 query expansion method
evaluated on the MS MARCO benchmark [1], which uses sparse annotations, shows
no improvement over baselines such as BM25 [10]. However, the same method
shows significant improvements over BM25 when evaluated on densely annotated
benchmarks, such as TREC-DL.

In this work, to mitigate the issue with sparse annotations on multilingual IR
datasets, we translate the TREC’s Robust 2004 benchmark [18], an English
dataset with a high number of judgments, to 8 languages using a high-quality
automatic translator. We call this dataset mRobust04.

In Table 1 we compare mRobust04 with other multilingual IR datasets. Despite
having a modest number of queries and documents, mRobust04 has much more
annotations per query, which, we conjecture, makes it a reliable benchmark for
evaluating future multilingual retrieval models. We also evaluate on this
dataset two multilingual models that are close to the state of the art.

##  2 Translation Methodology

Robust04 is an English news dataset whose documents are in a single file,
divided by <DOC> tags. Regular expressions were used to delimit and extract
relevant text from each document within the file, and BeautifulSoup was used
to clean any HTML tags that may have remained.

After that, we fed Robust04’s queries and corpus to the Google Translate API
to translate to the following languages: Chinese, French, German, Indonesian,
Italian, Portuguese, Russian and Spanish. Some documents had more characters
than the maximum allowed by the API, so we used the nltk’s [2] sentence
tokenizer to split them into chunks of acceptable sizes and send them
independently to the API. The resulting translations of these chunks were then
concatenated to form the translated document. The annotated query-document
pairs are the same for all languages.

Dataset | MT | Langs | Queries | Docs | J/q
---|---|---|---|---|---
Mr. Tydi | No | 11 | 2k-16k | 136k-32M | 1.03
mMARCO | Yes | 14 | 540k | 8.8M | 1.06
CLEF 2001-2003 | No | 5 | 50-60 | 87k-454k | 27.93
HC4 | No | 3 | 54-60 | 486k-4.7M | 54.36
TREC-8 CLIR | No | 4 | 28 | 62k-242k | 206.75
mRobust04 (ours) | Yes | 9 | 249 | 528k | 1250.60
Table 1: Comparison of mRobust04 with other multilingual IR datasets. “MT”
refers to whether the dataset was machine translated or not. J/q is the
average number of judgments per query per language.

##  3 Evaluation

We evaluate a sparse model (BM25), a dense model (mColBERT) and a reranker
(mT5) on mRobust04. We use mT5 and mColBERT finetuned on mMARCO as provided by
Bonifacio et al. [3] and evaluate them on mRobust04 in a zero-shot manner.

Inference in each language was performed by creating windows of sentences,
with Spacy[8], of maximum 10 and stride of 5 for both mT5 and mColBERT, since
their maximum tokenized length is lower than most documents in the corpus. The
sparse first-stage retrieval, BM25, is not limited by a maximum length;
therefore, the corpus was indexed without any windowing.

We report nDCG@20 and R@1000. In preliminary experiments, we observed that mT5
and mColBERT have 6% and 20% fewer judged documents on average in their top 20
compared to BM25. Therefore we also report nDCG’ (i.e., nDCG “prime”) [15],
which does not penalize the model for retrieving unjudged query-document
pairs.

| en | fr | pt | it | id | ru | es | de | zh | avg
---|---|---|---|---|---|---|---|---|---|---
nDCG@20
BM25 | 0.389 | 0.389 | 0.389 | 0.387 | 0.383 | 0.372 | 0.364 | 0.333 | 0.289 | 0.367
mT5 | 0.466 | 0.376 | 0.391 | 0.384 | 0.374 | 0.372 | 0.402 | 0.375 | 0.358 | 0.389
mColBERT | 0.362 | 0.302 | 0.323 | 0.305 | 0.287 | 0.265 | 0.309 | 0.280 | 0.262 | 0.300
nDCG’@20
BM25 | 0.394 | 0.418 | 0.409 | 0.411 | 0.407 | 0.403 | 0.394 | 0.372 | 0.349 | 0.396
mT5 | 0.486 | 0.429 | 0.439 | 0.436 | 0.432 | 0.431 | 0.454 | 0.435 | 0.418 | 0.440
mColBERT | 0.414 | 0.383 | 0.401 | 0.379 | 0.367 | 0.348 | 0.389 | 0.361 | 0.345 | 0.377
R@1000
BM25 | 0.649 | 0.655 | 0.657 | 0.628 | 0.649 | 0.627 | 0.640 | 0.514 | 0.517 | 0.616
mColBERT | 0.597 | 0.526 | 0.549 | 0.525 | 0.510 | 0.475 | 0.547 | 0.503 | 0.423 | 0.518
Table 2: Main results in the mRobust04 dataset. mT5 and mColBERT were
finetuned on mMARCO.

The results are shown in Table 2. Except for the Chinese language, the nDCG@20
results for BM25 in each language are very close to English, indicating that
our automatic translation was able to retain the information present in the
original documents successfully. The average nDCG@20 of the mT5 reranker
slightly surpasses BM25’s. Looking at nDCG’@20, mT5 shows clear improvements
over BM25. This suggests that there is a non-negligible amount of documents in
top 20 reranked by mT5 that are relevant but were not annotated.

We expected the dense model, mColBERT, to be worse than the mT5 model and
better than BM25 as observed by Bonifacio et al. [3]. This is because mColBERT
would be able to overcome the lexical matching problem that BM25 suffers from,
as dense models could potentially represent semantically similar words closer
to each other in the indexed embedding space. However, mColBERT did not
perform well on mRobust04, staying behind both models for all metrics and
languages. One possibility is that mColBERT is “overfitted” to mMARCO and was
unable to generalize to a new domain. Another explanation is similar to that
proposed by Rosa et al. [14]: dense retrievers show great in-domain
effectiveness but poor out-of-domain generalization. However, rigorously
testing this hypothesis for the multilingual scenario is beyond the scope of
this work.

## Acknowledgments

This research was partially funded by grants 2020/09753-5 and 2022/01640-2
from Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP). We also
thank Google Cloud for credits to support this work.

## References

  * Bajaj et al. [2018] P. Bajaj, D. Campos, N. Craswell, L. Deng, J. Gao, X. Liu, R. Majumder, A. McNamara, B. Mitra, T. Nguyen, M. Rosenberg, X. Song, A. Stoica, S. Tiwary, and T. Wang.  MS MARCO: A Human Generated MAchine Reading COmprehension Dataset.  _arXiv:1611.09268v3_ , 2018.
  * Bird et al. [2009] S. Bird, E. Klein, and E. Loper.  _Natural language processing with Python: analyzing text with the natural language toolkit_.  " O’Reilly Media, Inc.", 2009.
  * Bonifacio et al. [2021] L. H. Bonifacio, V. Jeronymo, H. Q. Abonizio, I. Campiotti, R. de Alencar Lotufo, and R. Nogueira.  mmarco: A multilingual version of MS MARCO passage ranking dataset.  _CoRR_ , abs/2108.13897, 2021.  URL https://arxiv.org/abs/2108.13897.
  * Braschler [2002a] M. Braschler.  Clef 2001 — overview of results.  In C. Peters, M. Braschler, J. Gonzalo, and M. Kluck, editors, _Evaluation of Cross-Language Information Retrieval Systems_ , pages 9–26, Berlin, Heidelberg, 2002a. Springer Berlin Heidelberg.
  * Braschler [2002b] M. Braschler.  Clef 2002—overview of results.  In _Workshop of the Cross-Language Evaluation Forum for European Languages_ , pages 9–27. Springer, 2002b.
  * Braschler [2003] M. Braschler.  Clef 2003–overview of results.  In _Workshop of the cross-language evaluation forum for european languages_ , pages 44–63. Springer, 2003.
  * Craswell et al. [2021] N. Craswell, B. Mitra, E. Yilmaz, D. Campos, E. M. Voorhees, and I. Soboroff.  Trec deep learning track: reusable test collections in the large data regime.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 2369–2375, 2021\.
  * Honnibal and Montani [2017] M. Honnibal and I. Montani.  spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing.  To appear, 2017.
  * Lawrie et al. [2022] D. Lawrie, J. Mayfield, D. W. Oard, and E. Yang.  Hc4: a new suite of test collections for ad hoc clir.  In _European Conference on Information Retrieval_ , pages 351–366. Springer, 2022.
  * Lin et al. [2021] J. Lin, R. Nogueira, and A. Yates.  Pretrained transformers for text ranking: Bert and beyond.  _Synthesis Lectures on Human Language Technologies_ , 14(4):1–325, 2021.
  * Majumder et al. [2013] P. Majumder, D. Pal, A. Bandyopadhyay, and M. Mitra.  Overview of fire 2010.  In _Multilingual Information Access in South Asian Languages_ , pages 252–257. Springer, 2013.
  * Mitra [2008] M. Mitra.  Overview of fire 2008.  In _Working Notes of Forum for Information Retrieval Evaluation_ , 2008.
  * Peters and Braschler [2001] C. Peters and M. Braschler.  European research letter: Cross-language system evaluation: The clef campaigns.  _Journal of the American Society for Information Science and Technology_ , 52(12):1067–1072, 2001.
  * Rosa et al. [2022] G. M. Rosa, L. Bonifacio, V. Jeronymo, H. Abonizio, M. Fadaee, R. Lotufo, and R. Nogueira.  No parameter left behind: How distillation and model size affect zero-shot retrieval.  _arXiv preprint arXiv:2206.02873_ , 2022.
  * Sakai [2007] T. Sakai.  Alternatives to bpref.  In _Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval_ , pages 71–78, 2007.
  * Sakai et al. [2021] T. Sakai, D. W. Oard, and N. Kando.  _Evaluating Information Retrieval and Access Tasks: NTCIR’s Legacy of Research Impact_.  Springer Nature, 2021.
  * Schäuble and Sheridan [1998] P. Schäuble and P. Sheridan.  Cross-language information retrieval (clir) track overview.  _NIST SPECIAL PUBLICATION SP_ , pages 31–44, 1998.
  * Voorhees [2004] E. M. Voorhees.  Overview of the TREC 2004 robust track.  In _Proceedings of the Thirteenth Text REtrieval Conference (TREC 2004)_ , pages 52–69, Gaithersburg, Maryland, 2004.
  * Voorhees et al. [2022a] E. M. Voorhees, N. Craswell, and J. Lin.  Too many relevants: Whither cranfield test collections?  In _Proceedings of the 45th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2022)_ , 2022a.
  * Voorhees et al. [2022b] E. M. Voorhees, I. Soboroff, and J. Lin.  Can old trec collections reliably evaluate modern neural retrieval models?  _arXiv preprint arXiv:2201.11086_ , 2022b.
  * Zhang et al. [2021] X. Zhang, X. Ma, P. Shi, and J. Lin.  Mr. tydi: A multi-lingual benchmark for dense retrieval.  In _Proceedings of the 1st Workshop on Multilingual Representation Learning_ , pages 127–137, 2021.


# Fusion of Embeddings Networks for Robust Combination of
Text Dependent and Independent Speaker Recognition

###### Abstract

By implicitly recognizing a user based on his/her speech input, speaker
identification enables many downstream applications, such as personalized
system behavior and expedited shopping checkouts. Based on whether the speech
content is constrained or not, both text-dependent (TD) and text-independent
(TI) speaker recognition models may be used. We wish to combine the advantages
of both types of models through an ensemble system to make more reliable
predictions. However, any such combined approach has to be robust to
incomplete inputs, i.e., when either TD or TI input is missing. As a solution
we propose a fusion of embeddings network (foenet) architecture, combining
joint learning with neural attention. We compare foenet with four competitive
baseline methods on a dataset of voice assistant inputs, and show that it
achieves higher accuracy than the baseline and score fusion methods,
especially in the presence of incomplete inputs.

Keywords— Speaker recognition, fusion of embeddings.

##  1 Introduction

Speaker recognition answers the question “who is speaking” given a speech
utterance. Based on whether the utterance content is constrained or not, there
are two types of speaker recognition model: text-dependent (TD) and text-
independent (TI). For the former, the utterance content is known or limited to
a small set of options. For deployment in voice assistants, the input usually
consists of the predefined wakeword, such as “Hey Google”, “Echo” or “Alexa”.
TI systems, on the other hand, make no assumptions on what was said, and
therefore have wider applicability. Besides, they are typically more accurate
than TD systems as the utterances from TI systems tend to be longer than the
ones from TD systems at both training and test time [1].

For example, given an utterance like “Alexa, what time is it?”, the TD and TI
speaker recognition models can predict speaker identity independently. The TD
model compares the acoustic signal corresponding to “Alexa” and a user’s
corresponding enrolled wakeword segments to calculate a matching score. The TI
model, on the other hand, can take either the entire utterance or the non-
wakeword portion and compare it with users’ enrolled utterances to yield
another matching score. The two models are generally trained with independent
machine learning models and on different datasets with the goal of optimizing
their recognition performance individually. When both TD and TI models are
available, we should be able to improve overall accuracy by combining their
predictions; however, the following three concerns arise. First, it is not
clear how to best combine the models, given that a range of fusion methods
have been proposed in machine learning (such as early fusion and late fusion
[2, 3], etc.). Second, the inputs for the two systems, especially the TD
system, may not be always available. For example, the wakeword may be optional
in certain contexts. Table 1 further summarizes the scenarios with missing
inputs from either the TD or the TI system. Third, a user’s voice may change
(e.g., due to aging) and they may re-enroll, which may lead to a domain shift
between training and test data, which in turn may affect the balance between
TI and TD models for fusion purposes.

Table 1: Scenarios when speaker profile or utterance embeddings are
unavailable. $E_{spk}$ and $E_{u}$ represent speaker profile and test
utterance embedding, respectively. Detailed descriptions of $E_{spk}^{TD}$ and
$E_{u}^{TD}$,$E_{spk}^{TI}$ and $E_{u}^{TI}$ are given in Section 2.

Scenario | $E_{spk}^{TD}$ | $E_{u}^{TD}$ | $E_{spk}^{TI}$ | $E_{u}^{TI}$
---|---|---|---|---
There are no wakewords in an utterance | $\checkmark$ | ${\mathbf{x}}$ | $\checkmark$ | $\checkmark$
The wakeword detector fails to identify the wakeword in an utterance | $\checkmark$ | ${\mathbf{x}}$ | $\checkmark$ | $\checkmark$
Devices are woken up by a button press | $\checkmark$ | ${\mathbf{x}}$ | $\checkmark$ | $\checkmark$
The speaker gets enrolled, but for a different wakeword | ${\mathbf{x}}$ | $\checkmark$ | $\checkmark$ | $\checkmark$
TD model is working improperly during run time | $\checkmark$ | ${\mathbf{x}}$ | $\checkmark$ | $\checkmark$
TI model is working improperly during run time | $\checkmark$ | $\checkmark$ | $\checkmark$ | ${\mathbf{x}}$

Speaker recognition has been studied extensively as a supervised
classification problem [4, 5, 6]. Traditionally, solutions are based on
i-vector representation of speech segments [7]. More recently, methods based
on deep neural net embeddings (d-vectors) have been adopted. Deep speaker [8]
and VGGVox [9] utilize CNN-based residual networks to extract audio embeddings
and optimize triplet and contrastive losses to train speaker recognition
models, respectively. Two other Resnet-based methods [10, 11] adopt additive
margin softmax classification loss [12] to improve the recognition accuracy.
More recently, Mockingjay [13], TERA [14], APC [15] and DeCoAR [16] learn
speaker embedding representations based on self-supervised spectrogram
reconstructions or predictions.

While combining of speaker recognition models was very popular in research
systems before d-vectors [17, 18], little recent work has looked at combining
multiple neural embedding systems. [19] explores person verification by fusing
audio and visual systems. Researchers investigate how to fuse GMM-UBM based TD
and TI speaker recognition models in [20], where the TD and TI scores are fed
as inputs to a fusion classifier. Nevertheless, it does not address the
problem of incomplete inputs.

Our work assumes users have registered profiles consisting of embeddings, each
based on four to ten utterances. We also assume pre-trained TD and TI models,
which are capable of generating corresponding fix-length embeddings given a
new utterance. Unlike the aforementioned fusion research, which combines
score-level outputs from component systems, we develop a fusion approach that
uses embedding-level predictions from both TD and TI models. Moreover, we
allow the system to operate in the face of incomplete input, such as when an
utterance does not start with a wakeword; the wakeword detector fails to
identify the wakeword; a user has not yet enrolled for a wakeword sample (but
the test utterance contains one); or an unexpected run-time error prevents the
recognition engines from generating either TD or TI embeddings.

Figure 1: _foe net_ architecture. Two differential embeddings
$E_{\text{diff}}^{TD}$ and $E_{\text{diff}}^{TI}$ are first calculated based
on speaker profile and test utterance embeddings, for TD and TI systems
separately. In addition, two backup differential embeddings
$E_{\text{infer}}^{TD}$ and $E_{\text{infer}}^{TI}$ are inferred from TI and
TD systems, respectively. The backup differential embeddings are used only
when $E_{\text{diff}}^{TD}$ or $E_{\text{diff}}^{TI}$, respectively, are not
available. $\hat{E}_{diff}^{TD}$ and $\hat{E}_{diff}^{TI}$ combines the
information from direct differential embedding and inferred differential
embedding. Finally $\hat{E}_{diff}^{TD}$ and $\hat{E}_{diff}^{TI}$ are
concatenated and fed to a connected layer.

##  2 Fusion of Embeddings Network

Given a test utterance $u$, the goal of the speaker recognition model is to
learn a scoring function such that the score $s(spk,u)$ between the target
speaker and $u$ is as high as possible, while the scores between other
speakers and $u$ are as low as possible.

We use $E_{u}^{TD}$ and $E_{u}^{TI}$ to denote the embeddings of a test
utterance $u$ generated by TD and TI models, respectively. Similarly, we use
$E_{spk}^{TD}$ and $E_{spk}^{TI}$ to denote the profile embeddings of speaker
$spk$ generated by the TD and TI model, respectively. More precisely, if the
profile of a speaker is composed of a set of $M$ utterances
$\\{u_{1},u_{2},...,u_{M}\\}$, then
$E_{spk}=\frac{1}{M}\sum_{i=1}^{M}E_{u_{i}}$.

To effectively fuse predictions from both TD and TI models, while handling the
issue of incomplete inputs, we propose the fusion model shown in Fig. 1, which
combines TD and TI predictions at the embedding level. When the input from one
of the systems is not available, the model will infer the missing embedding
from the one that is available. This results in a consistent input to the
fusion layer, which computes a scalar score from the concatenation of TD and
TI embeddings-level outputs.

For both TD and TI models, we first calculate a differential embedding between
the speaker profile embedding $E_{spk}$ and the utterance embedding $E_{u}$.
Formally,

$E_{diff}^{TD}=E_{spk}^{TD}-E_{u}^{TD},$ (1)

and

$E_{diff}^{TI}=E_{spk}^{TI}-E_{u}^{TI},$ (2)

where the operator $-$ denotes element-wise subtraction. Ideally, if the
utterance $u$ comes from the target speaker $spk$, small values, which are
close to a vector of zeros, are expected to be observed in both
$E_{diff}^{TD}$ and $E_{diff}^{TI}$. This is because $E_{spk}$, a
representative of $spk$’s multiple enrolled utterances, is expected to be
close in the latent space to the embedding representation of the speaker’s
test utterance $u$. If $u$ comes from a non-target speaker, on the other hand,
values very different from zeros are expected in both $E_{diff}^{TD}$ and
$E_{diff}^{TI}$. We posit that both $E_{diff}^{TD}$ and $E_{diff}^{TI}$ serve
as useful discriminants, which help effectively distinguish genuine speakers
from others and expedite model training. Moreover, we expect that
$E_{diff}^{TD}$ and $E_{diff}^{TI}$ remain discriminative as users’ profiles
and test utterances evolve over time. As users’ voices evolve over time, their
profiles can be continuously updated by adding their recent voice utterances,
which can be achieved by comparing the recent voice interactions received from
devices and users’ profiles at that moment. In this way, relative small
values, close to zeros, remain expected in $E_{diff}^{TD}$ and $E_{diff}^{TI}$
if test utterances come from target speakers.

As detailed in Table 1, $E_{spk}$ and $E_{u}$ are not always available. In
such cases, we cannot calculate the differential embedding directly. To
address this issue, when either one or both of the two embedding inputs (i.e.,
$E_{spk}$ and $E_{u}$) from one system are not available, both $E_{spk}$ and
$E_{u}$ from that system will be set to zero vectors. $E_{diff}$ will also be
a zero vector as the result of element-wise subtraction. At the same time, we
will infer the differential embedding from the other subsystem, that is
available. Formally,

$E_{infer}^{TD}=\begin{cases}0^{\prime}s,\text{if both $E_{spk}^{TD}$ and
$E_{u}^{TD}$ are available,}\\\ f(E_{diff}^{TI}\cdot
W_{TD2TI}+b_{TD2TI}),\text{Otherwise.}\end{cases}$ (3)

Similarly,

$E_{infer}^{TI}=\begin{cases}0^{\prime}s,\text{if both $E_{spk}^{TI}$ and
$E_{u}^{TI}$ are available,}\\\ f(E_{diff}^{TD}\cdot
W_{TI2TD}+b_{TI2TD}),\text{Otherwise.}\end{cases}$ (4)

where $W_{TD2TI}$, $W_{TI2TD}$ and $b_{TD2TI}$, $b_{TI2TD}$ are learnable
weight matrices and bias vectors, respectively. $f(\cdot)$ is the activation
function. Exponential linear units [21] (ELUs) are chosen as the activation
function for their expected benefits in convergence and accuracy. The inferred
differential embedding serves as a substitute that we only rely on when the
direct differential embedding is not available. Therefore,

$\hat{E}_{diff}^{TD}=E_{diff}^{TD}+E_{infer}^{TD}.$ (5)

Similarly,

$\hat{E}_{diff}^{TI}=E_{diff}^{TI}+E_{infer}^{TI}.$ (6)

We then combine the differential information from TD and TI systems by
concatenating $\hat{E}_{diff}^{TD}$ and $\hat{E}_{diff}^{TI}$.

$\hat{E}_{diff}=\hat{E}_{diff}^{TD}\|\hat{E}_{diff}^{TI}.$ (7)

We further feed $\hat{E}_{diff}$ to a fully connected layer to yield the
prediction score $y^{pred}$. Formally,

$y^{pred}=f(BN(\hat{E}_{diff}\cdot W_{pred}+b_{pred})),$ (8)

where $W_{pred}$ and $b_{pred}$ are learnable parameters. $BN(\cdot)$ conducts
the batch normalizations [22], and $f(\cdot)$ is the activation function (the
sigmoid function in our implementation).

We use cross-entropy as the loss for an instance $i$:

$l_{i}(\Theta)=-[y_{i}\log(y^{\text{pred}}_{i})+(1-y_{i})\log(1-y^{\text{pred}}_{i})],$
(9)

where $\Theta$ denotes the union of all model parameters.

Given a mini-batch of $k$ training instances, the loss over all $k$ training
instances is given by

$L(\Theta)=\frac{1}{k}\sum_{i=1}^{k}l_{i}(\Theta)+\alpha L_{2}(\Theta),$ (10)

where $L_{2}(\Theta)$ calculates the $L_{2}$ norm of $\Theta$ as the
regularizer and $\alpha$ is a hyperparameter, which balances the trade-off
between the classification loss and regularizer. To update the model
parameters $\Theta$, we apply Adam [23]. Algorithm 1 summarizes the detailed
training processes of _foe net_.

1 Input: learning rate $\eta$, maximal number of epochs $itr_{max}$, TD
speaker embedding $E_{spk}^{TD}$, TD utterance embedding $E_{u}^{TD}$, TI
speaker embedding $E_{spk}^{TI}$, TI utterance embedding $E_{u}^{TI}$

Initialize: Model parameters $\Theta$, EER∗ = $+\infty$

1: /* Training on the training dataset */

2: for $itr~{}\leq~{}itr_{max}$ do

3: Randomly shuffle all training instances.

4: Sequentially generate a mini-batch of $k$ training instances.

5: Calculate loss based on Equation 10.

6: Update model parameters by applying Adam.

7:

8: /* Calculate the EER on the validation dataset */

9: if EER $\leq$ EER∗ then

10: $\Theta^{*}$ = $\Theta$

11: EER∗ = EER

Output: $\Theta^{*}$

Algorithm 1 Embedding fusion model training

##  3 Experiments

We follow previous work [24] to extract acoustic features from the raw audio.
Forty-dimensional Mel-spectrograms are extracted from waveforms after energy-
based voice activity detection.

###  3.1 Training and evaluation data

The training and evaluation are conducted on de-identified speech utterances
collected from Alexa devices. The training data comprises both positive and
negative instances. To construct positive instances, we apply an existing
speaker recognition model to 5,000-hour Alexa data and construct
utterance/speaker pairs, as identified by high prediction scores in single-
speaker registered households. In this way, it is less likely that non-target
speakers are included in the positive training instances. The same number of
negative instances are then constructed by pairing a random guest speaker and
a test utterance from the same gender but from a different household. The
gender is determined by a pre-trained utterance-level gender classifier. This
selection strategy is based on the intuition that confusable (same-gender)
pairs are more informative for training. After constructing the dataset, 85%
of instances are utilized as parameter training data and the remaining 15%
serve as validation data, i.e., for model selection.

The evaluation dataset is constructed by first randomly sampling anonymized
utterances. Then each sampled utterance and the enrollment data of speakers
associated with the same device are sent to multiple annotators to collect the
ground-truth labels independently. To reduce annotation errors, we select
utterances which have consistent annotation labels to form the final
evaluation dataset. For comparisons over time, we construct two such
evaluation datasets based on data from two consecutive weeks.

###  3.2 Baselines

To evaluate the performance of _foe net_, the following four methods are
adopted as baselines:

Single-system GE2E

[25] utilizes an LSTM to construct utterance embeddings and optimizes the
speaker recognition system by maximizing the similarity among utterances
coming from the same speaker. It utilizes the entire utterance to make
predictions and serves as a TI model. No TD system is used.

Average fusion (AF)

takes the prediction scores from TD and TI models as inputs and outputs the
average of these two scores as the fused prediction score. When either TD or
TI score is absent, we construct a piecewise linear score mapping based on
pairs of corresponding FAR numbers between AF and the TD/TI system.

Score fusion (SF)

[20] takes the prediction scores from the TD and TI systems as inputs and
trains a neural network to learn the joint prediction. When the score from one
system is absent, -1 is used as a placeholder input during both training and
inference.

Enhanced score fusion (E-SF)

extends SF by inferring the score from the other SID system output when one
score is absent. The missing scores are estimated by nonlinear regression
(linear transform followed by tanh) with the score from the other system as
input, and take the place of the missing fusion inputs in the SF network (see
above).

We train the TD model based on the Siamese network [26] and the TI model using
GE2E [25]. However, note that the proposed embedding fusion framework can be
applied to any embedding-based TD and TI systems, or even to any sets of such
systems where some of the outputs are sometimes unavailable.

###  3.3 Results

We evaluated the performance of foenet against different baseline methods on
the two one-week online evaluation datasets. We calculate false accept rate
(FAR) and false reject rate (FRR) on the evaluation sets.

$\text{FAR}=\frac{\\#\text{ of false accepted imposter trials}}{\\#\text{ of
imposter trials}}$ (11) $\text{FRR}=\frac{\\#\text{ of false rejected target
trials}}{\\#\text{ of target trials}}$ (12)

As different downstream applications have different requirements for expected
FARs, we threshold scores at four different values, and compare corresponding
FRR results across methods.

Table 2: FRR relative improvements (%) in Week 1

Scenarios | Methods | Targeted FAR
---|---|---
|  | 0.8% | 2.0% | 5.0% | 12.5%
TD&TI present |  _foe net_ vs GE2E | 21.0 | 22.5 | 22.8 | 22.5
_foe net_ vs AF | 10.3 | 10.3 | 14.4 | 14.1
_foe net_ vs SF | 11.9 | 13.2 | 15.0 | 13.8
_foe net_ vs E-SF | 11.3 | 12.1 | 14.9 | 13.8
TD absent |  _foe net_ vs GE2E | 14.8 | 19.4 | 30.5 | 47.7
_foe net_ vs AF | 17.2 | 20.3 | 31.7 | 49.3
_foe net_ vs SF | 6.0 | 14.4 | 29.1 | 48.3
_foe net_ vs E-SF | 4.2 | 13.3 | 27.6 | 47.0
TI absent |  _foe net_ vs GE2E | not applicable
_foe net_ vs AF | 35.3 | 40.7 | 48.9 | 50.1
_foe net_ vs SF | 4.5 | 13.0 | 20.3 | 29.8
_foe net_ vs E-SF | 8.6 | 16.5 | 22.3 | 31.2

Table 3: FRR relative improvements (%) in Week 2

Scenarios | Methods | Targeted FAR
---|---|---
|  | 0.8% | 2.0% | 5.0% | 12.5%
TD&TI present |  _foe net_ vs GE2E | 20.5 | 21.7 | 25.0 | 22.5
_foe net_ vs AF | 8.3 | 12.1 | 13.1 | 14.6
_foe net_ vs SF | 12.1 | 14.3 | 14.3 | 16.5
|  _foe net_ vs E-SF | 10.5 | 13.3 | 13.7 | 17.4
TD absent |  _foe net_ vs GE2E | 14.3 | 20.6 | 30.7 | 45.0
_foe net_ vs AF | 15.2 | 20.6 | 30.7 | 46.0
_foe net_ vs SF | 5.2 | 14.3 | 28.1 | 45.2
|  _foe net_ vs E-SF | 4.0 | 13.0 | 26.6 | 43.8
TI absent |  _foe net_ vs GE2E | not applicable
_foe net_ vs AF | 34.9 | 40.7 | 49.9 | 53.3
_foe net_ vs SF | 3.8 | 10.7 | 23.1 | 31.2
|  _foe net_ vs E-SF | 10.4 | 15.7 | 25.8 | 32.8

Tables 2 and 3 compare the FRRs for different methods on the two evaluation
datasets. The tabulated values are the relative FRR reductions between foenet
and each of the four baselines. We highlight four main observations. First, we
observe that foenet, AF, SF, and E-SF outperform single-system GE2E in most
cases, especially when both TD and TI inputs are available. This shows the
advantage of utilizing both TD and TI models in combination. Clearly,
leveraging both TD and TI systems yields more accurate speaker identity
predictions than just depending on a single TI model.

Second, foenet consistently outperforms the fusion-by-average (AF) and the two
score-fusion baselines (SF and E-SF). For example, when we target 12.5% FAR,
compared with AF/SF/E-SF, foenet reduces FRR by 14.1%/13.8%/13.8%,
respectively, when both TD and TI inputs are available in Week 1. We observe
similar FRR reductions when targeting 0.8%, 2.0%, and 5.0% FARs. The same
observation applies to the Week-2 evaluation set. We conclude that fusion at
the embedding level, rather than at the score level, significantly improves
the speaker recognition performance.

Third, for almost all FAR levels, the advantage of foenet over GE2E, AF, SF,
and E-SF increases when there are incomplete inputs (note that GE2E can only
be applied when TI input is present). Specifically, when TD signals are not
available, foenet outperforms GE2E, AF, SF, and E-SF by 47.7%, 49.3%, 48.3%,
and 47.0% respectively, at a target FAR of 12.5% (in Week 1). This shows that
our approach of inferring missing differential embeddings prior to system
fusion is effective.

Fourth, we observe that E-SF fails to outperform SF consistently and they
achieve similar FRR performances in most comparisons. This shows the
disadvantage of score-level fusions, as all information has been already
integrated into a single score and it becomes too hard to extract sufficient
information from single scores to recover the missing scores from other
systems.

We also separately confirmed the intuition that generating negative samples
based on same-gender pairings improves model performance. There is a relative
6% FRR reduction when gender information is used for ruling out easy,
different-gender samples.

##  4 Conclusions

We presented foenet, a fusion architecture that combines predictions from both
TD and TI speaker recognition systems at the embedding-level, by combining
differential embeddings from both subsystems. Special care is taken to allow
the system to work when either TD or TI input is not available, as may happen
due to the operational characteristics of voice assistants (such as missing
wakewords). This is accomplished by estimating the missing differential
embeddings from the embeddings that are available. foenet does not require
fine tuning of the previously trained TI and TD models; both models can be
directly used as is. Experiments on Alexa voice assistant traffic data
demonstrate that foenet is substantially more effective than four baselines,
i.e., a single TI GE2E model, a score-averaging fusion method, and two score-
based neural network fusion methods.

## References

  * [1] R. Chojnacka, J. Pelecanos, Q. Wang, and I. Lopez-Moreno, “Speakerstew: Scaling to many languages with a triaged multilingual text-dependent and text-independent speaker verification system,” _CoRR_ , vol. abs/2104.02125, 2021.
  * [2] H. Gunes and M. Piccardi, “Affect recognition from face and body: early fusion vs. late fusion,” in _Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Waikoloa, Hawaii, USA, October 10-12, 2005_. IEEE, 2005, pp. 3437–3443.
  * [3] C. Snoek, M. Worring, and A. W. M. Smeulders, “Early versus late fusion in semantic video analysis,” in _Proceedings of the 13th ACM International Conference on Multimedia, Singapore, November 6-11, 2005_ , H. Zhang, T. Chua, R. Steinmetz, M. S. Kankanhalli, and L. Wilcox, Eds. ACM, 2005, pp. 399–402.
  * [4] R. Li, J. Jiang, J. L. Li, C. Hsieh, and W. Wang, “Automatic speaker recognition with limited data,” in _WSDM, Houston, TX_ , 2020, pp. 340–348.
  * [5] R. Li, J. Jiang, X. Wu, H. Mao, C. Hsieh, and W. Wang, “Bridging mixture density networks with meta-learning for automatic speaker identification,” in _2020 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2020, Barcelona, Spain, May 4-8, 2020_. IEEE, 2020, pp. 3522–3526.
  * [6] R. Li, J. Jiang, X. Wu, C. Hsieh, and A. Stolcke, “Speaker identification for household scenarios with self-attention and adversarial training,” in _Interspeech 2020, 21st Annual Conference of the International Speech Communication Association, Virtual Event, Shanghai, China, 25-29 October 2020_. ISCA, 2020, pp. 2272–2276.
  * [7] N. Dehak, P. Kenny, R. Dehak, P. Dumouchel, and P. Ouellet, “Front-End Factor Analysis for Speaker Verification,” _IEEE Trans. Audio, Speech & Language Processing_, vol. 19, no. 4, pp. 788–798, 2011.
  * [8] C. Li, X. Ma, B. Jiang, X. Li, X. Zhang, X. Liu, Y. Cao, A. Kannan, and Z. Zhu, “Deep Speaker: an End-to-End Neural Speaker Embedding System,” _CoRR_ , vol. abs/1705.02304, 2017.
  * [9] J. S. Chung, A. Nagrani, and A. Zisserman, “VoxCeleb2: Deep Speaker Recognition,” _CoRR_ , vol. abs/1806.05622, 2018. [Online]. Available: http://arxiv.org/abs/1806.05622
  * [10] W. Xie, A. Nagrani, J. S. Chung, and A. Zisserman, “Utterance-level Aggregation for Speaker Recognition in the Wild,” in _Proceedings of ICASSP, Brighton, United Kingdom, May 12-17_ , 2019.
  * [11] M. Hajibabaei and D. Dai, “Unified Hypersphere Embedding for Speaker Recognition,” _CoRR_ , vol. abs/1807.08312, 2018. [Online]. Available: http://arxiv.org/abs/1807.08312
  * [12] F. Wang, W. Liu, H. Dai, H. Liu, and J. Cheng, “Additive Margin Softmax for Face Verification,” in _Proceedings of ICLR, Vancouver, BC, Canada, April 30 - May 3_ , 2018.
  * [13] A. T. Liu, S. Yang, P. Chi, P. Hsu, and H. Lee, “Mockingjay: Unsupervised speech representation learning with deep bidirectional transformer encoders,” in _Processing of ICASSP 2020, Barcelona, Spain, May 4-8, 2020_. IEEE.
  * [14] A. T. Liu, S. Li, and H. Lee, “TERA: self-supervised learning of transformer encoder representation for speech,” _CoRR_ , vol. abs/2007.06028, 2020.
  * [15] Y. Chung, W. Hsu, H. Tang, and J. R. Glass, “An unsupervised autoregressive model for speech representation learning,” in _Interspeech 2019, 20th Annual Conference of the International Speech Communication Association, Graz, Austria, 15-19 September 2019_ , G. Kubin and Z. Kacic, Eds. ISCA, 2019, pp. 146–150.
  * [16] S. Ling, Y. Liu, J. Salazar, and K. Kirchhoff, “Deep contextualized acoustic representations for semi-supervised speech recognition,” in _2020 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2020, Barcelona, Spain, May 4-8, 2020_. IEEE, 2020, pp. 6429–6433.
  * [17] S. S. Kajarekar, N. Scheffer, M. Graciarena, E. Shriberg, A. Stolcke, L. Ferrer, and T. Bocklet, “The SRI NIST 2008 speaker recognition evaluation system,” in _Proc. IEEE ICASSP_ , 2009, pp. 4205–4208. [Online]. Available: http://www.speech.sri.com/papers/papers/icassp2009-sre08system.ps.gz
  * [18] L. Burget, M. Fapšo, V. Hubeika, O. Glembek, M. Karafiát, M. Kockmann, P. Matějka, P. Schwarz, and J. Černockỳ, “BUT system for NIST 2008 speaker recognition evaluation,” in _Proc. Interspeech_ , 2009, pp. 2335–2338.
  * [19] S. Shon, T. Oh, and J. R. Glass, “Noise-tolerant audio-visual online person verification using an attention-based neural network fusion,” in _IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2019, Brighton, United Kingdom, May 12-17, 2019_. IEEE, 2019.
  * [20] I. Mporas, S. Safavi, and R. Sotudeh, “Improving robustness of speaker verification by fusion of prompted text-dependent and text-independent operation modalities,” in _Speech and Computer - 18th International Conference, SPECOM 2016, Budapest, Hungary, August 23-27, 2016, Proceedings_ , ser. Lecture Notes in Computer Science, A. Ronzhin, R. Potapova, and G. Németh, Eds., vol. 9811. Springer, 2016, pp. 378–385.
  * [21] D. Clevert, T. Unterthiner, and S. Hochreiter, “Fast and accurate deep network learning by exponential linear units (ELUs),” in _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.
  * [22] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in _Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015_ , ser. JMLR Workshop and Conference Proceedings, F. R. Bach and D. M. Blei, Eds., vol. 37. JMLR.org, 2015, pp. 448–456.
  * [23] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2015.
  * [24] P. Anand, A. K. Singh, S. Srivastava, and B. Lall, “Few Shot Speaker Recognition using Deep Neural Networks,” _CoRR_ , vol. abs/1904.08775, 2019\.
  * [25] L. Wan, Q. Wang, A. Papir, and I. Moreno, “Generalized End-to-end Loss For Speaker Verification,” in _Proceedings of ICASSP, Calgary, AB, Canada, April 15-20_ , 2018, pp. 4879–4883.
  * [26] J. Bromley, I. Guyon, Y. LeCun, E. Säckinger, and R. Shah, “Signature verification using a siamese time delay neural network,” in _Advances in Neural Information Processing Systems, [7th NIPS Conference, Denver, Colorado, USA, 1993]_ , 1993, pp. 737–744.


reductions, is applied to the template rather than to an instance.

###  4.1. The arc-graph reduction and adjunctions

A reduction between PCSPs that provably goes beyond gadget replacements has
been used in (Krokhin et al., 2020) to improve hardness results for
approximate graph colouring. This reduction transforms a digraph into its
_arc-graph_ , which is defined as follows. For a digraph $\mathbf{G}$, its
arc-graph $\delta(\mathbf{G})$ is the digraph whose vertices are the edges of
$\mathbf{G}$, and whose edges are pairs of edges of $\mathbf{G}$ forming a
2-path:

$\delta(\mathbf{G})=(E^{\mathbf{G}};\\{((x,y),(z,w))\mid(x,y),(z,w)\in
E^{\mathbf{G}},y=z\\}).$

It is known that, for any digraphs $\mathbf{G},\mathbf{H}$, we have
$\delta(\mathbf{G})\to\mathbf{H}$ if and only if
$\mathbf{G}\to\delta_{R}(\mathbf{H})$, where the transformation $\delta_{R}$
can be described in a few ways. For example, we can set
$\delta_{R}(\mathbf{H})$ to be the digraph whose vertices are all subsets of
$H$, and there is an edge from a subset $U$ to a subset $V$ if there is $u\in
U$ such that $(u,v)\in E^{\mathbf{H}}$ for all $v\in V$. It is not hard to
check that $\delta$ is a reduction from
$\operatorname{PCSP}(\mathbf{G},\delta_{R}(\mathbf{H})$ to
$\operatorname{PCSP}(\delta(\mathbf{G}),\mathbf{H})$ whenever both PCSPs are
defined, i.e., when $\delta(\mathbf{G})\to\mathbf{H}$ and
$\mathbf{G}\to\delta_{R}(\mathbf{H})$.

This reduction can be used to reduce from
$\operatorname{PCSP}(\mathbf{K}_{b(k)},\mathbf{K}_{b(c)})$ to
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{c})$ for any $k,c\geq 4$ where
$b(k)=\binom{k}{\lfloor k/2\rfloor}$. Starting with a result of Huang (2013),
a repeated application of this reduction has led to a considerable improvement
in state-of-the-art NP-hardness results for approximate graph colouring
(Krokhin et al., 2020). We will discuss this in more detail in Section 5.2.

The arc-graph reduction falls into a wider scheme of reductions that are
described by _adjunctions_ , which is a notion from category theory. Two
transformations $\gamma$ and $\omega$ are said to be _adjoint_ if, for all
structures $\mathbf{A}$ and $\mathbf{B}$,

(7) $\gamma(\mathbf{A})\to\mathbf{B}\text{ if and only if
}\mathbf{A}\to\omega(\mathbf{B}),$

assuming that $\gamma$ transforms $\mathbf{A}$ to a structure similar to
$\mathbf{B}$ and $\omega$ transforms $\mathbf{B}$ to a structure similar to
$\mathbf{A}$. In this case $\gamma$ is called a _left adjoint_ to $\omega$,
and $\omega$ a _right adjoint_ to $\gamma$. Another example of adjunction is
when $\gamma$ is a gadget replacement, and $\omega$ the corresponding pp-
power, as we described in Section 2.2.1. As it is known from the algebraic
approach, in this case $\gamma$ gives an efficiently computable reduction from
$\operatorname{CSP}(\omega(\mathbf{A}))$ to $\operatorname{CSP}(\mathbf{A})$
for each relational structure $\mathbf{A}$ (to which $\omega$ can be applied).
This in fact generalises to arbitrary adjunctions (naturally, from the
computational complexity perspective, we are only interested in cases where
$\gamma$ is efficiently computable), and to PCSPs: any efficiently computable
left adjoint $\gamma$ to $\omega$ can be used as a reduction from
$\operatorname{PCSP}(\mathbf{B},\omega(\mathbf{A}^{\prime}))$ to
$\operatorname{PCSP}(\gamma(\mathbf{B}),\mathbf{A}^{\prime})$ (Krokhin et al.,
2020). More information on the use of adjunctions in PCSP (and more examples)
can be found in (Krokhin et al., 2020).

We remark that it is currently not known how (or whether) reductions given by
adjunctions, even in the special case of the arc-graph reduction, can be
characterised in terms of polymorphisms of the involved templates.

###  4.2. Generalising minion homomorphisms

We briefly outline the core results of a recent paper by Barto and Kozik
(2022) that describes a reduction between PCSPs that is more general than
gadget reductions and gives a sufficient condition for the existence of this
reduction from $\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ that is weaker than the
existence of minion homomorphism from
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$. Moreover, this
sufficient condition is still expressed in terms of the two polymorphism
minions. This result goes towards the general goal described in the beginning
of this section. In particular, it allows one to to show NP-hardness of some
PCSPs by a regular type of reduction from 3-Sat through the use of
polymorphisms. This covers several NP-hardness results, e.g., those from
Examples 2.4, 2.7, and 2.8, where original proofs relied on Gap Label Cover
and the PCP theorem.

We formulate a simplified version of the reduction used in (Barto and Kozik,
2022) — while formally, this formulation is different, it can be shown that if
there is a reduction according to (Barto and Kozik, 2022) between two PCSPs,
then the reduction described here also works. We use the notation
$\binom{X}{\leq k}$ for the set of all at most $k$-element non-empty subsets
of $X$. And we refine a definition of a power of a structure to allow sets for
exponents; the structure $\mathbf{B}^{X}$ is isomorphic to $\mathbf{B}^{\lvert
X\rvert}$.

###### Definition 4.1.

Let $X$ be a set and $\mathbf{B}$ a relational structure, we define the _$X$
-th power of $\mathbf{B}$_ denoted by $\mathbf{B}^{X}$ as the structure
$(B^{X};R^{\mathbf{B}^{X}},\dots)$ where $B^{X}$ is the set of all functions
from $X$ to $B$, and

$R^{\mathbf{B}^{X}}=\\{(b_{1},\dots,b_{k})\mid(b_{1}(x),\dots,b_{k}(x))\in
R^{\mathbf{B}}\text{ for all }x\in X\\}$

for each $k$-ary relational symbol $R$ of $\mathbf{B}$.

We now give a concise description of the reduction which we will call here,
for the lack of better name, _$k$ -reduction_. Assume that we are reducing
from $\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$, and fix a (large
enough) positive integer $k$. Intuitively, the reduction is very similar to a
gadget replacement with the key difference that we consider each set of at
most $k$ variables at a time as one unit replaced by one gadget — each of
these gadgets is a power of $\mathbf{B}$ as defined above.

Let $\mathbf{I}$ be an instance of
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$, we construct an
instance $\phi(\mathbf{I})$ as follows. For a subset $K\subseteq I$, let
$\mathbf{I}[K]$ denote the (induced) substructure of $\mathbf{I}$ with domain
$K$ obtained by removing all tuples containing elements not from $K$ from all
relations in $\mathbf{I}$.

  * •

For each $K\in\binom{I}{\leq k}$, let $\mathcal{F}_{K}$ be the set of all
homomorphisms from $\mathbf{I}[K]$ to $\mathbf{A}$. For each such $K$,
introduce into $\phi(\mathbf{I})$ a copy of $\mathbf{B}^{\mathcal{F}_{K}}$.

  * •

For each $L\subset K\in\binom{I}{\leq k}$, there is a natural map from
$\mathcal{F}_{K}$ to $\mathcal{F}_{L}$ that maps $h$ to its restriction
$h|_{L}$. We identify each element $b$ of $\mathbf{B}^{\mathcal{F}_{L}}$ with
the element $b_{K}$ of $\mathbf{B}^{\mathcal{F}_{K}}$ defined as
$b_{K}(h)=b(h|_{L})$.

It is not hard to see that this transformation $\phi$ can be computed in log-
space. When is this transformation a reduction from
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$? Barto and Kozik (2022)
provide a partial answer to this question. We also note that they only claim
that their reduction is polynomial time since in order to provide a log-space
reduction between search problems, we need to provide an efficient way to
reconstruct a solution for $\mathbf{I}$ from a solution $\phi(\mathbf{I})$.
Theorem 4.3 below only asserts that if there is a solution to
$\phi(\mathbf{I})$ then there is also a solution to $\mathbf{I}$, but it is
not obvious whether it can be computed in log-space.

We remark that $k$-reduction is also closely connected with Sherali-Adams (SA)
hierarchy (see Sherali and Adams, 1990; Ciardo and Živný, 2022b) in the
following sense. First, SA can be essentially viewed as a reduction from a CSP
to linear programming. Naturally, this reduction is different from the basic
linear programming relaxation. Namely, the difference lies in the fact that
the $k$-th level of SA considers $k$ variables at the same time in very much
the same way as in the definition above. A difference from the above
construction is in the step where the sets $\mathcal{F}_{K}$ are converted
into a gadget ($\mathbf{B}^{\mathcal{F}_{K}}$ above): SA uses a more efficient
gadget consisting of all probability distributions on $\mathcal{F}_{K}$. This
consequently also alters the identification step (second item above).

Barto and Kozik (2022) introduce a generalisation of minion homomorphisms that
is a sufficient condition for the existence of a $k$-reduction for some $k$.
The simpler version of the new homomorphism is the so-called _$d$
-homomorphism_ which is a mapping that assigns to each function from
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ a list of at most $d$
_candidates_ from $\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$ of the
same arity, such that, for each minor relation $f=g^{\pi}$, there is a choice
of candidates, $f^{\prime}$ from image of $f$ and $g^{\prime}$ from the image
of $g$, that satisfy the same minor relation $f^{\prime}=(g^{\prime})^{\pi}$.
(The standard minion homomorphism is thus a 1-homomorphism.) This notion
further generalises to $(d,r)$-homomorphisms defined below; a $d$-homomorphism
is a $(d,1)$-homomorphism. Loosely speaking, a $d$-homomorphism forces us to
weakly satisfy each minor relation, while a $(1,r)$-homomorphism does not
require that each minor relation is satisfied, but at least one that from each
chain of $r$ minor relations. A precise definition that combines both these
behaviours is given below.

###### Definition 4.2.

Fix a minion $\mathscr{M}$, a _chain of minors_ in $\mathscr{M}$ of length $r$
is a sequence $t_{0},\dots,t_{r}\in\mathscr{M}$ together with functions
$\pi_{i,j}$ for $0\leq i<j\leq r$, such that $t_{j}=t_{i}^{\pi_{i,j}}$ for all
$i<j$ and $\pi_{i,k}=\pi_{i,j}\circ\pi_{j,k}$, for all $i<j<k$.

Let $\mathscr{M}$ and $\mathscr{N}$ be two minions. A _$(d,r)$ -homomorphism_
from $\mathscr{M}$ to $\mathscr{N}$ is a mapping $\xi$ that assigns to each
element of $\mathscr{M}$ a non-empty subset of $\mathscr{N}$ of size at most
$d$ such that

  1. (1)

for all $f\in\mathscr{M}$, every $g\in\xi(f)$ has the same arity as $f$.

  2. (2)

for each chain of minors in $\mathscr{M}$ as above, there exist $i<j$ and
$g_{i}\in\xi(t_{i})$, $g_{j}\in\xi(t_{j})$ such that
$g_{j}=g_{i}^{\pi_{i,j}}$.

Note that, in a chain of minors, the maps $\pi_{i,j}$ are determined by
$\pi_{i,i+1}$ since all others are obtained by composition. So, one way to
create such a chain is to start with $t_{0}$ and to iteratively take a minor
$t_{i+1}=t_{i}^{\pi_{i,i+1}}$.

Often a $(d,r)$-homomorphism can be given by providing $r$ partial
$d$-homomorphisms that cover the whole minion $\mathscr{M}$. More precisely,
assume that $\mathscr{M}=\mathscr{M}_{1}\cup\dots\cup\mathscr{M}_{r}$ where
each $\mathscr{M}_{i}$ is not necessarily a minion, and that we have maps
$\xi_{i}\colon\mathscr{M}_{i}\to\mathscr{N}$ that are _partial
$d$-homomorphisms_, i.e., they satisfy the conditions (1) and (2) in
Definition 4.2 for every chain of minors of length 1 that is contained in the
same $\mathscr{M}_{i}$. Then there is a $(d,r)$-homomorphism
$\xi\colon\mathscr{M}\to\mathscr{N}$ which is defined by taking the union of
$\xi_{i}$’s and breaking ties arbitrarily whenever some of $\xi_{i}$’s
disagree. This is a $(d,r)$-homomorphism, since, for every chain of minors
$t_{0},\dots,t_{r}$, there will be some $s$ such that some $t_{i}$ and $t_{j}$
belong to the same $\mathscr{M}_{s}$ and $\xi(t_{i})=\xi_{s}(t_{i})$ and
$\xi(t_{j})=\xi_{s}(t_{j})$.

###### Theorem 4.3 ((Barto and Kozik, 2022, Theorem 5.1)).

Let $(\mathbf{A},\mathbf{A}^{\prime})$ and $(\mathbf{B},\mathbf{B}^{\prime})$
be two PCSP templates. If there is a $(d,r)$-homomorphism from
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$, then there exists $k$
such that $\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ reduces to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ by the $k$-reduction.

One important consequence of the above theorem (Corollary 4.4 below) is that
polymorphisms of a bounded arity (or, more generally, of bounded essential
arity) have no influence on the complexity of a PCSP. In particular, one
cannot make any conclusions about the complexity of
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ solely on the basis of
the presence of any single finite set of functions in the polymorphism minion
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$. A coordinate $i$ of a
function $f\colon A^{n}\rightarrow A^{\prime}$ is called _inessential_ if, for
all $i\in[n]$ and $a_{1},\dots,a_{n},a_{i}^{\prime}\in A$, we have
$f(a_{1},\dots,a_{i},\dots,a_{n})=f(a_{1},\dots,a^{\prime}_{i},\dots,a_{n})$.
Otherwise, the coordinate $i$ is called _essential_. The number of essential
coordinates of a function is called its _essential arity_.

###### Corollary 4.4.

Fix any number $m\geq 1$. If there is a partial minion homomorphism

$\xi\colon\mathscr{B}\to\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$

where $\mathscr{B}\subseteq\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$
is the set of all polymorphisms of essential arity at least $m$ then
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ is reducible to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ by $k$-reduction for
some $k$.

By partial minion homomorphism in the above theorem, we mean that minors
$f=g^{\pi}$ are preserved for all functions $f,g\in\mathscr{B}$.

As a special case of Corollary 4.4, consider the situation when $A=B$,
$A^{\prime}=B^{\prime}$ and
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$ and
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ have the same functions
of essential arity at least $m$, for some $m$, (but there is assumption on
functions of essential arity less than $m$ in the two minions). Then Corollary
4.4 implies that $\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ and
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ are reducible to each
other.

The proof of Corollary 4.4 is straightforward, we can extend the partial
homomorphism $\xi$ to a full $d$-homomorphism, where $d$ is the number of
$m$-ary functions in $\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$. To
define the extension, map any $n$-ary function
$f\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ of essential arity
less then $m$ to the set of all $n$-ary functions in
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$ whose set of essential
coordinates is contained in the set of essential coordinates of $f$. It is not
hard to check that this indeed gives a $d$-homomorphism from
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$, and one can apply
Theorem 4.3.

An argument similar to the one before Theorem 4.3 gives the following.

###### Corollary 4.5.

Let $\mathscr{A}=\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$ and
$\mathscr{B}=\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ If there is
$r$ and a collection of $r$ partial minion $d$-homomorphism
$\xi_{i}\colon\mathscr{B}_{i}\to\mathscr{A}$ where
$\mathscr{B}_{i}\subseteq\mathscr{B}$ for each $i=0,\dots,r-1$, and
$\mathscr{B}=\bigcup_{i=0}^{r-1}\mathscr{B}_{i}$ then
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ is reducible to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ by $k$-reduction for
some $k$.

One open question relating $(d,r)$-homomorphisms with the arc-graph reduction
is whether there is a $(d,r)$-homomorphism for some $d$ and $r$ from
$\operatorname{Pol}(\delta\mathbf{G},\mathbf{H})$ to
$\operatorname{Pol}(\mathbf{G},\delta_{R}\mathbf{H})$ for any digraphs
$\mathbf{G}$ and $\mathbf{H}$. We know that the arc-graph reduction is a
reduction between the corresponding PCSPs. In fact, it is possible to show
using the construction $\delta_{R}$ that $3$-reduction also provides such a
reduction in this case. Nevertheless, it is not clear that the sufficient
condition from Theorem 4.3 is satisfied in this case. If it is not, this would
mean that $(d,r)$-homomorphisms are not necessary for $k$-reduction to work.

We are far from understanding reductions (beyond gadget reductions) in many
ways: Is $k$-reduction sufficient to build a strong enough general theory for
PCSPs? Is there a characterisation when a $k$-reduction is an actual reduction
from one PCSP to another in terms of the polymorphism minions of the two
templates? Would a more general reduction be more open to such a
characterisation?

###  4.3. Some open questions and directions

  * •

Find a class of reductions between PCSPs that is strong enough (say, to cover
more than gadget reductions) together with a characterisation when such a
reduction is applicable.

  * •

Can reductions given by adjunctions be described in terms of polymorphisms?
The special case of the arc-graph construction is a good place to start.

  * •

Is $(d,r)$-homomorphism also a necessary condition for the existence of a
$k$-reduction? If not, find a more general (polymorphism-based) condition that
would be both sufficient and necessary for such reductions.

  * •

Is there a $(d,r)$-homomorphism for some $d$ and $r$ from
$\operatorname{Pol}(\delta\mathbf{G},\mathbf{H})$ to
$\operatorname{Pol}(\mathbf{G},\delta_{R}\mathbf{H})$ for all (or some
interesting) digraphs $\mathbf{G}$ and $\mathbf{H}$?

  * •

It is known (Krokhin et al., 2020) that each minion of polymorphisms carries a
topological structure. Investigate how this topological structure can be used
to provide more reductions between PCSPs.

##  5\. “Limited enough” polymorphisms and NP-hardness

For CSPs, we know exactly which problems $\operatorname{CSP}(\mathbf{B})$ are
NP-hard (assuming $\text{P}\neq\text{NP}$), by (Bulatov, 2017; Zhuk, 2017,
2020). In fact, the hardness part of the CSP Dichotomy Theorem is easy and has
long been known (Bulatov et al., 2005). One way to characterise the NP-hard
CSPs is as follows (Barto et al., 2018). Recall the minion $\mathscr{P}$ of
all projections on $\\{0,1\\}$ from Section 2.2.3. Then the NP-complete CSPs
are the problems $\operatorname{CSP}(\mathbf{B})$ such that there exists a
minion homomorphism from $\operatorname{Pol}(\mathbf{B})$ to $\mathscr{P}$.
Since, as we mentioned in Section 2.2.3, $\mathscr{P}$ is the polymorphism
minion of the structure corresponding to 3-Sat, this means that every NP-hard
$\operatorname{CSP}(\mathbf{B})$ admits a gadget reduction from 3-Sat (unless
P = NP). Since every projection of a given arity $n$ is uniquely determined by
one of its coordinates, the existence of such a minion homomorphism means
exactly that, for each function $f$ in $\operatorname{Pol}(\mathbf{B})$, one
can select one “important” coordinate $i_{f}$ in such a way that if
$f=g^{\pi}$ then $i_{f}=\pi(i_{g})$.

For PCSPs, the situation is more complicated, since, as mentioned before,
there are many NP-hard PCSPs whose polymorphism minion does not admits a
minion homomorphism to $\mathscr{P}$ (and hence there is no gadget reduction
from 3-Sat). In fact, there is some belief (Brakensiek and Guruswami, 2021)
that, unlike for CSPs, understanding hardness in PCSPs will be at least as
difficult as understanding tractability (regardless of the question about the
existence of dichotomy for PCSPs).

###  5.1. Proving NP-hardness results via polymorphisms

A prevalent (so far) use of Theorem 4.3 to prove NP-hardness of PCSPs is to
show a reduction from 3-Sat, i.e., with $\mathbf{A}=\mathbf{A}^{\prime}$ being
the template of 3-Sat, and hence
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})=\mathscr{P}$.

###### Corollary 5.1.

Let $(\mathbf{B},\mathbf{B}^{\prime})$ be a PCSP template. If, for some fixed
$d,r\geq 1$, there is a $(d,r)$-homomorphism from
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ to $\mathscr{P}$ then
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ is NP-hard.

Corollary 5.1 for the case $r=1$ was proved in (Barto et al., 2021b) (the core
of the argument appeared in (Austrin et al., 2017)) and for the case $d=1$ and
arbitrary $r$ in (Brandts et al., 2021), but both of these results predate
(Barto and Kozik, 2022) and their original proofs relied on the PCP theorem.

Let us spell out what the condition in the above corollary says. Fix a
$(d,r)$-homomorphism
$\xi\colon\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})\rightarrow\mathscr{P}$.
If $f$ is an $n$-ary function in
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ then $\xi(f)$ is a non-
empty collection of (at most) $d$ projections
$p_{n}^{s_{1}},\ldots,p_{n}^{s_{d}}$ of arity $n$, where $1\leq s_{j}\leq n$
for each $j$. In other words, $\xi$ can be viewed as selecting a set
$\operatorname{sel}(f)=\\{s_{1},\ldots,s_{d}\\}\subseteq[n]$ of (at most) $d$
“special” coordinates in $f$. Now assume that we have a chain of minors
$t_{0},\dots,t_{r}\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ such
that $t_{j}=t_{i}^{\pi_{i,j}}$, for each $i<j$, where
$\pi_{i,k}=\pi_{i,j}\circ\pi_{j,k}$, for all $i<j<k$. Then there must exist
$i<j$ such that
$\operatorname{sel}(t_{j})\cap\pi_{i,j}(\operatorname{sel}(t_{i}))\neq\emptyset$.
In other words, it cannot be that, for all $i,j$, the image under $\pi_{i,j}$
of the “special” coordinates in $t_{i}$ does not contain any “special”
coordinates of $t_{j}$.

Informally, the fact that one can identify a bounded number of special
coordinates in every polymorphism (in a coordinated way) shows that these
polymorphisms are in some way “lopsided”, and so
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ is “limited enough”. To
contrast this intuition with “rich enough” polymorphisms from Section 3, let
us explain why there cannot be a $(d,r)$-homomorphism from
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ to $\mathscr{P}$ if
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ contains symmetric
functions of all arities. Indeed, assume such a $(d,r)$-homomorphism $\xi$
exists for some $d,r$. Choose any symmetric function $t_{0}$ of arity
$d\cdot(r+1)$ in $\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ and let
$S=sel(t_{0})$ be the set of (at most) $d$ special coordinates of $t_{0}$
selected by $\xi$. Choose a permutation $\pi$ on $[d\cdot(r+1)]$ so that $S$
intersects none of the sets $\pi(S),\pi^{2}(S),\ldots,\pi^{d(r+1)-1}(S)$,
clearly this can be done. Consider the chain of minors $t_{0},\dots,t_{r}$
where $t_{i}=t_{0}^{\pi^{i}}$ (and so $\pi_{i,j}=\pi^{j-i}$ for all $i<j$).
Note that we have $t_{0}=t_{1}=\ldots=t_{r}$, since $t_{0}$ is symmetric, but
$S=\operatorname{sel}(t_{j})$ is disjoint from
$\pi_{i,j}(\operatorname{sel}(t_{i}))=\pi^{j-i}(S)$ for all $i<j$, by the
choice of $\pi$.

Let us now discuss how Corollary 5.1 is applied. Naturally, it is all about
selecting special sets of coordinates in polymorphisms. How exactly to select
the special variables for a given application is the creative part.

Let’s start with the case $r=1$. In this case we want to select, for each
polymorphism $f$, a set $\operatorname{sel}(f)$ of (at most) $d$ “special”
coordinates in such a way that, for every minor relation $t_{1}=t_{0}^{\pi}$
in $\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$, the set of special
coordinates in $t_{0}$, after applying $\pi$, i.e.,
$\pi(\operatorname{sel}(t_{0}))$, shares at least one element with the set
$\operatorname{sel}(t_{1})$.

###### Example 5.2.

Assume that we can prove that each
$f\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ has at least one and
at most $d$ essential variables (which means that the values of the remaining,
non-essential, variables have no effect on the output of $f$). We can set
$\operatorname{sel}(f)$ to be the set of essential variables of $f$. In this
case it is easy to check that if $t_{1}=t_{0}^{\pi}$ then
$\operatorname{sel}(t_{1})$ and $\pi(\operatorname{sel}(t_{0}))$ can never be
disjoint. This reasoning was used, for example, in (Austrin et al., 2017) to
prove NP-hardness of $(2+\varepsilon)$-Sat problems (see Example 2.4) — though
via the PCP theorem.

The case $r=1$ can be applicable even when polymorphisms have an unbounded
number of essential variables — the special variables can be selected on the
basis of some other property, as in Example 2.18 or in the following example.

###### Example 5.3.

Let $\mathbf{C}_{2k+1}$ be an undirected cycle with $2k+1$ nodes, $k\geq 1$,
and let $\mathbf{K}_{3}$ be a 3-clique. The approximate graph homomorphism
problem $\operatorname{PCSP}(\mathbf{C}_{2k+1},\mathbf{K}_{3})$ (recall
Example 2.7) has been proved NP-hard in (Krokhin et al., 2020) by applying
Corollary 5.1 as follows. One can associate a topological space to every
graph. The space associated with an odd cycle is a circle, and the space
associated with the $n$-th power of an odd cycle is an $n$-torus. Furthermore,
any graph homomorphism $f$, and hence also a polymorphism, induces a
continuous map $\hat{f}$ between the corresponding spaces, hence we assign to
a polymorphism $f\colon\mathbf{C}_{2k+1}^{n}\to\mathbf{K}_{3}$ a continuous
map $\hat{f}$ from $n$-torus to the circle. Observing that the main
topological invariant of a continuous map from a circle to itself is its
degree (or winding number), one can then prove, roughly, that $\hat{f}$ will
have a bounded number of coordinates with non-zero degree. These coordinates
are then chosen to form the set $\operatorname{sel}(f)$, and one can prove
that
$\operatorname{sel}(t_{1})\cap\pi(\operatorname{sel}(t_{0}))\neq\emptyset$
holds whenever $t_{1}=t_{0}^{\pi}$.

The previous example is a rare (so far) case when the analysis of
polymorphisms in a hardness proof for PCSP is performed not by direct
combinatorics, but instead by first mapping them by a minion homomorphism to a
different abstract minion, where the behaviour of their images is easier to
understand. It would be of significant interest to find more examples of
hardness of proofs of this sort, where the target abstract minion can be of
topological or of some other nature.

Now let us discuss applications of Corollary 5.1 with $r>1$. One useful
pattern is provided in the following example, taken from (Brandts et al.,
2021), where it is applied to prove NP-hardness of certain generalisations of
$(2+\varepsilon)$-Sat to non-Boolean domains.

###### Example 5.4.

Assume that we can define the notion of a set of coordinates, called _smug
sets_ in (Brandts et al., 2021), for functions in
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ so that the following
conditions are satisfied:

  * •

every $f\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ has a smug set
consisting of at most $d$ coordinates;

  * •

no function in $\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ can have
more than $r$ pairwise disjoint smug sets;

  * •

if $f=g^{\pi}$ for some
$g,f\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ then the
$\pi$-preimage of any smug set in $f$ is a smug set in $g$.

Then, for any $f\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$, we can
set $\operatorname{sel}(f)$ to be an arbitrary smug set of variables of size
at most $d$ in it. This does not in general guarantee that
$\operatorname{sel}(t_{1})\cap\pi(\operatorname{sel}(t_{0}))\neq\emptyset$
whenever $t_{1}=t_{0}^{\pi}$. However, the last two conditions in the
definition of a smug set imply that, for any chain of minors
$t_{0},\dots,t_{r}\in\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$, it
is impossible that
$\operatorname{sel}(t_{j})\cap\pi_{i,j}(\operatorname{sel}(t_{i}))=\emptyset$
for all $i<j$.

Another useful pattern of applying Corollary 5.1 with $r>1$ is when functions
in $\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ can be shown to
exhibit $r$ different types of behaviour, so that
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ can be divided into $r$
(not necessarily disjoint) types, where the definition of
$\operatorname{sel}(f)$ depends on the type of a polymorphism, and one can
show that $\operatorname{sel}(g)\cap\pi(\operatorname{sel}(f))\neq\emptyset$
holds whenever $g=f^{\pi}$ and $g$ and $f$ are of the same type. This can also
be described as representing
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ as
$\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})=\mathscr{M}_{1}\cup\dots\cup\mathscr{M}_{r}$,
and providing partial $d$-homomorphisms
$\xi_{i}\colon\mathscr{M}_{i}\to\mathscr{P}$ (see Definition 4.2 and the
discussion after it).

###### Example 5.5.

A few simple applications of the above pattern can be found in (Barto et al.,
2021a), where it is applied to problems
$\operatorname{PCSP}(\mathbf{T},\mathbf{B})$ (as in Example 2.5) with
$\mathbf{B}$ being a structure with domain $\\{0,1,2\\}$. For example,
consider the case when the relation of $\mathbf{B}$ consists of triples
$(0,0,1),(0,0,2),(1,1,2)$ and all triples obtained from them by permuting
coordinates. For a function $f:\\{0,1\\}^{n}\rightarrow\\{0,1,2\\}$, call a
set $X$ of coordinates of $f$ a $2$-set if $f$ evaluates to $2$ whenever all
variables in $X$ are equal to 1. Also, define $E(f)$ to be the set of all
coordinates $i$ such that $f(\mathbf{x}_{i})\neq 0$, where $\mathbf{x}_{i}$ is
the tuple where 1 appears only in position $i$. It is shown in (Barto et al.,
2021a) that each $f\in\operatorname{Pol}(\mathbf{T},\mathbf{B})$ has at least
one of the following properties: $f$ has a 2-set $X$ of size at most 2 or the
set $E(f)$ has size at most 5. Whichever case applies for each $f$, select the
corresponding set, $X$ or $E(f)$, to be $\operatorname{sel}(f)$, breaking ties
arbitrarily when there is any choice. Thus, we have
$\operatorname{Pol}(\mathbf{T},\mathbf{B})=\mathscr{M}_{1}\cup\mathscr{M}_{2}$,
where $\mathscr{M}_{i}$ consists all functions
$f\in\operatorname{Pol}(\mathbf{T},\mathbf{B})$ such that
$\operatorname{sel}(f)$ is defined by the first or by the second property
above. It is then shown that this provides partial $5$-homomorphisms from each
$\mathscr{M}_{i}$ to $\mathscr{P}$, and hence a $(5,2)$-homomorphism from
$\operatorname{Pol}(\mathbf{T},\mathbf{B})$ to $\mathscr{P}$.

NP-hardness results for various Boolean PCSPs that can be obtained by using
Corollary 5.1 (even though the original proofs are not always presented that
way) can be found in (Brakensiek and Guruswami, 2021; Brakensiek et al., 2021;
Brandts and Živný, 2021; Ficak et al., 2019).

###  5.2. Hardness of PCSPs from Gap Label Cover

NP-hardness of the Gap Label Cover problem is the starting point of many
hardness proofs in inapproximability. Many hardness results for graph and
hypergraph colouring were obtained via ad hoc reductions from Gap Label Cover,
and will discuss some of them here (see (Barto et al., 2021b, Section 5) for
more details). We remark that one advantage of hardness proofs via Corollary
5.1 (or similar), as compared with reductions from Gap Label Cover is that the
reduction itself is not ad hoc, and thus is more suitable for building a
general theory.

We start with two examples where the original hardness proofs used Gap Label
Cover, but subsequently new proofs via Corollary 5.1 were found.

###### Example 5.6.

Recall the hypergraph colouring problem
$\operatorname{PCSP}(\mathbf{H}_{k},\mathbf{H}_{c})$ from Example 2.8. It was
proved in (Dinur et al., 2005) that
$\operatorname{PCSP}(\mathbf{H}_{k},\mathbf{H}_{c})$ is NP-hard for all $2\leq
k\leq c$, by using a reduction from a multi-layered version of Gap Label
Cover. It was then shown in (Barto et al., 2021b, Section 5.3) how the proof
from (Dinur et al., 2005) can be directly translated into the language of
polymorphisms. Wrochna (2022) refined this to provide a short combinatorial
proof that there is a way to select special coordinates in functions from
$\operatorname{Pol}(\mathbf{H}_{2},\mathbf{H}_{c})$ that gives a
$(d,r)$-homomorphism from $\operatorname{Pol}(\mathbf{H}_{2},\mathbf{H}_{c})$
to $\mathscr{P}$ for appropriately chosen $d$ and $r$, so this hardness result
can now also be explained by using Corollary 5.1.

###### Example 5.7.

Recall Example 2.21. For any $k\geq 3$, the problem
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{2k-1})$ has been proved NP-
hard in (Barto et al., 2021b) by providing a minion homomorphism from
$\operatorname{Pol}(\mathbf{K}_{k},\mathbf{K}_{2k-1})$ to
$\operatorname{Pol}(\mathbf{H}_{2},\mathbf{H}_{c})$, where $c$ is the number
of binary functions in $\operatorname{Pol}(\mathbf{K}_{k},\mathbf{K}_{2k-1})$.
From the previous example, there is a $(d,r)$-homomorphism from
$\operatorname{Pol}(\mathbf{H}_{2},\mathbf{H}_{c})$ to $\mathscr{P}$, for some
$d,r$. It is easy to check that a composition of a minion homomorphism with a
$(d,r)$-homomorphism is again a $(d,r)$-homomorphism, so we conclude that
there is a $(d,r)$-homomorphism from
$\operatorname{Pol}(\mathbf{K}_{k},\mathbf{K}_{2k-1})$ to $\mathscr{P}$.

Let us now discuss hardness results for approximate graph colouring that have
not been explained via polymorphisms so far. Notably, all state-of-the-art NP-
hardness results for $\operatorname{Pol}(\mathbf{K}_{k},\mathbf{K}_{c})$ with
$6\leq k\leq c$ are in this category.

###### Example 5.8.

The strongest known NP-hardness results for
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{c})$ with $k=3,4,5$ are those
from the previous example, with $c=2k-1$. In (Huang, 2013), it was proved, by
a reduction from Gap Label Cover, that
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{c})$ is NP-hard for
$c=2^{\Omega(k^{1/3})}$ and $k$ large enough. By starting from Huang’s result
and repeatedly applying the arc-graph reduction (see Section 4.1), it was
shown in (Krokhin et al., 2020) that
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{c})$ is NP-hard for all $k\geq
4$ and $c=\binom{k}{\lfloor k/2\rfloor}-1$ (which coincides with $2k-1$ for
$k=5$ and is the strongest known result for $k\geq 6$). We note that neither
Huang’s result nor the arc-graph reduction currently have an explanation in
terms of polymorphisms.

Another result from (Krokhin et al., 2020) obtained by using the arc-digraph
construction is that it is enough to prove NP-hardness of
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{c})$ for some fixed $k\geq 3$
and all $c\geq k$, the same will then follow for all $3\leq k\leq c$.

Other examples of NP-hardness results that were obtained by ad hoc reductions
from Gap Label Cover (and cannot currently be explained in terms of
polymorphisms) include results on rainbow vs. normal and strong vs. normal
hypergraph colouring, see references in Example 2.8.

###  5.3. Some open questions and directions

  * •

At the moment, Corollary 5.1 is the most general known formalisation of what
it means for a PCSP to have “limited enough” polymorphisms (to guarantee NP-
hardness). Find other (incomparable or more general) formalisations.

  * •

We mentioned symmetric Boolean PCSPs in Section 3.2. All such PCSPs that are
not tractable are NP-hard (Brakensiek and Guruswami, 2021; Ficak et al.,
2019). Find other interesting examples of NP-hard Boolean (or non-Boolean)
PCSPs.

  * •

Which of the problems $\operatorname{PCSP}(\mathbf{T},\mathbf{B})$ from
Example 2.5 are NP-hard? Specifically, solve this for the case
$\mathbf{B}=\mathbf{LO}_{k}$ whose domain is $\\{0,1,\ldots,k-1\\},k\geq 3$,
and the relation consists of all tuples $(x,y,z)$ that have a unique maximal
element (or, in other words, if two of $x,y,z$ are equal then the third
element is larger than the two equal ones). See (Barto et al., 2021a; Nakajima
and Živný, 2022) for related results.

  * •

Pick your favourite structure $\mathbf{A}$ with NP-hard
$\operatorname{CSP}(\mathbf{A})$ and describe all NP-hard problems
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. More generally, classify the
complexity of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ depending on
$\mathbf{B}$.

  * •

Recall that a smooth digraph is one that has neither sources nor sinks (in
other words, each vertex has positive in- and out-degrees). See (Barto et al.,
2017, 2009) for an explicit description of smooth digraphs $\mathbf{G}$ with
tractable (NP-hard, resp.) $\operatorname{CSP}(\mathbf{G})$. Generalising the
Brakensiek-Guruswami conjecture from Example 2.7, are all problems
$\operatorname{PCSP}(\mathbf{G},\mathbf{H})$ NP-hard when $\mathbf{G}$ and
$\mathbf{H}$ are smooth digraphs with NP-hard CSPs?

  * •

Further develop the topology-based approach mentioned in Example 5.3 to attack
the approximate graph colouring problem (and possibly other PCSPs such as
variants of hypergraph colouring mentioned in Example 2.8).

  * •

Topology has been applied in hardness proofs for PCSPs in different ways:
combinatorial analysis via Borsuk-Ulam-style theorems (Austrin et al., 2020;
Dinur et al., 2005) and topological analysis of polymorphisms (Krokhin et al.,
2020). Investigate whether there is a common pattern behind these
applications.

  * •

In the introduction, we mentioned that the truth of some NP-hardness
conjectures (related to variants of unique games) is known to imply NP-
hardness of all approximate graph colouring problems. Are the reverse
implications true for approximate graph colouring (or some other PCSPs)?

  * •

Investigate logical inexpressibility for PCSPs (see (Atserias and Dalmau,
2022) for the first example of work in this direction).

## References

  * (1)
  * Arora et al. (1998) Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998.  Proof verification and the hardness of approximation problems.  _J. ACM_ 45, 3 (1998), 501–555.
  * Arora and Safra (1998) Sanjeev Arora and Shmuel Safra. 1998.  Probabilistic Checking of Proofs: A New Characterization of NP.  _J. ACM_ 45, 1 (Jan. 1998), 70–122.  https://doi.org/10.1145/273865.273901
  * Asimi and Barto (2021) Kristina Asimi and Libor Barto. 2021.  Finitely Tractable Promise Constraint Satisfaction Problems. In _46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021_ _(LIPIcs)_. Dagstuhl, Germany, 11:1–11:16.  https://doi.org/10.4230/LIPIcs.MFCS.2021.11
  * Atserias et al. (2009) Albert Atserias, Andrei A. Bulatov, and Anuj Dawar. 2009\.  Affine systems of equations and counting infinitary logic.  _Theor. Comput. Sci._ 410, 18 (2009), 1666–1683.  https://doi.org/10.1016/j.tcs.2008.12.049
  * Atserias and Dalmau (2022) Albert Atserias and Víctor Dalmau. 2022.  Promise Constraint Satisfaction and Width. In _Proc. ACM-SIAM Symposium on Discrete Algorithms, SODA 2022_. 1129–1153.  https://doi.org/10.1137/1.9781611977073.48
  * Austrin et al. (2020) Per Austrin, Amey Bhangale, and Aditya Potukuchi. 2020\.  Improved Inapproximability of Rainbow Coloring. In _Proc. ACM-SIAM Symposium on Discrete Algorithms, SODA 2020_. 1479–1495.  https://doi.org/10.1137/1.9781611975994.90 arXiv:1810.02784
  * Austrin et al. (2017) Per Austrin, Venkatesan Guruswami, and Johan Håstad. 2017\.  $(2+\varepsilon)$-Sat Is NP-hard.  _SIAM J. Comput._ 46, 5 (2017), 1554–1573.  https://doi.org/10.1137/15M1006507
  * Barto et al. (2021a) Libor Barto, Diego Battistelli, and Kevin M. Berg. 2021a.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In _Symp. on Theoretical Aspects of Computer Science, STACS 2021_ _(LIPIcs)_. Schloss Dagstuhl–LZI, Dagstuhl, Germany, 10:1–10:16.  https://doi.org/10.4230/LIPIcs.STACS.2021.10
  * Barto et al. (2021b) Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. 2021b.  Algebraic Approach to Promise Constraint Satisfaction.  _J. ACM_ 68, 4, Article 28 (Aug. 2021), 66 pages.  https://doi.org/10.1145/3457606
  * Barto and Kozik (2014) Libor Barto and Marcin Kozik. 2014.  Constraint Satisfaction Problems Solvable by Local Consistency Methods.  _J. ACM_ 61, 1 (Jan. 2014), 3:1–3:19.  https://doi.org/10.1145/2556646
  * Barto and Kozik (2022) Libor Barto and Marcin Kozik. 2022.  Combinatorial Gap Theorem and Reductions between Promise CSPs. In _Proc. ACM-SIAM Symposium on Discrete Algorithms, SODA 2022_. SIAM, Virtual Conference, 1204–1220.  https://doi.org/10.1137/1.9781611977073.50
  * Barto et al. (2009) Libor Barto, Marcin Kozik, and Todd Niven. 2009.  The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell).  _SIAM J. Comput._ 38, 5 (2009), 1782–1802.  https://doi.org/10.1137/070708093
  * Barto et al. (2017) Libor Barto, Andrei Krokhin, and Ross Willard. 2017\.  _Polymorphisms, and How to Use Them_ , 1–44.  In Krokhin and Živný Krokhin and Živný (2017).  https://doi.org/10.4230/DFU.Vol7.15301.1
  * Barto et al. (2018) Libor Barto, Jakub Opršal, and Michael Pinsker. 2018\.  The wonderland of reflections.  _Israel Journal of Mathematics_ 223, 1 (Feb 2018), 363–398.  https://doi.org/10.1007/s11856-017-1621-9
  * Bodirsky (2021) Manuel Bodirsky. 2021\.  _Complexity of Infinite-Domain Constraint Satisfaction_.  Cambridge University Press.  https://doi.org/10.1017/9781107337534
  * Brakensiek and Guruswami (2016) Joshua Brakensiek and Venkatesan Guruswami. 2016.  New Hardness Results for Graph and Hypergraph Colorings. In _Conference on Computational Complexity (CCC 2016)_ _(LIPIcs, Vol. 50)_ , Ran Raz (Ed.). Schloss Dagstuhl–LZI, Dagstuhl, Germany, 14:1–14:27.  https://doi.org/10.4230/LIPIcs.CCC.2016.14
  * Brakensiek and Guruswami (2021) Joshua Brakensiek and Venkatesan Guruswami. 2021.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  _SIAM J. Comput._ 50, 6 (2021), 1663–1700.  https://doi.org/10.1137/19M128212X
  * Brakensiek et al. (2021) Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. 2021\.  Conditional Dichotomy of Boolean Ordered Promise CSPs. In _48th International Colloquium on Automata, Languages, and Programming, ICALP 2021_. 37:1–37:15.  https://doi.org/10.4230/LIPIcs.ICALP.2021.37
  * Brakensiek et al. (2020) Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. 2020\.  The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.  _SIAM J. Comput._ 49, 6 (2020), 1232–1248.  https://doi.org/10.1137/20M1312745 arXiv:1907.04383v3
  * Brandts et al. (2021) Alex Brandts, Marcin Wrochna, and Stanislav Živný. 2021\.  The Complexity of Promise SAT on Non-Boolean Domains.  _ACM Trans. Comput. Theory_ 13, 4 (2021), 26:1–26:20.  https://doi.org/10.1145/3470867
  * Brandts and Živný (2021) Alex Brandts and Stanislav Živný. 2021.  Beyond PCSP(1-in-3, NAE). In _48th International Colloquium on Automata, Languages, and Programming, ICALP 2021_. 121:1–121:14.  https://doi.org/10.4230/LIPIcs.ICALP.2021.121
  * Braverman et al. (2022) Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer. 2022\.  An Invariance Principle for the Multi-slice, with Applications. In _IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021_. 228–236.  https://doi.org/10.1109/FOCS52979.2021.00030
  * Bulatov et al. (2005) Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. 2005\.  Classifying the Complexity of Constraints Using Finite Algebras.  _SIAM J. Comput._ 34, 3 (March 2005), 720–742.  https://doi.org/10.1137/S0097539700376676
  * Bulatov (2017) Andrei A. Bulatov. 2017\.  A Dichotomy Theorem for Nonuniform CSPs. In _IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS 2017_. 319–330.  https://doi.org/10.1109/FOCS.2017.37
  * Bulatov and Dalmau (2006) Andrei A. Bulatov and Víctor Dalmau. 2006.  A Simple Algorithm for Mal’tsev Constraints.  _SIAM J. Comput._ 36, 1 (2006), 16–27.  https://doi.org/10.1137/050628957
  * Bulatov et al. (2008) Andrei A. Bulatov, Andrei Krokhin, and Benoit Larose. 2008\.  Dualities for Constraint Satisfaction Problems. In _Complexity of Constraints: An Overview of Current Research Themes_. Springer, Berlin, Heidelberg, 93–124.  https://doi.org/10.1007/978-3-540-92800-3_5
  * Bulín et al. (2019) Jakub Bulín, Andrei Krokhin, and Jakub Opršal. 2019\.  Algebraic Approach to Promise Constraint Satisfaction. In _Proc. of the 51st Annual ACM-SIGACT Symposium on the Theory of Computing, STOC 2019_. ACM, New York, USA, 602–613.  https://doi.org/10.1145/3313276.3316300
  * Ciardo and Živný (2022a) Lorenzo Ciardo and Stanislav Živný. 2022a.  CLAP: A New Algorithm for Promise CSPs. In _Proc. ACM-SIAM Symposium on Discrete Algorithms, SODA 2022_. 1057–1068.  https://doi.org/10.1137/1.9781611977073.46
  * Ciardo and Živný (2022b) Lorenzo Ciardo and Stanislav Živný. 2022b.  The Sherali-Adams Hierarchy for Promise CSPs through Tensors.  (2022).  https://doi.org/10.48550/arXiv.2203.02478 arXiv:2203.02478
  * Dinur et al. (2009) Irit Dinur, Elchanan Mossel, and Oded Regev. 2009\.  Conditional Hardness for Approximate Coloring.  _SIAM J. Comput._ 39, 3 (2009), 843–873.  https://doi.org/10.1137/07068062X
  * Dinur et al. (2005) Irit Dinur, Oded Regev, and Clifford Smyth. 2005.  The Hardness of 3-Uniform Hypergraph Coloring.  _Combinatorica_ 25, 5 (Sept. 2005), 519–535.  https://doi.org/10.1007/s00493-005-0032-4
  * Feder and Vardi (1998) Tomás Feder and Moshe Y. Vardi. 1998.  The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study Through Datalog and Group Theory.  _SIAM J. Comput._ 28, 1 (Feb. 1998), 57–104.  https://doi.org/10.1137/S0097539794266766
  * Ficak et al. (2019) Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz. 2019.  Dichotomy for Symmetric Boolean PCSPs. In _46th International Colloquium on Automata, Languages, and Programming, ICALP 2019_ _(LIPIcs, Vol. 132)_. Schloss Dagstuhl–LZI, Dagstuhl, Germany, 57:1–57:12.  https://doi.org/10.4230/LIPIcs.ICALP.2019.57 arXiv:1904.12424
  * Garey and Johnson (1976) M. R. Garey and David S. Johnson. 1976.  The Complexity of Near-Optimal Graph Coloring.  _J. ACM_ 23, 1 (1976), 43–49.  https://doi.org/10.1145/321921.321926
  * Guruswami and Khanna (2004) Venkatesan Guruswami and Sanjeev Khanna. 2004.  On the Hardness of 4-Coloring a 3-Colorable Graph.  _SIAM Journal on Discrete Mathematics_ 18, 1 (2004), 30–40.  https://doi.org/10.1137/S0895480100376794
  * Guruswami and Lee (2017) Venkatesan Guruswami and Euiwoong Lee. 2017.  Strong inapproximability results on balanced rainbow-colorable hypergraphs.  _Combinatorica_ (14 Dec. 2017).  https://doi.org/10.1007/s00493-016-3383-0
  * Guruswami and Sandeep (2020a) Venkatesan Guruswami and Sai Sandeep. 2020a.  $d$-To-1 Hardness of Coloring 3-Colorable Graphs with ${O}(1)$ Colors. In _47th International Colloquium on Automata, Languages, and Programming, ICALP 2020_ _(LIPIcs)_. Schloss Dagstuhl–LZI, Dagstuhl, Germany, 62:1–62:12.  https://doi.org/10.4230/LIPIcs.ICALP.2020.62
  * Guruswami and Sandeep (2020b) Venkatesan Guruswami and Sai Sandeep. 2020b.  Rainbow Coloring Hardness via Low Sensitivity Polymorphisms.  _SIAM J. Discrete Math._ 34, 1 (2020), 520–537.  https://doi.org/10.1137/19M127731X
  * Hell and Nešetřil (1990) Pavol Hell and Jaroslav Nešetřil. 1990.  On the complexity of $H$-coloring.  _J. Combin. Theory Ser. B_ 48, 1 (1990), 92–110.
  * Huang (2013) Sangxia Huang. 2013\.  Improved Hardness of Approximating Chromatic Number. In _APPROX 2013 & RANDOM 2013_. Springer, Berlin, Heidelberg, 233–243.  https://doi.org/10.1007/978-3-642-40328-_17
  * Idziak et al. (2010) Paweł M. Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard. 2010\.  Tractability and Learnability Arising from Algebras with Few Subpowers.  _SIAM J. Comput._ 39, 7 (2010), 3023–3037.  https://doi.org/10.1137/090775646
  * Jeavons et al. (1997) Peter Jeavons, David Cohen, and Marc Gyssens. 1997\.  Closure Properties of Constraints.  _J. ACM_ 44, 4 (July 1997), 527–548.  https://doi.org/10.1145/263867.263489
  * Kannan and Bachem (1979) Ravindran Kannan and Achim Bachem. 1979.  Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix.  _SIAM J. Comput._ 8, 4 (1979), 499–507.  https://doi.org/10.1137/0208040
  * Kawarabayashi and Thorup (2017) Ken-ichi Kawarabayashi and Mikkel Thorup. 2017.  Coloring 3-Colorable Graphs with Less than $n^{1/5}$ Colors.  _J. ACM_ 64, 1 (2017), 4:1–4:23.  https://doi.org/10.1145/3001582
  * Kazda et al. (2022) Alexandr Kazda, Peter Mayr, and Dmitriy Zhuk. 2022\.  Small Promise CSPs that reduce to large CSPs.  _Logical Methods in Computer Science_ 18 (Aug. 2022).  Issue 3. https://doi.org/10.46298/lmcs-18(3:25)2022 arXiv:2109.07924
  * Khanna et al. (2000) Sanjeev Khanna, Nathan Linial, and Shmuel Safra. 2000\.  On the Hardness of Approximating the Chromatic Number.  _Combinatorica_ 20, 3 (01 Mar 2000), 393–415.  https://doi.org/10.1007/s004930070013
  * Krokhin et al. (2020) Andrei Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. 2020\.  Topology and adjunction in promise constraint satisfaction.  (2020).  https://doi.org/10.48550/arXiv.2003.11351 arXiv:2003.11351
  * Krokhin and Živný (2017) Andrei Krokhin and Stanislav Živný (Eds.). 2017\.  _The Constraint Satisfaction Problem: Complexity and Approximability_.  Schloss Dagstuhl – LZI.
  * Nakajima and Živný (2022) Tamio-Vesa Nakajima and Stanislav Živný. 2022\.  Linearly ordered colourings of hypergraphs.  (2022).  https://doi.org/10.48550/arXiv.2204.05628 arXiv:2204.05628
  * Raz (1998) Ran Raz. 1998.  A Parallel Repetition Theorem.  _SIAM J. Comput._ 27, 3 (1998), 763–803.  https://doi.org/10.1137/S0097539795280895
  * Schaefer (1978) Thomas J. Schaefer. 1978\.  The Complexity of Satisfiability Problems. In _Proceedings of the Tenth Annual ACM Symposium on Theory of Computing_ _(STOC ’78)_. ACM, New York, USA, 216–226.  https://doi.org/10.1145/800133.804350
  * Sherali and Adams (1990) Hanif D. Sherali and Warren P. Adams. 1990.  A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems.  _SIAM J. Discret. Math._ 3, 3 (1990), 411–430.  https://doi.org/10.1137/0403036
  * Wrochna (2022) Marcin Wrochna. 2022\.  A note on hardness of promise hypergraph colouring.  (2022).  https://doi.org/10.48550/arXiv.2205.14719 arXiv:2205.14719
  * Zhuk (2017) Dmitriy Zhuk. 2017\.  A Proof of CSP Dichotomy Conjecture. In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_. 331–342.  https://doi.org/10.1109/FOCS.2017.38
  * Zhuk (2020) Dmitriy Zhuk. 2020\.  A Proof of the CSP Dichotomy Conjecture.  _J. ACM_ 67, 5 (Aug. 2020), 30:1–30:78.  https://doi.org/10.1145/3402029