# Multilingual LAMA: Investigating Knowledge in Multilingual Pretrained
Language Models

Nora Kassner , Philipp Dufter∗, Hinrich Schütze
Center for Information and Language Processing (CIS), LMU Munich, Germany
<EMAIL_ADDRESS>Equal contribution - random order.

###### Abstract

Recently, it has been found that monolingual English language models can be
used as knowledge bases. Instead of structural knowledge base queries, masked
sentences such as “Paris is the capital of [MASK]” are used as probes. We
translate the established benchmarks TREx and GoogleRE into 53 languages.
Working with mBERT, we investigate three questions. (i) Can mBERT be used as a
multilingual knowledge base? Most prior work only considers English. Extending
research to multiple languages is important for diversity and accessibility.
(ii) Is mBERT’s performance as knowledge base language-independent or does it
vary from language to language? (iii) A multilingual model is trained on more
text, e.g., mBERT is trained on 104 Wikipedias. Can mBERT leverage this for
better performance? We find that using mBERT as a knowledge base yields
varying performance across languages and pooling predictions across languages
improves performance. Conversely, mBERT exhibits a language bias; e.g., when
queried in Italian, it tends to predict Italy as the country of origin.

##  1 Introduction

Pretrained language models (LMs) Peters et al. (2018); Howard and Ruder
(2018); Devlin et al. (2019) can be finetuned to a variety of natural language
processing (NLP) tasks and generally yield high performance. Increasingly,
these models and their generative variants are used to solve tasks by simple
text generation, without any finetuning Brown et al. (2020). This motivated
research on how much knowledge is contained in LMs: Petroni et al. (2019) used
models pretrained with masked language to answer fill-in-the-blank templates
such as “Paris is the capital of [MASK].”

This research so far has been exclusively on English. In this paper, we focus
on using _multilingual_ pretrained LMs as knowledge bases. Working with mBERT,
we investigate three questions. (i) Can mBERT be used as a multilingual
knowledge base? Most prior work only considers English. Extending research to
multiple languages is important for diversity and accessibility. (ii) Is
mBERT’s performance as knowledge base language-independent or does it vary
from language to language? To answer these questions, we translate English
datasets and analyze mBERT for 53 languages. (iii) A multilingual model is
trained on more text, e.g., BERT’s training data contains the English
Wikipedia, but mBERT is trained on 104 Wikipedias. Can mBERT leverage this
fact? Indeed, we show that pooling across languages helps performance.

| Query | Two most frequent predictions
---|---|---
en | X was created in MASK. | [Japan (170), Italy (56), …]
de | X wurde in MASK erstellt. | [Deutschland (217), Japan (70), …]
it | X è stato creato in MASK. | [Italia (167), Giappone (92), …]
nl | X is gemaakt in MASK. | [Nederland (172), Italië (50), …]
en | X has the position of MASK. | [bishop (468), God (68), …]
de | X hat die Position MASK. | [WW (261), Ratsherr (108), …]
it | X ha la posizione di MASK. | [pastore ( 289), papa (138), …]
nl | X heeft de positie van MASK. | [burgemeester (400), bisschop (276) , …]
Table 1: Language bias when querying (TyQ) mBERT. Top: For an Italian cloze
question, Italy is favored as country of origin. Bottom: There is no overlap
between the top-ranked predictions, demonstrating the influence of language –
even though the facts are the same: the same set of triples is evaluated
across languages. Table 3 shows that pooling predictions across languages
addresses bias and improves performance. WW = “Wirtschaftswissenschaftler”.

In summary our contributions are:  i) We automatically create a multilingual
version of TREx and GoogleRE covering 53 languages.  ii) We use an alternative
to fill-in-the-blank querying – ranking entities of the type required by the
template (e.g., cities) – and show that it is a better tool to investigate
knowledge captured by pretrained LMs.  iii) We show that mBERT answers queries
across languages with varying performance: it works reasonably for 21 and
worse for 32 languages.  iv) We give evidence that the query language affects
results: a query formulated in Italian is more likely to produce Italian
entities (see Table 1).  v) Pooling predictions across languages improves
performance by large margins and even outperforms monolingual English BERT.
Code and data are available online (https://github.com/norakassner/mlama).

##  2 Data

###  2.1 LAMA

We follow the LAMA setup introduced by Petroni et al. (2019). More
specifically, we use data from TREx Elsahar et al. (2018) and
GoogleRE.111code.google.com/archive/p/relation-extraction-corpus/ Both consist
of triples of the form (object, relation, subject). The underlying idea of
LAMA is to query knowledge from pretrained LMs using templates without any
finetuning: the triple (Paris, capital-of, France) is queried with the
template “Paris is the capital of [MASK].” In LAMA, TREx has 34,039 triples
across 41 relations, GoogleRE 5528 triples and 3 relations. Templates for each
relation have been manually created by Petroni et al. (2019). We call all
triples from TREx and GoogleRE together _LAMA_.

LAMA has been found to contain many “easy-to-guess” triples; e.g., it is easy
to guess that a person with an Italian sounding name is born in Italy. _LAMA-
UHN_ is a subset of triples that are hard to guess introduced by Poerner et
al. (2020).

###  2.2 Translation

We translate both entities and templates. We use Google Translate to translate
templates in the form “[X] is the capital of [Y]”. After translation, all
templates were checked for validity (i.e., whether they contain “[X]”, “[Y]”
exactly once) and corrected if necessary. In addition, German, Hindi and
Japanese templates were checked by native speakers to assess translation
quality (see Table 2). To translate the entity names, we used Wikidata and
Google knowledge graphs.

mBERT covers 104 languages. Google Translate covers 77 of these. Wikidata and
Google Knowledge Graph do not provide entity translations for all languages
and not all entities are contained in the knowledge graphs. For English we can
find a total of 37,498 triples which we use from now on. On average, 34% of
triples could be translated (macro average over languages). We only consider
languages with a coverage above 20%, resulting in the final number of
languages we include in our study: 53. The macro average of translated triples
in these 53 languages is 43%. Figure 1 gives statistics. We call the
translated dataset _mLAMA_.

Figure 1: x-axis is the number of translated triples, y-axis the number of
languages. There are 39,567 triples in the original LAMA (TREx and GoogleRE).

##  3 Experiments

###  3.1 Model

We work with mBERT Devlin et al. (2019), a model pretrained on the 104 largest
Wikipedias. We denote mBERT queried in language x as mBERT[x]. As comparison
we use the English BERT-Base model and refer to it as BERT. In initial
experiments with XLM-R Conneau et al. (2020) we observed worse performance,
similar to Jiang et al. (2020a). Thus, for simplicity we only report results
on mBERT.

###  3.2 Typed and Untyped Querying

Petroni et al. (2019) use templates like “Paris is the capital of [MASK]” and
give $\arg\max_{w\in\mathcal{V}}p(w|t)$ as answer where $V$ is the vocabulary
of the LM and $p(w|t)$ is the (log-)probability that word $w$ gets predicted
in the template $t$. Thus the object of a triple must be contained in the
vocabulary of the language model. This has two drawbacks: it reduces the
number of triples that can be considered drastically and hinders performance
comparisons across LMs with different vocabularies. We refer to this procedure
as _UnTyQ_.

We propose to use typed querying, _TyQ_ : for each relation a candidate set
$\mathcal{C}$ is created and the prediction becomes
$\arg\max_{c\in\mathcal{C}}p(c|t)$. For templates like “[X] was born in
[MASK]”, we know which entity type to expect, in this case cities. We observed
that (English-only) BERT-base predicts city names for MASK whereas mBERT
predicts years for the same template. TyQ prevents this.

We choose as $\mathcal{C}$ the set of objects across all triples for a single
relation. The candidate set could also be obtained from an entity typing
system (e.g., Yaghoobzadeh and Schütze (2016)), but this is beyond the scope
of this paper. Variants of TyQ have been used before Xiong et al. (2020).

###  3.3 Singletoken vs. Multitoken Objects

Assuming that objects are in the vocabulary Petroni et al. (2019) is a
restrictive assumption, even more in the multilingual case as e.g., “Hamburg”
is in the mBERT vocabulary, but French “Hambourg” is tokenized to [“Ham”,
“##bourg”]. We consider multitoken objects by including multiple [MASK] tokens
in the templates. For both TyQ and UnTyQ we compute the score that a
multitoken object is predicted by taking the average of the log probabilities
for its individual tokens.

Given a template $t$ (e.g., “[X] was born in [Y].”) let $t_{1}$ be the
template with one mask token, (i.e., “[X] was born in [MASK].”) and $t_{k}$ be
the template with $k$ mask tokens (i.e., “[X] was born in [MASK] [MASK]
…[MASK].”). We denote the log probability that the token $w\in V$ is predicted
at $i$th mask token as $p(m_{i}=w|t_{k})$, where $V$ is the vocabulary of the
LM. To compute $p(e|t)$ for an entity $e$ that is tokenized into $l$ tokens
$\epsilon_{1},\epsilon_{2},\dots,\epsilon_{l}$ we simply average the log
probabilities across tokens:

$p(e|t)=\frac{1}{l}\sum_{i=1}^{l}p(m_{i}=\epsilon_{i}|t_{l}).$

If $k$ is the maximum number of tokens of any entity $e\in\mathcal{C}$ gets
split into, we consider all templates $t_{1}$, …, $t_{k}$, with $C$ being the
candidate set. The prediction is then the word with the highest average log
probability across all templates $t_{1}$, …, $t_{k}$.

Note that for UnTyQ the space of possible predictions is $V\times
V\times\dots\times V$ whereas for TyQ it is the candidate set $\mathcal{C}$.

###  3.4 Evaluation

We compute precision at one for each relation, i.e., $1/|T|\sum_{t\in
T}\mathds{1}\\{\hat{t}_{object}=t_{object}\\}$ where $T$ is the set of all
triples and $\hat{t}_{object}$ is the object predicted by TyQ or UnTyQ. Note
that $T$ is different for each language. Our final measure (p1) is then the
precision at one averaged over relations (i.e., macro average). Results for
multiple languages are the macro average p1 across languages.

##  4 Results and Discussion

We first investigate TyQ and UnTyQ and find that TyQ is better suited for
investigating knowledge in LMs. After exploring the translation quality, we
use TyQ on mLAMA and observe rather stable performance for 21 and poor
performance for 32 languages. When investigating the languages more closely,
we find that prediction results highly depend on the language. Finally, we
validate our initial hypothesis that mBERT can leverage its multilinguality by
pooling predictions: pooling indeed performs better.

###  4.1 UnTyQ vs. TyQ

Figure 2:  Distribution of p1 scores for 53 languages in UnTyQ vs. TyQ. Left:
singletoken (object $=$ 1 token). Right: multitoken (object $>$ 1 token).

Figure 2 shows the distribution of p1 scores for single and multitoken
objects. As expected, TyQ works better, both for single and multitoken
objects. With UnTyQ, performance not only depends on the model’s knowledge,
but on at least three extraneous factors: (i) Does the model understand the
type constraints of the template (e.g., in “X is the capital of Y”, Y must be
a country)? (ii) How “fluent” a substitution is an object under linguistic
constraints (e.g., morphology) that can be viewed as orthogonal to knowledge?
Many English templates cannot be translated into a single template in many
languages, e.g., “in X” (with X a country) has different translations in
French: “à Chypre”, “au Mexique”, “en Inde”. But the LAMA setup requires a
single template. By enforcing the type, we reduce the number of errors that
are due to surface fluency. (iii) The inadequacy of the original LAMA setup
for multitoken answers. Figure 2 (right) shows that the original UnTyQ
struggles with multitokens (mean p1 .03 vs. .17 for TyQ).

_Overall, TyQ allows us to focus the evaluation on the core question: what
knowledge is contained in LMs? From now on, we report numbers in the TyQ
setting._

| machine | manually | manually
---|---|---|---
| translated | corrected | paraphrased
de | 18.1 | 19.4 | (6) | 20.9 | (18)
hi | 5.4 | 6.2 | (14) | 6.2 | (1)
ja | 0.4 | 0.4 | (14) | 0.7 | (5)
Table 2: Effect of manual template modification on UnTyQ. Shown is p1, number
of templates modified (in brackets). Templates are modified to correct
mistakes from machine translation and paraphrased to achieve the correct
object type. Manual template correction has a small effect on UnTyQ.

Manual template tuning or automatic template mining Jiang et al. (2020b) has
been investigated in the literature to approach the typing problem. We had
native speakers check templates for German, Hindi and Japanese, correct
mistakes in the automatic translation and paraphrase the template to obtain
predictions with the correct type. Table 2 shows that corrections do not yield
strong improvements. We conclude that template modifications are not an
effective solution for the typing problem.

Figure 3:  p1 of BERT (red) vs mBERT[x] (blue) divided by p1 of mBERT[en] on
the same set of triples in each language x. mBERT captures less factual
knowledge than monolingual English BERT. While performance is reasonable for
21 languages, it is below 60% for 32 languages. Dashed line is rel-p1 of
mBERT[en] (by definition equal to 1.0). Performance of BERT varies slightly as
the set of triples is different for each language. Note that the Wikipedia of
Cebuano (ceb) consists mostly of machine translated articles.

###  4.2 Translation Quality

Contemporaneous work by Jiang et al. (2020a) provides manual translations of
LAMA templates for 23 languages respecting grammatical gender and inflection
constraints. We evaluate our machine translated templates by comparing
performance on a common subset of 14 languages using TyQ querying on the TREx
subset. Surprisingly, we find a performance difference of 1 percentage points
(0.23 vs. 0.24, p1 averaged over languages) in favor of the machine translated
templates. This indicates that the machine translated templates in combination
with TyQ exhibit comparable performance but come with the benefit of larger
language coverage (53 vs. 23 languages).

###  4.3 Multilingual Performance

In mLAMA, not all triples are available in all languages. Thus absolute
numbers are not comparable across languages and we adopt a relative
performance comparison: we report p1 of a model-language combination divided
by p1 of mBERT’s performance in English (mBERT[en]) on the exact same set of
triples and call this _rel-p1_. A rel-p1 score of 0.5 for mBERT[fi] means that
p1 of mBERT on Finnish is half of mBERT[en]’s performance on the same triples.
rel-p1 of English BERT is usually greater than 1 as monolingual BERT tends to
outperform mBERT[en].

Figure 3 shows that mBERT performs reasonably well for 21 languages, but for
32 languages rel-p1 is less than 0.6 (i.e., their p1 is 60% of English’s p1).
We conclude that mBERT does not exhibit a stable performance across languages.
The variable performance (from 20% to almost 100% rel-p1) indicates that mBERT
has no common representation for, say, “Paris” across languages, i.e., mBERT
representations are language-dependent.

###  4.4 Bias

If mBERT captured knowledge independent of language, we should get similar
answers across languages for the same relation. However, Table 1 shows that
mBERT exhibits language-specific biases; e.g., when queried in Italian, it
tends to predict Italy as the country of origin. This effect occurs for
several relations: Table 4 in the supplementary presents data for ten
relations and four languages.

###  4.5 Pooling

We investigate pooling of predictions across languages by picking the object
predicted by the majority of languages. Table 3 shows that pooled mBERT
outperforms mBERT[en] by 6 percentage points on LAMA, presumably in part
because the language-specific bias is eliminated. mBERT[pooled] even
outperforms BERT by 3 percentage points on LAMA-UHN. This indicates that mBERT
can leverage the fact that it is trained on 104 Wikipedias vs. just one and
even outperforms the much stronger model BERT.

| LAMA | LAMA-UHN
---|---|---
BERT | 38.5 | 29.0
mBERT[en] | 35.0 | 25.7
mBERT[pooled] | 41.1 | 32.1
Table 3: p1 for BERT, mBERT queried in English, mBERT pooled on LAMA and LAMA-
UHN.

##  5 Related Work

Petroni et al. (2019) first asked the question: can pretrained LMs function as
knowledge bases? Subsequent analyses focused on different aspects, such as
negation Kassner and Schütze (2020), easy to guess names Poerner et al.
(2020), integrating adapters Wang et al. (2020) or finding alternatives to a
“fill-in-the-blank” approach with single-token answers Bouraoui et al. (2020);
Heinzerling and Inui (2020); Jiang et al. (2020b). Other work combines
pretrained LM with information retrieval Guu et al. (2020); Lewis et al.
(2020a); Izacard and Grave (2020); Kassner and Schütze (2020); Petroni et al.
(2020). None of this work addresses languages other than English.

Multilingual models like mBERT Devlin et al. (2019) and XLM-R Conneau et al.
(2020) perform well for zero-shot crosslingual transfer Hu et al. (2020).
However, we are not aware of any prior work that analyzed to what degree
pretrained multilingual models can be used as knowledge bases. There are many
multilingual question answering datasets such as XQuAD Artetxe et al. (2020),
TiDy Clark et al. (2020), MKQA Longpre et al. (2020) and MLQA Lewis et al.
(2020b). Usually, multilingual models are finetuned to solve such tasks. Our
goal is not to improve question answering or create an alternative
multilingual question answering dataset, but instead to investigate which
knowledge is contained in pretrained multilingual LMs without any kind of
supervised finetuning.

There is a range of alternative multilingual knowledge bases that could be
used for evaluation. Those include ConceptNet Speer et al. (2017) or BabelNet
Navigli and Ponzetto (2010). We decided to provide a translated versions of
TREx and GoogleRE for the sake of comparability across languages. By
translating manually created templates and entities we can ensure
comparability across languages. This is not possible for crowd-sourced
databases like ConceptNet.

In contemporaneous work, Jiang et al. (2020a) create and investigate a
multilingual version of LAMA. They provide human template translations for 23
languages, propose several methods for multitoken decoding and code-switching,
and experiment with a number of PLMs. In contrast to their work, we
investigate typed querying, focus on comparabiliy and pooling across
languages, and explore language biases.

##  6 Conclusion

We presented mLAMA, a dataset to investigate knowledge in language models
(LMs) in a multilingual setting covering 53 languages. While our results
suggest that correct entities can be retrieved for many languages, there is a
clear performance gap between English and, e.g., Japanese and Thai. This
suggests that mBERT is not storing entity knowledge in a language-independent
way. Experiments investigating language bias confirm this finding. We hope
that this paper and the dataset we publish will stimulate research on
investigating knowledge in LMs _multilingually_ rather than just in English.

## Acknowledgements

This work was supported by the European Research Council (# 740516) and the
German Federal Ministry of Education and Research (BMBF) under Grant No.
01IS18036A. The authors of this work take full responsibility for its content.
The second author was supported by the Bavarian research institute for digital
transformation (bidt) through their fellowship program. We thank Yannick
Couzinié and Karan Tiwana for correcting the Japanese and Hindi templates. We
thank the anonymous reviewers for valuable comments.

## References

  * Artetxe et al. (2020) Mikel Artetxe, Sebastian Ruder, and Dani Yogatama. 2020.  On the cross-lingual transferability of monolingual representations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4623–4637, Online. Association for Computational Linguistics.
  * Bouraoui et al. (2020) Zied Bouraoui, José Camacho-Collados, and Steven Schockaert. 2020.  Inducing relational knowledge from BERT.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 7456–7463. AAAI Press.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Clark et al. (2020) Jonathan H. Clark, Jennimaria Palomaki, Vitaly Nikolaev, Eunsol Choi, Dan Garrette, Michael Collins, and Tom Kwiatkowski. 2020.  TyDi QA: A benchmark for information-seeking question answering in typologically diverse languages.  _Transactions of the Association for Computational Linguistics_ , 8:454–470.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Elsahar et al. (2018) Hady Elsahar, Pavlos Vougiouklis, Arslen Remaci, Christophe Gravier, Jonathon Hare, Frederique Laforest, and Elena Simperl. 2018.  T-REx: A large scale alignment of natural language with knowledge base triples.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC-2018)_ , Miyazaki, Japan. European Languages Resources Association (ELRA).
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. 2020\.  REALM: retrieval-augmented language model pre-training.  _Computing Research Repository_ , arXiv:2002.08909.
  * Heinzerling and Inui (2020) Benjamin Heinzerling and Kentaro Inui. 2020.  Language models as knowledge bases: On entity representations, storage capacity, and paraphrased queries.  _Computing Research Repository_ , arXiv:2008.09036.
  * Howard and Ruder (2018) Jeremy Howard and Sebastian Ruder. 2018.  Universal language model fine-tuning for text classification.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 328–339, Melbourne, Australia. Association for Computational Linguistics.
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson. 2020.  XTREME: A massively multilingual multi-task benchmark for evaluating cross-lingual generalisation.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 4411–4421. PMLR.
  * Izacard and Grave (2020) Gautier Izacard and E. Grave. 2020.  Leveraging passage retrieval with generative models for open domain question answering.  _ArXiv_ , abs/2007.01282.
  * Jiang et al. (2020a) Zhengbao Jiang, Antonios Anastasopoulos, Jun Araki, Haibo Ding, and Graham Neubig. 2020a.  X-FACTR: Multilingual factual knowledge retrieval from pretrained language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5943–5959, Online. Association for Computational Linguistics.
  * Jiang et al. (2020b) Zhengbao Jiang, Frank F. Xu, Jun Araki, and Graham Neubig. 2020b.  How can we know what language models know.  _Transactions of the Association for Computational Linguistics_ , 8:423–438.
  * Kassner and Schütze (2020) Nora Kassner and Hinrich Schütze. 2020.  BERT-kNN: Adding a kNN search component to pretrained language models for better QA.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings, EMNLP 2020, Online Event, 16-20 November 2020_ , pages 3424–3430. Association for Computational Linguistics.
  * Kassner and Schütze (2020) Nora Kassner and Hinrich Schütze. 2020.  Negated and misprimed probes for pretrained language models: Birds can talk, but cannot fly.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7811–7818, Online. Association for Computational Linguistics.
  * Lewis et al. (2020a) Mike Lewis, Marjan Ghazvininejad, Gargi Ghosh, Armen Aghajanyan, Sida Wang, and Luke Zettlemoyer. 2020a.  Pre-training via paraphrasing.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Lewis et al. (2020b) Patrick Lewis, Barlas Oguz, Ruty Rinott, Sebastian Riedel, and Holger Schwenk. 2020b.  MLQA: Evaluating cross-lingual extractive question answering.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7315–7330, Online. Association for Computational Linguistics.
  * Longpre et al. (2020) Shayne Longpre, Yi Lu, and Joachim Daiber. 2020.  MKQA: A linguistically diverse benchmark for multilingual open domain question answering.  _CoRR_ , abs/2007.15207.
  * Navigli and Ponzetto (2010) Roberto Navigli and Simone Paolo Ponzetto. 2010.  Babelnet: Building a very large multilingual semantic network.  In _ACL 2010, Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, July 11-16, 2010, Uppsala, Sweden_ , pages 216–225. The Association for Computer Linguistics.
  * Peters et al. (2018) Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2227–2237, New Orleans, Louisiana. Association for Computational Linguistics.
  * Petroni et al. (2020) Fabio Petroni, Patrick Lewis, Aleksandra Piktus, Tim Rocktäschel, Yuxiang Wu, Alexander H. Miller, and Sebastian Riedel. 2020.  How context affects language models’ factual predictions.  In _Automated Knowledge Base Construction_.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick S. H. Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander H. Miller. 2019.  Language models as knowledge bases? In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , pages 2463–2473. Association for Computational Linguistics.
  * Poerner et al. (2020) Nina Poerner, Ulli Waltinger, and Hinrich Schütze. 2020.  E-BERT: Efficient-yet-effective entity embeddings for BERT.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 803–818, Online. Association for Computational Linguistics.
  * Speer et al. (2017) Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.  Conceptnet 5.5: An open multilingual graph of general knowledge.  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA_ , pages 4444–4451. AAAI Press.
  * Wang et al. (2020) Ruize Wang, Duyu Tang, Nan Duan, Zhongyu Wei, Xuanjing Huang, Jianshu Ji, Guihong Cao, Daxin Jiang, and Ming Zhou. 2020.  K-adapter: Infusing knowledge into pre-trained models with adapters.  _Computing Research Repository_ , arXiv:2002.01808.
  * Xiong et al. (2020) Wenhan Xiong, Jingfei Du, William Yang Wang, and Veselin Stoyanov. 2020.  Pretrained encyclopedia: Weakly supervised knowledge-pretrained language model.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Yaghoobzadeh and Schütze (2016) Yadollah Yaghoobzadeh and Hinrich Schütze. 2016.  Intrinsic subspace evaluation of word embedding representations.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 236–246, Berlin, Germany. Association for Computational Linguistics.

Figure 4:  Three randomly sampled data entries from mLAMA per language. Due to the automatic generation of the dataset not all of them are fully correct. Figure 5:  Data samples continued. | en | de | nl | it
---|---|---|---|---
P495: “[X] was created in [Y]” | Japan (170), Italy (56) | Deutschland (217), Japan (70) | Nederland (172), Italië (50) | Italia (167), Giappone (92)
P101: “[X] works in the field of [Y]” | art (205), science (135) | Kunst (384), Film (64) | psychologie (263), kunst (120) | fisiologia (168), caccia (135)
P106: “[X] is [Y] by profession” | politician (423), composer (80) | Politiker (323), Journalist (128) | politicus (339), acteur (247) | giornalista (420), giurista (257)
P1001: “[X] is a legal term in [Y]” | India (12), Germany (11) | Deutschland (36), Russland (9) | Nederland (22), België (12) | Italia (31), Germania (16)
P39: “[X] has the position of [Y]” | bishop (468), God (68) | WW (261), Ratsherr (108) | burgemeester (400), bisschop (276) | pastore ( 289), papa (138)
P527 “[X] consists of [Y]” | sodium (125), carbon (88) | Wasserstof (398), C (49) | vet (216), aluminium (130) | calcio (165), atomo (96)
P1303 “[X] plays [Y]” | guitar (431), piano (165) | Gitarre (312), Klavier (204) | piano (581), harp (42) | arpa (188), pianoforte (139)
P178 “[X] is developed by [Y]” | Microsoft (177), IBM (55) | Microsoft (153), Apple (99) | Microsoft (200), Nintendo (69) | Microsoft (217), Apple (49)
P264 “[X] is represented by music label [Y]” | EMI (267), Swan (32) | EMI (202), Paramount Records (59) | EMI (225), Swan (50) | EMI (217), Swan (99)
P463 “[X] is a member of [Y]” | FIFA (126), NATO (33) | FIFA (118), NATO (38) | FIFA (157), WWE (16) | FIFA (121), NATO (36)
Table 4: Most frequent object predictions (TyQ) in different languages. Some
relations exhibit language specific biases. WW = “Wirtschaftswissenschaftler”.

##  Appendix A Language Bias

Table 4 shows the language bias for 10 relations. For each relation we
aggregated the predictions across all triples and show the most common two
predicted entities together with its count (in brackets). The querying
language clearly affects results. The effect is drastic for relations that ask
for a country (e.g., P495 or P1001). P39 yields very different results without
exhibiting a clear pattern. Other relations such as P463 or P178 are rather
stable.

##  Appendix B Data Samples

Table 4 and Table 5 show randomly sampled entries from the data.

##  Appendix C Pretraining Data

We investigate whether performance across languages is correlated with the
amount of pretraining data for each language. To this end we investigate the
number of articles per language as of January
2021222https://meta.wikimedia.org/wiki/List_of_Wikipedias and p1 for TyQ in
Figure 6. We do not have access to the original pretraining data of mBERT.
Thus, the number of articles we consider in the analysis might be different to
the actual data used to train mBERT.

Figure 6:  Scatter plot of p1 TyQ and number of articles in the corresponding
Wikipedia. There is no clear trend visible.


#  Lower Bounds for Pseudo-Deterministic Counting in a Stream

Vladimir Braverman
Rice University
<EMAIL_ADDRESS>Work partially supported by ONR Award N00014-18-1-2364 and NSF
awards 1652257, 1813487 and 2107239 Robert Krauthgamer
Weizmann Institute of Science
<EMAIL_ADDRESS>Work partially supported by ONR Award
N00014-18-1-2364, by a Weizmann-UK Making Connections Grant, by a Minerva
Foundation grant, and the Weizmann Data Science Research Center.  Aditya
Krishnan
Pinecone
<EMAIL_ADDRESS>Work partially done while the author was at Johns Hopkins
University and supported by the MINDS Data Science Fellowship. Shay Sapir
Weizmann Institute of Science
<EMAIL_ADDRESS>This research was partially supported by the Israeli
Council for Higher Education (CHE) via the Weizmann Data Science Research
Center.

###### Abstract

Many streaming algorithms provide only a high-probability relative
approximation. These two relaxations, of allowing approximation and
randomization, seem necessary – for many streaming problems, both relaxations
must be employed simultaneously, to avoid an exponentially larger (and often
trivial) space complexity. A common drawback of these randomized approximate
algorithms is that independent executions on the same input have different
outputs, that depend on their random coins. _Pseudo-deterministic_ algorithms
combat this issue, and for every input, they output with high probability the
same “canonical” solution.

We consider perhaps the most basic problem in data streams, of counting the
number of items in a stream of length at most $n$. Morris’s counter [CACM,
1978] is a randomized approximation algorithm for this problem that uses
$O(\log\log n)$ bits of space, for every fixed approximation factor (greater
than $1$). Goldwasser, Grossman, Mohanty and Woodruff [ITCS 2020] asked
whether pseudo-deterministic approximation algorithms can match this space
complexity. Our main result answers their question negatively, and shows that
such algorithms must use $\Omega(\sqrt{\log n/\log\log n})$ bits of space.

Our approach is based on a problem that we call _Shift Finding_ , and may be
of independent interest. In this problem, one has query access to a shifted
version of a known string $F\in\\{0,1\\}^{3n}$, which is guaranteed to start
with $n$ zeros and end with $n$ ones, and the goal is to find the unknown
shift using a small number of queries. We provide for this problem an
algorithm that uses $O(\sqrt{n})$ queries. It remains open whether
$\operatorname{poly}(\log n)$ queries suffice; if true, then our techniques
immediately imply a nearly-tight $\Omega(\log n/\log\log n)$ space bound for
pseudo-deterministic approximate counting.

##  1 Introduction

Computing over data streams is a rich algorithmic area that has developed
enormously, and actually started with the simple-looking problem of
approximate counting [Mor78]. Let us first recall the streaming model: The
input is a stream, i.e., a sequence of items, and the goal is to compute a
pre-defined function of these items, such as the number of items (or number of
the distinct items), while making one sequential pass over the stream (or
sometimes a few passes). Many useful functions actually depend on the items as
a multiset, i.e., ignoring their order, or even only on their frequencies
(like the famous $\ell_{p}$-norm of the frequency vector). Another possible
goal is to produce a sample, rather than computing a function, e.g., to
produce a uniformly random item.

The primary measure of efficiency for streaming algorithms is their space
complexity, and for many problems, researchers have designed space-efficient
algorithms, often with space complexity that is even polylogarithmic in the
input size. However, this comes at a price — these algorithms are usually
randomized (and not deterministic) and/or compute an approximate solution
(rather than exact one). In fact, oftentimes both relaxations are needed in
order to achieve low space complexity. For example, to count the number of
items in a stream of length at most $n$, there is a randomized approximation
algorithm using $O(\operatorname{loglog}n)$ bits of space, but algorithms that
are exact or deterministic must use $\Omega(\log n)$ bits [Mor78]. Another
example is the $\ell_{2}$-norm of the frequency vector of items from a ground
set $[d]$ (or equivalently, of a $d$-dimensional vector under a sequence of
additive updates) — there is a randomized approximation algorithm that uses
$O(\log d)$ bits of space, but algorithms that are exact or deterministic must
use $\Omega(d)$ bits of space [AMS96].

Gat and Goldwasser [GG11] initiated the study of _pseudo-deterministic_
algorithms, which informally means that when run (again) on the same input,
with high probability they produce exactly the same output. This notion
combats a potential issue with randomized algorithms, that independent
executions on the same input might return different outputs, depending on the
algorithm’s coin tosses. Many known streaming algorithms suffer from this
issue, which is a serious concern for some users and applications. Pseudo-
deterministic algorithms were later considered in the streaming model by
Goldwasser, Grossman, Mohanty and Woodruff [GGMW20], and these are formally
defined as follows.

######  Definition 1.1.

A streaming algorithm $A$ is _pseudo-deterministic_ (PD) if there is a
function $F(\cdot)$ defined on inputs of $A$ (streams), such that for every
stream $\sigma$,

$\Pr[A(\sigma)=F(\sigma)]\geq 9/10,$

where the probability is over the random choices of the algorithm. We shall
refer to $F$ as the _canonical function_ of algorithm $A$.111 The canonical
function $F$ depends on the order arrival of the stream items. In an
alternative definition, the canonical function depends on the items only as a
multiset, i.e., ignoring their order in the stream. These two definitions are
equivalent in the setting of approximate counting, which is the focus of our
work.

We focus on _estimation problems_ , which ask to approximate a numerical
value, and are very popular in the streaming model. For such problems, the
notion of PD relaxes the exact setting and the deterministic one, since exact
algorithms have one canonical output (the exact numerical value), and hence
they are PD. Thus the known lower bounds for these settings do not apply for
PD algorithms, and a central question, identified in [GGMW20], remains open:

_Are there efficient PD streaming algorithms for estimation problems?_

Currently, no lower bounds are known for natural estimation problems, although
for several search problems, like reporting an element from a stream with
deletions (equivalently, an index from the support of the frequency vector),
it is known that lower bounds for deterministic algorithms extend to PD
algorithms [GGMW20].

###  1.1 Main Result: Approximate Counting

Perhaps the most basic problem in the streaming model is to count the number
of stream items. Exact counting, i.e., computing the number of items exactly,
requires $\Theta(\log n)$ bits of space when the stream has length at most
$n$, even for randomized algorithms with some error probability. Work by
Morris [Mor78], later refined in [Fla85, GS09, NY22], showed that the number
of stream items can be $(1+\epsilon)$-approximated with probability $9/10$
using $O_{\epsilon}(\operatorname{loglog}n)$ bits of space, where $\epsilon>0$
is arbitrary but fixed. Throughout, we refer to multiplicative approximation,
and use the notations $O_{c}(\cdot)$ and $\Omega_{c}(\cdot)$ to hide factors
that are polynomial in $c$. Morris’s algorithm has found many applications,
both in theory and in practice [Lum18, NY22]. An open question stated
explicitly by Goldwasser, Grossman, Mohanty and Woodruff [GGMW20] is whether
there is a PD algorithm for this problem using $O(\operatorname{loglog}n)$
bits of space. We answer their question negatively, by proving the following
lower bound.

######  Theorem 1.2 (Main Result).

For every $c,n>1$, every PD streaming algorithm that $c$-approximates the
number of items in a stream of length at most $(c+1)n$ must use
$\Omega_{c}(\sqrt{{\log n}/{\operatorname{loglog}n}})$ bits of space.

To be more precise, our lower bound is actually $\Omega\big{(}\tfrac{\log
n}{\sqrt{\log n\operatorname{loglog}(cn)}+\log c}\big{)}$, which is still
$\Omega(\sqrt{\tfrac{\log n}{\operatorname{loglog}n}})$ as long as
$c<2^{\sqrt{\log n\operatorname{loglog}n}}$. Previously, there was a large gap
for this problem, between $O(\log n)$ bits (by a deterministic algorithm) and
$\Omega(\operatorname{loglog}n)$ bits (from the randomized setting) [NY22].
See Table 1 for a summary of the known bounds.

Table 1:  Known space bounds (in bits) for $2$-approximate counting in a stream of length at most $n$. Folklore bounds are stated without a reference.  Algorithms | Upper bound | Lower bound
---|---|---
Exact or deterministic | $O(\log n)$ |  | $\Omega(\log n)$ |
Randomized and approximate | $O(\operatorname{loglog}n)$ | [Mor78] | $\Omega(\operatorname{loglog}n)$ | [NY22]
Pseudo-deterministic | $O(\log n)$ |  | $\Omega(\sqrt{{\log n}/{\operatorname{loglog}n}})$ | [Thm. 1.2]
Pseudo-deterministic |  |  | $\Omega(\log n)$ | [GGS23]

Our proof analyzes the promise variant of $c$-approximate counting for streams
of length at most $(c+1)n$, which we denote by $\Pi^{AC}_{c,n}$; this variant
asks to distinguish whether the number of stream items is $\leq n$ or $>cn$
(see Definition 2.1). A crucial property of PD algorithms is that they have to
be PD also for inputs in the range $[n+1,cn]$ (i.e., outside the promise). We
rely on this property of PD algorithms to prove the following result, which
immediately yields Theorem 1.2 as a corollary.

######  Theorem 1.3 (Main Result).

For every $c,n>1$, every PD streaming algorithm for problem $\Pi^{AC}_{c,n}$
must use $\Omega_{c}(\sqrt{{\log n}/{\operatorname{loglog}n}})$ bits of space.

Our proof of Theorem 1.3 appears in Section 4. It is based on a problem that
we call Shift Finding, which may be of independent interest, as it is very
natural and likely to find connections to other problems. In addition, it can
potentially lead to a near-tight $\Omega(\log n/\operatorname{loglog}n)$ lower
bound for PD streaming, by simply improving our algorithmic result for Shift
Finding. A very recent independent work by Grossman, Gupta and Sellke [GGS23]
shows a tight $\Omega(\log n)$ bound for $\Pi^{AC}_{c,n}$, using a very
different technique, which views the PD streaming algorithm as a Markov chain
with a limited number of states.

###  1.2 Main Technique: The Shift Finding Problem

Our main result relies on _algorithms_ for the shift Finding problem
$\Pi^{SF}_{c,n}$, which is defined below. Let us first introduce some basic
terminology. A function $F\mathrel{\mathop{\ordinarycolon}}[m]\to\\{0,1\\}$
can also be viewed as a string $F\in\\{0,1\\}^{m}$, and vice versa, and we
sometimes use these interchangeably. Given $s\in[0,n]$, let the shifted
version of this $F$ be the function
$F_{s}\mathrel{\mathop{\ordinarycolon}}x\mapsto F(s+x)$, with a properly
restricted domain, see Section 2.

######  Definition 1.4 (Shift Finding).

Let $c,n>1$. In problem $\Pi^{SF}_{c,n}$, the input is a string
$P\in\\{0,1\\}^{(c-1)n}$, and one has query access to a string $F_{s^{*}}$
that is the concatenation of $n-s^{*}$ zeros, then $P$, and finally $s^{*}$
ones, for an unknown $s^{*}\in[0,n]$. Thus, a query for $x\in[0,cn]$ returns
$F_{s^{*}}(x)$. The goal is to output $s^{*}$.

The measure of complexity of an algorithm for this problem is the number of
queries that it makes to $F_{s^{*}}$. A randomized algorithm is required to be
correct (in its output $s^{*}$) with probability $9/10$.

This problem may be also of independent interest. In a different variant of
shift finding, the input is a random string
$c\in\mathinner{\left\\{0,1\right\\}}^{n}$ and a vector $x$ that is obtained
from the string $c$ by a cyclic shift $\tau$ and some noise (random bit
flips), and the goal is to compute the shift $\tau$ with high probability.
This problem is related to GPS synchronization, see [HAKI12, AIKH13] for more
details. There is a sublinear time algorithm for this problem, running in time
roughly $O(n^{0.641})$ [AIKH13]. One main difference is that in our Definition
1.4, one string is completely known to the algorithm, and the only concern is
the number of queries to the second string.

####  1.2.1 Connection to PD Counting

We show that an algorithm for Shift Finding ($\Pi^{SF}_{c,n}$) implies a space
lower bound for PD streaming algorithm for counting ($\Pi^{AC}_{c,n}$).

######  Theorem 1.5.

Let $c,n>1$, and suppose that the Shift Finding problem $\Pi^{SF}_{c,n}$
admits a randomized algorithm that makes at most $q=q(c,n)$ queries (possibly
adaptive). Then, every PD streaming algorithm for the approximate counting
problem $\Pi^{AC}_{c,n}$ must use $\Omega(\tfrac{\log n}{\log q})$ bits of
space.

It immediately follows that if the Shift Finding problem $\Pi^{SF}_{c,n}$ can
be solved using $\operatorname{polylog}(n)$ queries (for fixed $c>1$), then PD
approximate counting requires $\Omega(\tfrac{\log n}{\operatorname{loglog}n})$
bits of space. However, our current upper bound for Shift Finding is
$q=O(\sqrt{cn})$ queries (Theorem 1.8) and is not strong enough to yield a
nontrivial lower bound for PD approximate counting.

Therefore, to prove our main lower bound (Theorem 1.3), we revert to a
generalization of Theorem 1.5 where the Shift Finding algorithm is still given
an instance of problem $\Pi^{SF}_{c,n}$ (namely, a string $F$ and query access
to $F_{s^{*}}$), but reports a small set $R\subset[0,n]$ (say of size $|R|\leq
t$) that contains the unknown shift (i.e., $s^{*}\in R$). This algorithm may
be randomized provided that it is PD, and its canonical function maps each
instance of problem $\Pi^{SF}_{c,n}$ to a set $R$ of size $t$ that contains
$s^{*}$.

######  Theorem 1.6.

Let $c,n>1$, and suppose there is a PD algorithm $Q$ that, given an instance
of problem $\Pi^{SF}_{c,n}$, makes at most $q=q(c,n)$ queries (possibly
adaptive) to $F_{s^{*}}$ and its canonical function $M$ maps the input to a
set $R\subset[0,n]$ of size $t=t_{c}(n)$ that contains $s^{*}$. Then every PD
streaming algorithm for problem $\Pi^{AC}_{c,n}$ must use
$\Omega(\tfrac{\log(n/t)}{\log q})$ bits of space.

We use Theorem 1.6, (more precisely its proof arguments rather than its
statement) to prove our main result (Theorem 1.3), see Section 4. At a high
level, the proof of Theorem 1.3 proceeds by splitting into two cases,
depending on the canonical function $F$. Roughly speaking, in one case we show
a Shift Finding algorithm that returns a set of size $t=n/2^{\sqrt{\log n}}$
using $q=O(\log n)$ queries by binary search, and in the other case an
algorithm to find the shift (i.e., $t=1$) with probability $9/10$ using
$q=2^{\sqrt{\log n}}$ uniformly random queries.

As a corollary of Theorem 1.5, we get that the _tracking_ version of
approximate counting must use $\Omega(\log n)$ bits of space, which is tight
with a straightforward deterministic counting. Tracking means that the
algorithm produces an output after every stream item rather than at the end of
the stream, and with probability $9/10$, all the outputs are simultaneously
correct (i.e., approximate the number of items seen so far).

######  Corollary 1.7 (Tracking).

For every $c,n>1$, every PD tracking algorithm that $c$-approximates the
number of items in a stream of length $(c+1)n$ must use $\Omega(\log n)$ bits
of space.

In contrast, for standard randomized algorithms, there is a tracking algorithm
for $(1+\epsilon)$-approximate counting that uses
$O_{\epsilon}(\operatorname{loglog}n)$ bits of space, for any fixed
$\epsilon>0$ [NY22]. Corollary 1.7 follows by an easy modification of the
proof of Theorem 1.5. That proof uses $O(\log q)$ repetitions of a PD
streaming algorithm, and then employs a union bound on $q$ input streams,
which is not necessary for tracking algorithms and thus the bound follows.

A more direct argument is essentially by equivalence to exact counting. For a
stream with $s<n$ items, the state of a PD tracking algorithm with canonical
function $F$ can be used to compute $s$, as follows. Simulate insertion of
more items to the stream until the output of the algorithm changes to $1$
(which corresponds to the first $1$ in $F_{s}$), from which $s$ can be
computed.

####  1.2.2 An Algorithm for Shift Finding

Consider a special case of the Shift Finding problem $\Pi^{SF}_{c,n}$, where
the input string $P$ is a run of zeros followed by a run of ones (viewed as a
function, it is a step function); then the algorithm can perform a binary
search using $O(\log(cn))$ queries, and find the unique location where
$F_{s^{*}}$ switches from value $0$ to $1$, and hence recover $s^{*}$. At the
other extreme, suppose the input string $P$ is random; then with high
probability every set of $O(\log n)$ queries from $P$ (and thus from
$F_{s^{*}}$) will be answered differently (viewed as a string in
$\\{0,1\\}^{O(\log n)}$). Based on these observations, one may hope that
problem $\Pi^{SF}_{c,n}$ admits an algorithm that makes
$\operatorname{polylog}(cn)$ queries. We leave this as an open question and
prove a weaker bound of $O(\sqrt{cn})$ queries.

######  Theorem 1.8 (Shift Finding Algorithm).

There is a deterministic algorithm for problem $\Pi^{SF}_{c,n}$ that makes
$O(\sqrt{cn})$ queries.

A key observation in our result, that may be useful in future work, is that
for every shift $s^{*}$ there is a “short witness” that uses exactly $2$
queries. We formalize this as verifying a given guess $s$ for the shift
$s^{*}$.

######  Lemma 1.9 (Short Witness).

There is a deterministic algorithm that, given as input an instance of problem
$\Pi^{SF}_{c,n}$ and $s<n$, makes $2$ queries to $F_{s^{*}}$ and returns ’yes’
if $s=s^{*}$ and ’no’ otherwise.

The proofs of Theorem 1.8 and Lemma 1.9 appear in Section 5. At a high level,
the Shift Finding algorithm in Theorem 1.8 queries the set
$\\{F_{s^{*}}(0),F_{s^{*}}(\sqrt{cn}),F_{s^{*}}(2\sqrt{cn}),...,F_{s^{*}}(cn)\\}$,
and then uses the short witness (Lemma 1.9) to check every feasible $s\in[n]$
(i.e., that agrees with the query answers). Following an observation by Peter
Kiss, we are able to improve our Shift Finding algorithm to use only
$O((cn)^{1/3}\log n)$ queries; details omitted.

###  1.3 Related Work

##### Pseudo-deterministic algorithms

The notion of pseudo-deterministic algorithms was introduced by [GG11] (they
originally called them Bellagio algorithms), followed by a long sequence of
works that studied it in different models [GGR13, Gro15, GG15, OS17, Hol17,
GGH18, DPV18, OS18, GGH19, GL19, Gol19, GGMW20, LOS21, DPV21, GIPS21, GG21,
DPWV22]. In the streaming and sketching models, [GGMW20] proved strong lower
bounds for finding a non-zero entry in a vector (given in a stream with
deletions), and for sketching $\ell_{2}$-norms. Another related setting is
that of sublinear time computation. Under certain assumptions, PD algorithms
(in the sublinear time region) were shown to admit the following relation with
deterministic algorithms – if for a certain problem there is a PD algorithm
using $q$ queries, then there is a deterministic algorithm using $O(q^{4})$
queries [GGR13]. The techniques of [GGR13] do not seem to extend to streaming
algorithms.

##### Adaptive adversarial streams

In this setting, the stream items are chosen adversarially and depend on past
outputs of the streaming algorithm (i.e., the stream is adaptive) [BJWY22].
This model is considered to be between PD algorithms and the standard
randomized setting, in the sense that for streams of length $m$, amplifying a
PD algorithm to success probability $1-\tfrac{1}{10m}$ (by $O(\log m)$
repetitions and taking the median) guarantees (by a union bound) that the
algorithm outputs the canonical solution after every stream item with
probability $9/10$, thus the adversary acts as an oblivious one (the adversary
knows in advance the output of the streaming algorithm, which is the canonical
function). For approximate counting, adaptive streams and standard (oblivious)
streams are equivalent (since the stream items are identical) and thus admit
an algorithm using $O(\operatorname{loglog}n)$ bits of space.

There is a vast body of work designing algorithms for adaptive streams, but
not much is known in terms of lower bounds. Lower bounds are known for some
search problems, like finding a spanning forest in a graph undergoing edge
insertions and deletions, but also for graph coloring [CGS22]. Regarding
estimation problems, the only lower bound we are aware of is for some
artificial problem [KMNS21]. Recently, Stoeckl [Sto23] showed a lower bound on
streaming algorithms that use a bounded amount of randomness, conditioned on a
lower bound for PD algorithms. In the related model of linear sketching, Hardt
and Woodruff [HW13] showed lower bounds on the dimensions of sketching
algorithms, which applies to many classical problems, like $\ell_{p}$-norm
estimation and heavy hitters.

##  2 Preliminaries

######  Definition 2.1 (Approximate counting).

Let $c,n>1$. In problem $\Pi^{AC}_{c,n}$, the input is a stream of
$l\leq(c+1)n$ identical items. The goal is to output $0$ if $l\leq n$ and $1$
if $l>cn$ (and otherwise the output can be either $0$ or $1$).

Let $A$ be a PD algorithm for problem $\Pi^{AC}_{c,n}$, and let
$F\mathrel{\mathop{\ordinarycolon}}[0,(c+1)n]\to\mathinner{\left\\{0,1\right\\}}$
be the canonical function of $A$. Thus, there is a fixed string
$P\in\\{0,1\\}^{(c-1)n}$ such that

$F(x)=\begin{cases}0&\text{if }x\in[0,n];\\\ 1&\text{if }x\in[cn+1,(c+1)n];\\\
P(x-n)&\text{otherwise.}\end{cases}$

For $s^{*}\in[0,n]$, let
$F_{s^{*}}\mathrel{\mathop{\ordinarycolon}}[0,(c+1)n-s^{*}]\to\mathinner{\left\\{0,1\right\\}}$
be a shifted version of $F$, namely the function
$F_{s^{*}}\mathrel{\mathop{\ordinarycolon}}x\mapsto F(s^{*}+x)$. We use these
notations throughout the paper.

Our proofs are based on a reduction from a simple one-way communication
problem, called MESSAGE and denoted $\Pi^{MSG}_{\Sigma}$, where Alice’s input
$x$ is from an alphabet $\Sigma$ that is fixed in advance, Bob has no input,
and the goal is that Bob outputs $x$ with probability at least $2/3$. It is
well known that this problem requires $\Omega(\log|\Sigma|)$ bits of
communication, even for randomized protocols using shared randomness. We
provide a proof for completeness.

######  Lemma 2.2.

For every alphabet $\Sigma$, every one-way communication protocol (even with
shared randomness) for problem $\Pi^{MSG}_{\Sigma}$ must use
$\Omega(\log|\Sigma|)$ bits of communication.

###### Proof.

Let $\mathcal{A}$ be a protocol for problem $\Pi^{MSG}_{\Sigma}$. For a random
string $r$ representing the randomness of $\mathcal{A}$, let
$\Sigma_{r}\subset\Sigma$ be the set of all $s\in\Sigma$ for which Bob
correctly recovers $s$. Let $r^{*}$ be a string maximizing $|\Sigma_{r}|$,
then by averaging, $|\Sigma_{r^{*}}|\geq\tfrac{2}{3}|\Sigma|$. Consider an
instance of $\mathcal{A}$ that uses $r^{*}$ as its random string. Assume by
contradiction that the number of communication bits is less than
$\log|\Sigma_{r^{*}}|$, then by the pigeonhole principle there are two
distinct inputs $s,s^{\prime}\in\Sigma_{r^{*}}$ such that $\mathcal{A}(s)$ and
$\mathcal{A}(s^{\prime})$ result in the same message. Bob then cannot
distinguish between (i.e., has the same output distribution for) $s$ and
$s^{\prime}$, a contradiction. Hence, the number of bits of communication is
at least $\log|\Sigma_{r^{*}}|=\Omega(\log|\Sigma|)$. ∎

##  3 Lower Bounds for PD Approximate Counting via Shift Finding

In this section, we prove Theorem 1.5. The proof involves three problems from
different settings: (a) PD approximate counting in the streaming model; (b)
Shift Finding in the query-access model; and (c) MESSAGE in one-way
communication with shared randomness. The proof essentially shows that if
there is an algorithm for Shift Finding that makes only $q$ queries and also a
streaming algorithm for PD approximate counting that uses $b$ bits of space,
then MESSAGE can be solved using $O(b\log q)$ bits of communication. Combining
this bound with the well-known lower bound for MESSAGE in Lemma 2.2 yields a
lower bound for $b$.

A core idea in the proof is that an execution of a PD streaming algorithm $A$
for the approximate counting problem $\Pi^{AC}_{c,n}$ on a stream with $s^{*}$
insertions, can be used (even without knowing $s^{*}$, by making additional
insertions and then querying the streaming algorithm $A$) to provide query
access to the shifted function
$F_{s^{*}}\mathrel{\mathop{\ordinarycolon}}x\mapsto F(s^{*}+x)$. This query
access, along with a query-efficient algorithm for the Shift Finding problem
$\Pi^{SF}_{c,n}$, is then used to solve an instance of the MESSAGE problem
$\Pi^{MSG}_{\Sigma}$.

In fact, we prove the following theorem, which holds for each string $F$
separately (rather than a bound that depends on the worst-case $F$), and
yields Theorem 1.5 as an immediate corollary.

######  Theorem 3.1.

Let $A$ be a PD streaming algorithm for problem $\Pi^{AC}_{c,n}$, where
$c,n>1$, and let
$F\mathrel{\mathop{\ordinarycolon}}[0,(c+1)n]\to\mathinner{\left\\{0,1\right\\}}$
be the canonical function of $A$. Suppose that Shift Finding with respect to
this specific $F$ (the problem of finding an unknown shift $s^{*}\in[n]$ with
probability at least $9/10$ given query access to $F_{s^{*}}$) admits a
randomized algorithm that makes at most $q=q(F)$ (possibly adaptive) queries.
Then the streaming algorithm $A$ must use $\Omega(\tfrac{\log n}{\log q})$
bits of space.

###### Proof.

Define algorithm $A^{\prime}$ to be an amplification of $A$ to success
probability $1-1/(10q)$, by running $O(\log q)$ independent repetitions and
reporting their majority. Assume there exists an algorithm $Q$ that for every
$s^{*}\in[n]$, makes at most $q=q(F)$ queries to $F_{s^{*}}$ (possibly
adaptive) and outputs $s^{*}$ with probability at least $9/10$.

Consider an instance of problem $\Pi^{MSG}_{\Sigma}$ with alphabet
$\Sigma=[0,n]$, and consider the following protocol for it. Alice starts an
execution of the streaming algorithm $A^{\prime}$ using the shared randomness,
then takes her input $s^{*}\in\Sigma$ and makes $s^{*}$ stream insertions to
algorithm $A^{\prime}$, and finally sends the state (memory contents) of
$A^{\prime}$ to Bob.

Bob continues the execution of the streaming algorithm $A^{\prime}$ (using the
shared randomness), and uses it to provide query access to $F_{s^{*}}$, as
follows. In order to query $F_{s^{*}}$ at any index $x$, Bob makes a fresh
copy $A_{0}$ of the streaming algorithm $A^{\prime}$, insert $x$ stream items
to algorithm $A_{0}$ and then reads its output. With probability at least
$1-1/(10q)$, the answer that Bob gets is indeed $F_{s^{*}}(x)$ (because the
number of items inserted to this instance of the algorithm is $x+s^{*}$). Bob
uses this query access and his knowledge of $F$ to simulate algorithm $Q$
(with the goal of recovering $s^{*}$).

Consider Bob’s simulation of algorithm $Q$. If $Q$ was executed with true
query access to $F_{s^{*}}$, then it would have had success probability
$9/10$, and would have made a sequence of queries $X_{Q}$ to $F_{s^{*}}$. This
sequence $X_{Q}$ depends only on $F_{s^{*}}$ and the coin tosses of algorithm
$Q$. In particular, revealing $X_{Q}$ (i.e., conditioned on $X_{Q}$) does not
affect the coins of the streaming algorithm $A^{\prime}$, and it still
succeeds with probability at least $1-1/(10q)$. We can thus apply a union
bound to conclude that algorithm $A^{\prime}$ succeeds on all queries $x\in
X_{Q}$ (i.e., outputs the corresponding $F_{s^{*}}(x)$) with probability at
least $1-q\cdot\tfrac{1}{10q}=9/10$. Hence, when Bob simulates algorithm $Q$
using the streaming algorithm $A^{\prime}$, with probability $9/10$ (over the
coins of $A^{\prime}$) the execution is identical to running algorithm $Q$
with true access to $F_{s^{*}}$, which itself succeeds with probability
$9/10$. By a union bound, with probability $8/10$ both algorithm $Q$ and the
streaming algorithm $A^{\prime}$ succeed, in which case Bob recovers $s^{*}$,
and therefore this communication protocol solves problem $\Pi^{MSG}_{\Sigma}$
with alphabet $\Sigma=[0,n]$.

By Lemma 2.2, the message Alice sends must contain $\Omega(\log n)$ bits, and
thus the streaming algorithm $A^{\prime}$ must use $\Omega(\log n)$ bits of
space. Recall that algorithm $A^{\prime}$ consists of $O(\log q)$ copies of
the streaming algorithm $A$ and thus algorithm $A$ must use
$\Omega(\tfrac{\log n}{\log q})$ bits of space. ∎

##  4 Lower Bound for PD Approximate Counting

In this section, we prove Theorem 1.3, i.e., for every $c,n>1$, we prove that
every PD streaming algorithm for the approximate counting problem
$\Pi^{AC}_{c,n}$ must use $\Omega_{c}(\sqrt{\tfrac{\log
n}{\operatorname{loglog}n}})$ bits of space.

Let $F$ be the canonical function of a PD streaming algorithm for problem
$\Pi^{AC}_{c,n}$. Our analysis is split into two cases depending on $F$, which
informally correspond to whether a fixed pattern (like “01”) appears in the
string $F$ at most $t$ times or not. These cases are analyzed using Theorems
1.6 and 3.1. The overall bound will be derived by optimizing the threshold $t$
between the two cases to roughly $t=n/2^{\sqrt{\log n}}$.

###  4.1 Scenario One

In this scenario, there is a specific pattern in $F$ that appears at most $t$
times, where $t=t_{c}(n)$ will be set at the end of our proof. We first
consider the pattern ”01” in $F$, which corresponds to $x\in[0,(c+1)n-1]$ such
that $F(x)=0$ and $F(x+1)=1$, and later generalize this pattern to a broader
family.

######  Lemma 4.1.

If the pattern ”01” appears at most $t$ times in $F$, then every PD streaming
algorithm for problem $\Pi^{AC}_{c,n}$ whose canonical function is $F$ must
use $\Omega(\tfrac{\log(n/t)}{\operatorname{loglog}(cn)})$ bits of space.

###### Proof.

The proof is by a reduction from problem MESSAGE, similarly to the proof of
Theorem 3.1. Perhaps the most delicate part is the definition of an alphabet
$\Sigma$ for the MESSAGE problem $\Pi^{MSG}_{\Sigma}$, and it proceeds as
follows.

Given $s\in[n]$, consider the following execution of Binary Search (B.S.) on
the function $F_{s}$. Initialize $l=0$ and $r=cn+1$, and at every iteration
query $F_{s}(\lfloor\tfrac{l+r}{2}\rfloor)$; if
$F_{s}(\lfloor\tfrac{l+r}{2}\rfloor)=0$, then
$l\leftarrow\lfloor\tfrac{l+r}{2}\rfloor$, otherwise
$r\leftarrow\lfloor\tfrac{l+r}{2}\rfloor$. These iterations maintain the
invariant that $F_{s}(l)=0$ and $F_{s}(r)=1$, and after at most $\log(cn)$
iterations arrive at $r=l+1$ with the pattern ”01”. Define a mapping
$M\mathrel{\mathop{\ordinarycolon}}[n]\to[cn]$ such that $M(s)$ is the
location where the binary search finds a ”01” in $F_{s}$, i.e., the final
index $l$; thus $F(s+M(s))=0$ and $F(s+M(s)+1)=1$.

In order to define an alphabet $\Sigma$, consider a partitioning of $[n]$ to
buckets, defined such that items $s,s^{\prime}$ are from the same bucket $B$
if and only if they are mapped to the same value $M(s)=M(s^{\prime})$. For
every bucket $B$ and every $s,s^{\prime}\in B$, we know from above that
$F(s^{\prime}+M(s))=0$ and $F(s^{\prime}+M(s)+1)=1$, so there are at most $t$
possibilities for $s^{\prime}$ (one of which is $s^{\prime}=s$), and thus the
size of the bucket $|B|\leq t$. Define $\Sigma\subset[n]$ by taking one
representative from each bucket. Thus, every $s_{1}\neq s_{2}\in\Sigma$
satisfy $M(s_{1})\neq M(s_{2})$ and $|\Sigma|\geq n/t$.

Let $A$ be a streaming algorithm whose canonical function is $F$ and let
algorithm $A^{\prime}$ be an amplification of algorithm $A$ that succeeds with
probability $1-1/(10\log(cn))$ (by making $O(\operatorname{loglog}(cn))$
repetitions and taking the majority). Consider an instance of the MESSAGE
problem $\Pi^{MSG}_{\Sigma}$, and proceed similarly to the proof of Theorem
3.1. We provide a self-contained analysis for completeness. Alice and Bob
perform the following protocol. Alice starts an execution of algorithm
$A^{\prime}$ using the shared randomness. For input $s^{*}\in\Sigma$, she
inserts $s^{*}$ stream items to algorithm $A^{\prime}$ and sends the state
(memory contents) of this algorithm $A^{\prime}$ to Bob. In order to get query
access to $F_{s^{*}}$ at index $x$, Bob makes a fresh copy $A_{0}$ of
algorithm $A^{\prime}$, continues the algorithm’s execution (using the shared
randomness), inserts $x$ stream items to algorithm $A_{0}$ and finally reads
its output. Bob uses this query access to simulate the B.S. algorithm on
$F_{s^{*}}$ (with the goal of recovering $M(s^{*})$). He then infers which
bucket corresponds to his result, and outputs the representative of that
bucket (which is $s^{*}$ if he recovers $M(s^{*})$).

If the B.S. algorithm were executed with true query access to $F_{s^{*}}$,
then it would have output $M(s^{*})$ and would have made a sequence of queries
$X_{BS}$ to $F_{s^{*}}$. This sequence depends only on $F_{s^{*}}$, and in
particular independent of the random coins of algorithm $A^{\prime}$. Thus by
a union bound, algorithm $A^{\prime}$ succeeds on all queries $x\in X_{BS}$
(i.e. outputs the corresponding $F_{s^{*}}(x)$) with probability at least
$1-\log(cn)\cdot 1/(10\log(cn))=9/10$. Hence, when Bob simulates the B.S.
algorithm using the streaming algorithm $A^{\prime}$, then with probability
$9/10$ the execution is identical to running the B.S. algorithm with true
query access to $F_{s^{*}}$. Thus with this probability $9/10$, Bob recovers
$M(s^{*})$, and hence outputs $s^{*}$, which concludes the correctness
analysis of the communication protocol.

By Lemma 2.2, the message Alice sends must contain
$\Omega(\log|\Sigma|)\geq\Omega(\log(n/t))$ bits, and thus algorithm
$A^{\prime}$ must use $\Omega(\log(n/t))$ bits of space. Recall that algorithm
$A^{\prime}$ is made of $O(\operatorname{loglog}(cn))$ copies of algorithm $A$
and thus algorithm $A$ must use
$\Omega(\tfrac{\log(n/t)}{\operatorname{loglog}(cn)})$ bits of space. ∎

######  Remark.

This proof can be easily generalized to prove Theorem 1.6. The first extension
is by replacing the B.S. algorithm and the corresponding buckets with any
deterministic algorithm $Q$ that returns a subset containing $s^{*}$. In order
to generalize $Q$ to any PD algorithm $Y$, consider the canonical function of
$Y$ instead of the mapping $M$, and apply the same proof. It holds because the
crucial property of the B.S. algorithm was the existence of the mapping $M$.
Then by an additional union bound, both algorithms $Q$ and $A^{\prime}$
succeed with probability $8/10$ (as in the proof of Theorem 3.1).

We now generalize Lemma 4.1 to a larger family of patterns in $F$, where each
pattern is characterized by a parameter $k\in[n]$, and appears at index
$x\in[0,(c+1)n-k]$ such that $F(x)=0$ and $F(x+k)=1$. These patterns are
allowed to overlap with each other (for different values of $k$). Denote such
a pattern by ”$0?^{k-1}1$”, where each question mark can represent either $0$
or $1$, and the number of question marks is $k-1<n$. A copy of this pattern
can be found in $O(\log\tfrac{n}{k})$ queries to $F_{s^{*}}$ by a binary
search on the grid $(0,k,...,\lceil\tfrac{cn}{k}\rceil k)$, since
$F_{s^{*}}(0)=0$ and $F_{s^{*}}(\lceil\tfrac{cn}{k}\rceil k)=1$. Hence, if
there exists $k$ for which this pattern appears at most $t$ times in $F$, then
the communication protocol above can be adjusted to imply that algorithm $A$
must use at least
$\Omega(\tfrac{\log(n/t)}{\operatorname{loglog}(cn/k)})\geq\Omega(\tfrac{\log(n/t)}{\operatorname{loglog}(cn)})$
bits of space. The only change in the proof is in the number of queries that
Bob makes, which affects the number of repetitions in algorithm $A^{\prime}$,
and thus only affects the $\operatorname{loglog}$ term.

######  Corollary 4.2.

If for some $k\leq n$ the pattern ”$0?^{k-1}1$” appears at most $t$ times in
$F$, then every PD streaming algorithm for problem $\Pi^{AC}_{c,n}$ whose
canonical function is $F$, must use
$\Omega(\tfrac{\log(n/t)}{\operatorname{loglog}(cn)})$ bits of space.

###  4.2 Scenario Two

In this scenario, for every $k\leq n$ the pattern ”$0?^{k-1}1$” appears at
least $t$ times in $F$.

######  Lemma 4.3.

If for all $k\in[n]$, the pattern ”$0?^{k-1}1$” appear at least $t$ times in
$F$, then every PD streaming algorithm for problem $\Pi^{AC}_{c,n}$ whose
canonical function is $F$, must use $\Omega(\tfrac{\log
n}{\log(cn/t)+\operatorname{loglog}n})$ bits of space.

###### Proof.

In this case, there is an algorithm for the Shift Finding problem
$\Pi^{SF}_{c,n}$ using $q=O(\tfrac{cn\log n}{t})$ queries to $F_{s^{*}}$, as
follows.

  1. 1.

let $S=[0,n]$

  2. 2.

repeat the following $\tfrac{10cn\log n}{t}$ times:

    1. (a)

pick $r\in[cn]$ uniformly at random and query $F_{s^{*}}(r)$

    2. (b)

let $S\leftarrow\\{s\in S\mathrel{\mathop{\ordinarycolon}}\
F(s+r)=F_{s^{*}}(r)\\}$

  3. 3.

if $|S|=1$, return $s\in S$; else return FAIL

The final set $S$ clearly contains the shift $s^{*}$. It remains to show that
all $s\neq s^{*}$ are removed from the set $S$ with high probability.

Fix $s\in[n],s\neq s^{*}$. There are $t$ values for $r\in[cn]$ for which
$F(s^{*}+r)\neq F(s+r)$, as follows. Assume without loss of generality that
$s^{*}<s$ and denote $k=s-s^{*}\in[n]$. Let $l$ be a location that corresponds
to the pattern ”$0?^{k-1}1$” in $F$, i.e. $F(l)=0$ and $F(l+k)=1$. If
$l\in[s^{*}+1,s^{*}+cn]$, then there is $r\in[cn]$ such that $s^{*}+r=l$, for
which $F(s^{*}+r)=0\neq F(l+k)=F(s+r)$. There are at least $t$ locations for
this pattern (i.e. possible values for $l$), thus it remains to show that
indeed $l\in[s^{*}+1,s^{*}+cn]$. It must be that $l+k>n$ since $F(x)=0$ for
all $x\leq n$, and similarly $l\leq cn$ since $F(x)=1$ for all $x>cn$. Hence
$l\in[n-k+1,cn]\subset[s^{*}+1,s^{*}+cn]$, and thus there are $t$ values for
$r\in[cn]$ for which $F(s^{*}+r)\neq F(s+r)$ (each value for $r$ corresponds
to a possible value for $l$).

Thus, in each repetition, $s$ is removed from the set $S$ with probability at
least $\tfrac{t}{cn}$. The probability $s$ is not removed after
$\tfrac{10cn\log n}{t}$ repetitions is $(1-\tfrac{t}{cn})^{(10cn\log
n)/t}<\tfrac{1}{n^{2}}$. By a union bound, all $s\neq s^{*}$ are removed with
probability $1-\tfrac{1}{n}$, which concludes the correctness analysis of the
algorithm for problem $\Pi^{SF}_{c,n}$.

By Theorem 3.1, every PD streaming algorithm for the approximate counting
problem $\Pi^{AC}_{c,n}$ with a canonical function $F$ must use
$\Omega(\tfrac{\log n}{\log((cn\log n)/t)})$ bits of space.

∎

###  4.3 Concluding the Proof of Theorem 1.3

Concluding the two scenarios, set $t=n/2^{\sqrt{\log n\cdot\log\log(cn)}}$ and
get by Corollary 4.2 and Lemma 4.3 that every PD streaming algorithm for the
approximate counting problem $\Pi^{AC}_{c,n}$ must use

$\Omega(\min\\{\tfrac{\log(n/t)}{\operatorname{loglog}(cn)},\tfrac{\log
n}{\log((cn/t)\log n)}\\})=\Omega(\tfrac{\log n}{\sqrt{\log
n\operatorname{loglog}(cn)}+\log c})$

bits of space, which boils down to $\Omega(\sqrt{\tfrac{\log
n}{\operatorname{loglog}n}})$ for $c<2^{\sqrt{\log n\operatorname{loglog}n}}$.

##  5 Shift Finding Algorithm

One can hope to prove tighter lower bounds for PD streaming algorithms for the
approximate counting problem $\Pi^{AC}_{c,n}$, and a possible approach is by
solving the Shift Finding problem $\Pi^{SF}_{c,n}$ using
$\operatorname{polylog}n$ queries. Recall that in problem $\Pi^{SF}_{c,n}$,
the input is a string $P\in\mathinner{\left\\{0,1\right\\}}^{(c-1)n}$, which
can be represented by a string $F$ which is a concatenation of $n$ zeros, $P$
and then $n$ ones; and query access to a shifted version of $F$ with shift
$s^{*}$, denoted $F_{s^{*}}$. As stated in Theorem 1.8, we show a
deterministic algorithm for problem $\Pi^{SF}_{c,n}$ using $O(\sqrt{cn})$
queries (Algorithm 1), and we leave open the question whether it is the right
bound. The proof relies on an efficient verification algorithm that for input
$s$, uses $2$ queries and returns ’yes’ if and only if $s=s^{*}$, as stated in
Lemma 1.9 and described next.

###### Proof of Lemma 1.9.

Denote by $l\in[n+1,cn+1]$ the smallest number such that $F(l)=1$, and by
$r\in[n,cn]$ the largest number such that $F(r)=0$. For input $s\in[0,n]$, the
verification algorithm returns ’no’ if $F_{s^{*}}(l-s)=0$ or
$F_{s^{*}}(r-s)=1$, and otherwise returns ’yes’.

If $s=s^{*}$, then $F_{s^{*}}(x-s)=F(x)$ and the verification algorithm
outputs ’yes’. If $s>s^{*}$, then $s^{*}-s+l<l$ and thus
$F_{s^{*}}(l-s)=F(s^{*}-s+l)=0$ and the verification algorithm outputs ’no’.
Similarly, if $s<s^{*}$ then $F_{s^{*}}(r-s)=1$ and the verification algorithm
outputs ’no’. ∎

######  Remark.

There is a randomized algorithm for problem $\Pi^{SF}_{c,n}$ using
$\tilde{O}_{c}(\sqrt{n})$ queries that is similar to the proof of Theorem 1.3
in Section 4. It proceeds by considering those two scenarios. In scenario one,
instead of constructing the set $\Sigma$, query witnesses for all the $t$
possible shifts using $2t$ queries and hence recover the unknown shift
$s^{*}$. In scenario two, the proof of Theorem 1.3 shows how to find the
unknown shift $s^{*}$ in $O(\tfrac{cn}{t}\log n)$ queries with high
probability. Hence, by setting $t=\sqrt{cn\log n}$, this algorithm finds the
unknown shift in $O(\max\\{t+\log(cn),\tfrac{cn}{t}\log n\\})\leq
O(\sqrt{cn\log n})$ queries with high probability.

Next is a slight improvement, a deterministic algorithm in $O(\sqrt{cn})$
queries, proving Theorem 1.8.

Algorithm 1 Deterministic Shift Finding in $O(\sqrt{cn})$ queries

1:$n,c,F$ and query access to $F_{s^{*}}$

2:$s^{*}$

3:$Q\leftarrow(F_{s^{*}}(0),F_{s^{*}}(\sqrt{cn}),F_{s^{*}}(2\sqrt{cn}),...,F_{s^{*}}(cn))$

4:let
$S\leftarrow\mathinner{\left\\{s\in[0,n]\mathrel{\mathop{\ordinarycolon}}\forall
i\in[0,\sqrt{cn}],F_{s}(i\sqrt{cn})=Q(i)\right\\}}$ $\triangleright$ i.e. the
set of all shifts that could have produced $Q$

5:for $s\in S$ do

6: check the witness of $s$

7: if $s=s^{*}$ then return $s$

######  Lemma 5.1.

The set $S$ in Algorithm 1 is of size $O(\sqrt{cn})$.

###### Proof.

Assume by contradiction that $|S|\geq\sqrt{cn}+1$. Hence by the pigeonhole
principle, there exists $s_{1}<s_{2}\in S$ such that
$s_{1}=s_{2}\mod\sqrt{cn}$. Hence for all
$i\in[0,\sqrt{cn}-\tfrac{s_{2}-s_{1}}{\sqrt{cn}}]$,

$\displaystyle
Q(i)=F_{s_{2}}(i\sqrt{cn})=F_{s_{1}}(s_{2}-s_{1}+i\sqrt{cn})=Q(\tfrac{s_{2}-s_{1}}{\sqrt{cn}}+i),$

where the first and last transitions hold since $s_{1},s_{2}\in S$ and
$\tfrac{s_{2}-s_{1}}{\sqrt{cn}}$ is an integer number, and the second
transition is by definition. Thus $Q$ has a period of length
$\tfrac{s_{2}-s_{1}}{\sqrt{cn}}\leq\lfloor\tfrac{s_{2}}{\sqrt{cn}}\rfloor$.
However, for
$i\in[\sqrt{cn}-\lfloor\tfrac{s_{2}}{\sqrt{cn}}\rfloor+1,\sqrt{cn}]$ the
values that $Q$ get are $Q(i)=F_{s_{2}}(i\sqrt{cn})=1$ since
$s_{2}+i\sqrt{cn}\geq cn$; thus all entries in $Q$ are equal $1$, which
contradicts the fact that $Q(0)=0$, and thus completes the proof. ∎

Algorithm 1 returns the shift $s^{*}$ since $s^{*}\in S$ and by the
correctness of the verifier in Lemma 1.9. The number of queries Algorithm 1
makes is $O(|S|+|Q|)=O(\sqrt{cn})$, which proves Theorem 1.8.

## References

  * [AIKH13] Alexandr Andoni, Piotr Indyk, Dina Katabi, and Haitham Hassanieh.  Shift finding in sub-linear time.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 457–465, 2013.  doi:10.1137/1.9781611973105.33.
  * [AMS96] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 20–29, 1996.  doi:10.1145/237814.237823.
  * [BJWY22] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev.  A framework for adversarially robust streaming algorithms.  J. ACM, 69(2):17:1–17:33, 2022.  doi:10.1145/3498334.
  * [CGS22] Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl.  Adversarially robust coloring for graph streams.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, volume 215 of LIPIcs, pages 37:1–37:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ITCS.2022.37.
  * [DPV18] Peter Dixon, A. Pavan, and N. V. Vinodchandran.  On pseudodeterministic approximation algorithms.  In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS, volume 117 of LIPIcs, pages 61:1–61:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.MFCS.2018.61.
  * [DPV21] Peter Dixon, A. Pavan, and N. V. Vinodchandran.  Complete problems for multi-pseudodeterministic computations.  In 12th Innovations in Theoretical Computer Science Conference, ITCS, volume 185 of LIPIcs, pages 66:1–66:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ITCS.2021.66.
  * [DPWV22] Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran.  Pseudodeterminism: promises and lowerbounds.  In STOC ’22: 54th Annual ACM Symposium on Theory of Computing, pages 1552–1565, 2022.  doi:10.1145/3519935.3520043.
  * [Fla85] Philippe Flajolet.  Approximate counting: A detailed analysis.  BIT, 25(1):113–134, 1985.  doi:10.1007/BF01934993.
  * [GG11] Eran Gat and Shafi Goldwasser.  Probabilistic search algorithms with unique answers and their cryptographic applications.  Electron. Colloquium Comput. Complex., TR11-136, 2011.  URL: https://eccc.weizmann.ac.il/report/2011/136.
  * [GG15] Shafi Goldwasser and Ofer Grossman.  Perfect bipartite matching in pseudo-deterministic RNC.  Electron. Colloquium Comput. Complex., TR15-208, 2015.  URL: https://eccc.weizmann.ac.il/report/2015/208.
  * [GG21] Sumanta Ghosh and Rohit Gurjar.  Matroid intersection: A pseudo-deterministic parallel reduction from search to weighted-decision.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 207 of LIPIcs, pages 41:1–41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021\.  doi:10.4230/LIPIcs.APPROX/RANDOM.2021.41.
  * [GGH18] Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden.  Pseudo-deterministic proofs.  In 9th Innovations in Theoretical Computer Science Conference, ITCS, volume 94 of LIPIcs, pages 17:1–17:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.ITCS.2018.17.
  * [GGH19] Michel X. Goemans, Shafi Goldwasser, and Dhiraj Holden.  Doubly-efficient pseudo-deterministic proofs.  arXiv preprint, 2019.  arXiv:1910.00994.
  * [GGMW20] Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff.  Pseudo-deterministic streaming.  In 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, pages 79:1–79:25, 2020.  doi:10.4230/LIPIcs.ITCS.2020.79.
  * [GGR13] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  On the possibilities and limitations of pseudodeterministic algorithms.  In Innovations in Theoretical Computer Science, ITCS, pages 127–138. ACM, 2013.  doi:10.1145/2422436.2422453.
  * [GGS23] Ofer Grossman, Meghal Gupta, and Mark Sellke.  Tight space lower bound for pseudo-deterministic approximate counting.  arXiv preprint, 2023.  arXiv:2304.01438.
  * [GIPS21] Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam.  On the pseudo-deterministic query complexity of NP search problems.  In 36th Computational Complexity Conference, CCC, volume 200 of LIPIcs, pages 36:1–36:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.CCC.2021.36.
  * [GL19] Ofer Grossman and Yang P. Liu.  Reproducibility and pseudo-determinism in log-space.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 606–620. SIAM, 2019.  doi:10.1137/1.9781611975482.38.
  * [Gol19] Oded Goldreich.  Multi-pseudodeterministic algorithms.  Electron. Colloquium Comput. Complex., TR19-012, 2019.  URL: https://eccc.weizmann.ac.il/report/2019/012.
  * [Gro15] Ofer Grossman.  Finding primitive roots pseudo-deterministically.  Electron. Colloquium Comput. Complex., TR15-207, 2015.  URL: https://eccc.weizmann.ac.il/report/2015/207.
  * [GS09] André Gronemeier and Martin Sauerhoff.  Applying approximate counting for computing the frequency moments of long data streams.  Theory Comput. Syst., 44(3):332–348, 2009.  doi:10.1007/s00224-007-9048-z.
  * [HAKI12] Haitham Hassanieh, Fadel Adib, Dina Katabi, and Piotr Indyk.  Faster GPS via the sparse fourier transform.  In The 18th Annual International Conference on Mobile Computing and Networking, Mobicom, pages 353–364. ACM, 2012.  doi:10.1145/2348543.2348587.
  * [Hol17] Dhiraj Holden.  A note on unconditional subexponential-time pseudo-deterministic algorithms for BPP search problems.  arXiv preprint, 2017.  arXiv:1707.05808.
  * [HW13] Moritz Hardt and David P. Woodruff.  How robust are linear sketches to adaptive inputs?  In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, page 121–130, 2013.  doi:10.1145/2488608.2488624.
  * [KMNS21] Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer.  Separating adaptive streaming from oblivious streaming using the bounded storage model.  In Advances in Cryptology - CRYPTO, volume 12827 of Lecture Notes in Computer Science, pages 94–121. Springer, 2021.  doi:10.1007/978-3-030-84252-9\\_4.
  * [LOS21] Zhenjian Lu, Igor Carboni Oliveira, and Rahul Santhanam.  Pseudodeterministic algorithms and the structure of probabilistic time.  In STOC ’21: 53rd Annual ACM Symposium on Theory of Computing, pages 303–316, 2021.  doi:10.1145/3406325.3451085.
  * [Lum18] Jérémie O. Lumbroso.  How Flajolet processed streams with coin flips.  arXiv preprint, 2018.  arXiv:1805.00612.
  * [Mor78] Robert Morris.  Counting large numbers of events in small registers.  Commun. ACM, 21(10):840–842, 1978.  doi:10.1145/359619.359627.
  * [NY22] Jelani Nelson and Huacheng Yu.  Optimal bounds for approximate counting.  In Proceedings of the 41st ACM Symposium on Principles of Database Systems, PODS, page 119–127, 2022.  doi:10.1145/3517804.3526225.
  * [OS17] Igor Carboni Oliveira and Rahul Santhanam.  Pseudodeterministic constructions in subexponential time.  In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, STOC, pages 665–677, 2017.  doi:10.1145/3055399.3055500.
  * [OS18] Igor Carboni Oliveira and Rahul Santhanam.  Pseudo-derandomizing learning and approximation.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 116 of LIPIcs, pages 55:1–55:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018\.  doi:10.4230/LIPIcs.APPROX-RANDOM.2018.55.
  * [Sto23] Manuel Stoeckl.  Streaming algorithms for the missing item finding problem.  In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 793–818, 2023.  doi:10.1137/1.9781611977554.ch32.