# Streaming algorithms for the missing item finding problem

Manuel Stoeckl Department of Computer Science, Dartmouth College.
This work was supported in part by the National Science Foundation under award
2006589.

###### Abstract

Many problems on data streams have been studied at two extremes of difficulty:
either allowing randomized algorithms, in the static setting (where they
should err with bounded probability on the worst case stream); or when only
deterministic and infallible algorithms are required. Some recent works have
considered the adversarial setting, in which a randomized streaming algorithm
must succeed even on data streams provided by an adaptive adversary that can
see the intermediate outputs of the algorithm.

In order to better understand the differences between these models, we study a
streaming task called “Missing Item Finding”. In this problem, for $r<n$, one
is given a data stream $a_{1},\ldots,a_{r}$ of elements in $[n]$, (possibly
with repetitions), and must output some $x\in[n]$ which does not equal any of
the $a_{i}$. We prove that, for $r=n^{\Theta(1)}$ and
$\delta=1/\mathrm{poly}(n)$, the space required for randomized algorithms that
solve this problem in the static setting with error $\delta$ is
$\Theta(\mathrm{polylog}(n))$; for algorithms in the adversarial setting with
error $\delta$, $\Theta((1+r^{2}/n)\mathrm{polylog}(n))$; and for
deterministic algorithms, $\Theta(r/\mathrm{polylog}(n))$. Because our
adversarially robust algorithm relies on free access to a string of $O(r\log
n)$ random bits, we investigate a “random start” model of streaming algorithms
where all random bits used are included in the space cost. Here we find a
conditional lower bound on the space usage, which depends on the space that
would be needed for a pseudo-deterministic algorithm to solve the problem. We
also prove an $\Omega(r/\mathrm{polylog}(n))$ lower bound for the space needed
by a streaming algorithm with $<1/2^{\mathrm{polylog}(n)}$ error against
“white-box” adversaries that can see the internal state of the algorithm, but
not predict its future random decisions.

##  1 Introduction

A streaming algorithm is one which processes a long sequence of input data and
performs a computation related to it. In general, we would like such
algorithms to use as little memory as possible – preferably far less than the
length of the input – while producing incorrect output with as low a
probability as possible. For some problems, there is a space-efficient
deterministic algorithm, which works for all possible inputs; but many others
require randomized algorithms which, for any input, have a bounded probability
of failure.

In the _adversarial setting_[BJWY20], one considers the case where a
randomized algorithm is processing an input stream that is produced in real
time, and furthermore the algorithm continually produces outputs depending on
the partial stream that it has seen so far. It is possible that the outputs of
the streaming algorithm will affect the future contents of the input stream;
whether by accident or malice, this feedback may yield an input stream for
which the randomized algorithm gives incorrect outputs. Thus, in the
adversarial setting, we require that an algorithm has a bounded probability of
failure, even when the input stream is produced by an adversary that can see
all past outputs of the algorithm.

The extent to which an algorithm is vulnerable to adversaries depends
critically on the use of randomness by the algorithm. If, given a randomized
algorithm that has nonzero failure probability on any fixed input stream, an
adversary somehow manages to determine all the past and future random choices
made by an instance of the the algorithm, then the adversary can determine a
specific continuation of the input stream on which the instance fails.
Algorithms that are robust to adversaries often prevent the adversary from
learning any of their important random decisions, and ensure that the
decisions which are revealed do not affect the future performance of the
algorithm. For example, [BJWY20] mentions a sketch-switching method in which a
robust algorithm maintains multiple independent copies of a non-robust
algorithm; it emits output derived from one non-robust instance until it
reaches the point where an adversary might make the instance fail, at which
point the algorithm switches to another instance, none of whose random choices
have been revealed to the adversary yet.

Recent research has introduced models with requirements stronger than
adversarial robustness. In the white-box streaming model[AB+22], algorithms
must avoid errors even when the adversary can see the current state of the
algorithm (i.e, including past random decisions), but not future random
decisions. In the pseudo-deterministic model[GGMW20], streaming algorithms
should with high probability always give the same output for a given input;
such algorithms are automatically robust against adversaries, because
(assuming the algorithm has not failed) the outputs of the algorithm reveal
nothing about any random decisions made by the algorithm.

In order to better understand the differences between all these models, we
study a streaming problem known as Missing Item Finding (mif). This problem is
perhaps the simplest search problem for data streams where the space of
possible answers shrinks as the stream progresses. For parameters $r<n$, given
an data stream $a_{1},\ldots,a_{r}$ of length $r$, where each element $e_{i}$
is an integer in the range $[n]$, the goal of the $\textsc{mif}(n,r)$ problem
is to identify some integer $x\in[n]$ for which, for all $i\in[r]$, $x\neq
a_{i}$.

This problem is of interest because it has significantly different space
complexities for regular randomized streaming algorithms, adversarially robust
streaming algorithms, and deterministic streaming algorithms. Surprisingly,
our adversarially robust algorithm when $r=\sqrt{n}$ needs oracle access to
$\widetilde{O}(\sqrt{n})$ random bits, but only $\widetilde{O}(\log n)$ random
bits of mutable memory. One of the main open problems left by our work is
whether this is necessary. Our white-box model lower bound shows that the
algorithm must make at least _some_ random decisions that remain hidden from
the adversary, and a conditional lower bound shows that, if the pseudo-
deterministic space complexity of $\textsc{mif}(n,\sqrt{n})$ is
$\widetilde{\Omega}(\sqrt{n})$, then the robust algorithm actually must use
$\widetilde{\Omega}(n^{1/4})$ bits of space, including random bits.

###  1.1 Our results and contributions

Our results – a series of upper and lower bounds for space complexities of
$\textsc{mif}(n,r)$ in various different models are given in Table 1. For a
more precise description of the models and of what guarantee exactly $\delta$
is associated with in each case, see Section 3.

Model |  Lower bound |  Upper bound |  Source
---|---|---|---
Classical |  $\Omega(\sqrt{\frac{\log(1/\delta)}{\log(n)}}+\frac{\log(1/\delta)}{(\log n)(1+\log(n/r))})$ ${\text{if }\delta\geq 1/n^{r}}$ |  $\min(r,\frac{\log(1/\delta)}{\log(n/r)})$ |  Thm 5, Thm 6
Adv. Robust |  $\Omega(\frac{r^{2}}{n}+\log(1-\delta))$ |  $O(\min(r,\left(1+\frac{r^{2}}{n}+\ln\frac{1}{\delta}\right)\cdot\log r))$ |  Thm 7 , Thm 8
Zero error $\star$ |  $\Omega(\frac{r^{2}}{n})$ |  $O(\min(r,(1+\frac{r^{2}}{n})\log r)$ |  Thm 9, Thm 10
Deterministic |  $\Omega(\sqrt{r}+\frac{r}{1+\log(n/r)})$ |  $O(\sqrt{r\log r}+\frac{r\log r}{\log n})$ |  Thm 11, Thm 12,
White box |  $\Omega(r/(\log n)^{4})$ ${\text{if }\delta\leq 1/n^{O(\log n)}}$ |  (see deterministic) |  Thm 13
Random start |  $\Omega(\sqrt{r}/\operatorname{polylog}n)$, assuming Pseudo-deterministic algs require $\Omega(r/\operatorname{polylog}n)$ bits |  $O((\sqrt{r}+r^{2}/n)\log n)$ |  Thm 16, Thm 17
Table 1:  Table summarizing the upper and lower bounds on the space complexity
of algorithms for $\textsc{mif}(n,r)$ in various models. $\delta$ is the worst
case error – see Section 3 for what this means in the different models.
$\star$: Unlike the other models, the complexity bounds for the zero error
case are defined using of the _expected_ algorithm space usage, not the worst-
case space usage.

We shall highlight some of the more novel results in what follows:

  * •

Our adversarially robust algorithm for $\textsc{mif}(n,r)$ uses its oracle-
type access to random bits to keep track of a list $L$ of outputs that it
could give. At each point in time, Algorithm 3 outputs the first element of
$L$ which is still available. An adversary can choose to make the algorithm
move to the next list element, but it cannot reliably provide an element from
$L$ that it has not yet seen. For the algorithm, switching to the next list
element is easy – it just increments a counter – but keeping track of future
intersections between the $L$ and the stream requires that it record each
intersecting element; fortunately, even with an adversary there will not be
too many such intersections.

  * •

Our deterministic algorithm for $\textsc{mif}(n,r)$ uses the (missing-)
pigeonhole principle multiple times, and stays within a factor $\log r$ of the
space lower bound. Algorithm 4 proceeds in several stages; in each stage, it
considers a partition of the input space into a number of different parts, and
maintains a bit vector keeping track of which part contains an element from
the stream that arrived in the current stage. When there is exactly one part
left, the algorithm remembers that part, discards the bit vector, and moves on
to the next stage and a new partition of the input space. With suitably chosen
partitions, the intersection of all the remembered parts from the different
stages will be nonempty and disjoint from each element of the stream. The
algorithm then reports an element from this intersection.

  * •

Our white-box lower bound proof establishes an adversary that samples its next
batch of inputs using a distribution $\nu$ over $[n]$ which is chosen so that
the algorithm will also produce outputs distributed according to $\nu$. This
is done using recursive applications of Brouwer’s fixed point theorem: for
example, at the base level, we can use it because the map from the
distribution on $[n]$ out of which the remaining input elements are sampled,
to the distribution of the final algorithm output, is a continuous map from
the space of distributions on $[n]$ to itself. Note that if $\nu$ picks some
element with probability $\geq 2/3$, then the algorithm will also output that
element with probability $\geq 2/3$, leading to a $\geq 1/3$ chance that the
algorithm incorrectly emits an output that it received in the stream. We then
show that, if a white box algorithm using less space than our lower bound
exists, then said algorithm will fail with $\geq 1/2^{O((\log n)^{2})}$
probability. This follows by an inductive argument which shows that, at any
point in the stream, either the algorithm will make a mistake with significant
probability, or there is a large enough chance that the next distribution
which the adversary picks will be more “concentrated” than before, as measured
by an $\ell_{p}$ norm for a value of $p$ slightly larger than 1. As
distributions cannot be infinitely “concentrated”, it follows that the
algorithm will eventually make a mistake with some low probability.

  * •

Our conditional lower bound proof for the “random start” model, relies on the
observation that at a given point in the stream, either the adversary is able
to provide an input where it learns a lot about the initial random bits of the
algorithm, or the algorithm, because it reveals very little about its internal
randomness, also must consistently produce the same output at some point, in
response to the same input. We can use this behavior to construct a pseudo-
deterministic algorithm which works on a shorter input stream.

The rest of this paper is organized as follows. Related work is described in
Section 2. Detailed descriptions of the models for streaming algorithms are
given in Section 3. Sections 4 through 9 contain the main results of this
paper, organized according to the rows of Table 1; they can be read in any
order.

##  2 Related work

The Missing Item Finding problem appears to have been first studied by
[Tar07]. While they primarily consider the problem of finding a duplicate
element in a stream of $m>n$ elements chosen from $[n]$, most of their results
also apply to $\textsc{mif}(n,n-1)$. For example, their multi-pass duplicate
finding algorithms can easily be translated to multiple pass algorithms to
find a missing element. Their main results also hold: they find an
deterministic streaming algorithm for $\textsc{mif}(n,n-1)$ using $O(\log n)$
bits of space must make $\Omega(\log n/\log\log n)$ passes over the stream,
and claim that a single-pass deterministic algorithm for $\textsc{mif}(n,n-1)$
requires at least $2^{n}-1$ states.111As Algorithm 1 uses exactly $2^{n-1}$
states for $\textsc{mif}(n,n-1)$, the value $2^{n}-1$ may be a typo.

A variation on the Missing Item Finding problem, that forbids repeated
elements in the input stream, was briefly studied in the first section of
[Mut05]. The paper mentions that for any $k\geq 1$, on a stream encoding a
subset of $[n]$ of size $n-k$, it is possible to recover the remaining $k$
elements with a sketch of size $O(k\log n)$. The paper [CGS22] also briefly
mentions a variant of Missing Item Finding to illustrate an exponential gap
between space usage for regular randomized and adversarially robust streaming
algorithms. For the problem where the stream can list any strict subset $S$ of
$[n]$, and one must recover a single element not in $S$, they observe that
there is a randomized algorithm which uses an $L_{0}$-sampling sketch to solve
the problem in $O((\log n)^{2}))$ space; but any adversarially robust
algorithm that succeeds with high probability needs $\Omega(n)$ bits.

If we were to extend the Missing Item Finding problem to turnstile streams,
then we would end up with something opposite to the “support-finding”
streaming problem. In the support-finding problem, the algorithm is given a
turnstile stream of updates to a vector $x\in\mathbb{Z}^{[n]}$; on querying
the algorithm, it must return any index $i\in[n]$ where $x_{i}\neq 0$.
[KNP+17] find that this problem – and the harder $L_{0}$ sampling problem,
where one must find a uniformly random element of the support of $x$ – have a
space lower bound of
$\Omega\left(\min\left(n,\log\frac{1}{\delta}(\log\frac{n}{\log(1/\delta)})^{2}\right)\right)$.
This is close to [JST11]’s $L_{0}$ sampling algorithm which uses
$O(\log\frac{1}{\delta}(\log n)^{2})$ bits of space.

The paper [MN22] studies a two player game that is similar to Missing Item
Finding. Here there are two players, a “Dealer” and a “Guesser”: for each of
$n$ turns, the players simultaneously do the following: the Dealer chooses a
number from $[n]$ that it has not picked so far, and the Guesser guesses a
number in $[n]$. The goal of the Guesser is to maximize expected score, the
number of times their number matches the Dealer’s choice; the Dealer tries to
minimize the score. The paper proves upper and lower bounds on the expected
score, for a number of scenarios. Notably, a Guesser that is limited to
remember only $m$ bits of information can do much better against a static
Dealer (that chooses a hard ordering of numbers at the start of the game) than
against an adaptive Dealer (that may choose the next number depending on the
guesses made by the Guesser.) For example, $m=O((\log n)^{2})$ suffices for an
expected score of $\Omega(\log n)$ against a static Dealer, but there exists
an adaptive Dealer which limits any Guesser’s expected score to $(1+o(1))\ln
m+O(\log\log n)$. The objectives of the Guesser and Dealer are similar to
those of the algorithm and adversary in Missing Item Finding: the Guesser
tries to avoid, if possible, guessing any value that the Dealer has revealed
before; while the Dealer tries to ensure the Guesser chooses that the Dealer
had already sent before. However, unlike Missing Item Finding, the Dealer-
Guesser game requires that numbers dealt never be repeated and that all
numbers be used, which makes it much easier to identify a number that will be
dealt in the future.

In the Mirror Game of [GS18], there are two players, Alice and Bob who
alternately declare numbers from the set $[2n]$. The players lose if they
declare a number that has been declared before. Since Alice goes first, even
if Bob can only remember $O(\log n)$ bits about the history of the game, Bob
still has a simple strategy that will not lose. On the other hand, [GS18]
prove that in order for Alice to guarantee a draw against Bob, they require
$\Omega(n)$ bits of memory. If a low probability of error is acceptable,
[Fei19] provide a randomized strategy for Alice with $O((\log n)^{3})$ bits of
memory that draws with high probability – but this requires oracle access to a
large number of random bits, or cryptographic assumptions. [Fei19] and [MN22]
ask whether there is a strategy using $O(\operatorname{polylog}n)$ bits of
memory and of randomness. (Again, the objective of Alice in this game is quite
similar to that of the algorithm in Missing Item Finding – but numbers are
never repeated, and all numbers in $[2n]$ are used by the end of the game.)

The problem of constructing an adversarially resilient Bloom filter is
addressed by [NY19]. Here one seeks a an “approximate set membership” data
structure, which is initialized on a set $S$ of size $n$, and thereafter
answers queries of the form “is $x\in S$” with false positive error
probability $\epsilon$. An implementation of this structure is adversarially
resilient if the false positive probability of the last element in the
sequence is still $\leq\epsilon$ when the adversary chooses the sets $S$, and
adaptively chooses the sequence of $t$ elements to query. In addition to lower
and upper bound results conditional on the existence of one-way functions,
[NY19] find a construction for an adversarially resilient bloom filter using
$O(n\log 1/\epsilon+t)$ bits of memory.

There are many papers on the topic of adversarially robust streaming. Among
them, we mention [HW13], who prove that linear sketches on turnstile streams
are not, in general, robust against adversaries. [BY20] find that algorithms
based on finding a representative random sample of the elements in a stream
may need only slight modification to work with adaptive adversaries; [BJWY20]
establish general methods to convert streaming algorithms with real valued
output that are not robust against adversaries to ones which are, in exchange
for an increase in space usage. [HKM+20] improve on the space tradeoff of this
result by using differential privacy. [WZ22] improve the space/approximation
factor tradeoffs for adversarially robust algorithms on tasks like $F_{p}$
estimation.

The thread of finding separations between the space needed for classical
streaming and for adversarially robust streaming has been pursued by [KMNS21],
who construct a problem whose classical and adversarially robust space
complexities are exponentially separated. [CGS22] mention that this also holds
for the variant of Missing Item Finding mentioned above, and prove a
separation for the adversarially robust space complexity of graph coloring on
insertion streams.

Pseudo-deterministic streaming algorithms were first studied by [GGMW20]; the
paper finds a separation between the classical and pseudo-deterministic memory
needed for the task of finding a nonzero entry of a vector given by turnstile
updates from a stream, among other problems. While it is not a streaming task,
the Find1 query problem – in which one is given a bit vector $x$ with
$\geq\nicefrac{{1}}{{2}}$ density of ones, and must find an index $i$ where
$x_{i}=1$ by querying coordinates – has been found to require significantly
more queries in the pseudo-deterministic case than in the general randomized
case [GIPS21].

Streaming algorithms robust against white box adversaries were considered by
[AB+22]; they rule out efficient white-box adversarially robust algorithms for
tasks like $F_{p}$ moment estimation, while finding algorithms for heavy-
hitters-type problems. They also show how to reduce white-box adversarially
robust algorithms to deterministic 2-party communication protocols, where
lower bounds may be easier to prove.222Unfortunately, for Missing Item
Finding, the natural 2-party communication game is
$\textsc{avoid}(n,r/2,r/2)$, whose deterministic communication lower bound is
almost the same as the randomized lower bound. See Section 3.2. In contrast,
our deterministic and white box lower bounds both use $O(\log n)$
players/adaptive steps.

The Missing Item Finding problem has connections to graph streaming problems.
Just as the $L_{0}$-sampling problem has been used by streaming algorithms
that find a structure in a graph, behaviors like those of the Missing Item
Finding problem appear in algorithms that look for a structure which is not in
a graph. Specifically, the graph coloring problem is equivalent to finding a
small collection of cliques which cover all vertices but do not include any
edge in the graph. [ACK19] proved that general randomized streaming algorithms
can $\Delta+1$ color a graph in $\widetilde{O}(n)$ space, where $n$ is the
number of vertices. [CGS22] showed that adversarially robust streaming
algorithms in $\widetilde{O}(n)$ space must use at least $\Delta^{2}$ colors
for a graph of maximum degree $\Delta$; and [ACS22] proved that deterministic
streaming algorithms using $\widetilde{O}(n)$ space must use
$\exp(\Delta^{\Omega(1)})$ colors. The papers [CGS22] and [ACS22] are
noteworthy in particular because their lower bound proofs use essentially the
same arguments as this paper’s lower bound proofs for Missing Item Finding.
(In fact, our proof of Theorem 7 was inspired by the [CGS22]’s proof, while
Theorem 11 was independently developed.) Because of this, we suspect that this
paper’s white box lower bound will have an analogue for graph coloring.

##  3 Preliminaries

#### Notation

In this paper, following standard convention, $[n]$ is the set
$\\{1,2,\ldots,n\\}$, and $\binom{X}{k}$ is shorthand for the set of all
subset of $X$ of size $k$. For a finite set $Y$, we let $\triangle Y$ be the
set of all probability distributions over $Y$. For $\pi$ a probability
distribution over $Y$, we write $\alpha\sim\pi^{k}$ to mean that $\alpha\in
Y^{k}$ and each coordinate of $\alpha$ is chosen independently at random
according to $\pi$. For some $x\in Y$, the distribution $\mathbbm{1}_{y}$ is
value $1$ on $y$ and value $0$ everywhere else; drawing a sample from this
distribution will always result in $y$. The $p$-norm of a distribution $\phi$
on $Y$ is written as ${\left\|{\phi}\right\|}_{p}:=\left(\sum_{i\in
Y}\phi(i)^{p}\right)^{1/p}$. The notation $[t]^{\star}$ gives the set of all
sequences of elements from $t$, of any length. The empty sequence is written
$\epsilon$; a sequence $s\in[t]^{\star}$ may be written as
$(s_{1},s_{2},\ldots,s_{k})$, in which case its length $|s|=k$. To concatenate
two sequences $a$ and $b$, we write “$a.b$”. $\widetilde{O}(x)$ means
$O(x\operatorname{polylog}(x))$, and $\widetilde{\Omega}(x)$ means
$\Omega(x/\operatorname{polylog}(x))$,

#### A simple algorithm

While in most cases there are more efficient alternatives, this algorithm for
$\textsc{mif}(n,r)$ is particularly simple:

Algorithm 1 A simple deterministic streaming algorithm for $\textsc{mif}(n,r)$

1:Initialization:

2:$x\leftarrow\\{0,\ldots,0\\}$, a vector in $\\{0,1\\}^{[r]}$

3:

4:Update($e\in[n]$):

5:if $e\leq r$ then

6: $x_{e}\leftarrow 1$

7:

8:Query:

9:if $\exists j\in[r]:x_{j}=0$ then

10: output: $j$

11:else

12: output: $r+1$

###  3.1 Models for streaming algorithms

We now precisely define the models of streaming computation considered in this
paper. We classify the models by the type of randomness used, the measure of
the cost of the algorithm, the setting in which they are measured, and by any
additional constraints.

#### Randomness

A streaming algorithm for $\textsc{mif}(n,r)$ has a set $\Sigma$ of possible
states; a possibly random initial state $s_{\mathrm{init}}\in\Sigma$, a
possibly random transition function $\tau:\Sigma\times[n]\rightarrow\Sigma$,
and a possibly random output function $\omega:\Sigma\rightarrow[n]$. The
models of this paper will use the following four variations:

  1. 1.

Random oracle: The initial state, transition function, and output function may
all be random and correlated; i.e, there is a space $\Omega$ and random
variable $R$ on that space for which $s_{\mathrm{init}}$ is a function of $R$,
and $\tau(s,a)=f(s,a,R)$ for some deterministic function
$f:\Sigma\times[n]\times\Omega\rightarrow\Sigma$, and $\omega(s)=g(s,R)$ for
some deterministic function $g:\Sigma\times\Omega\rightarrow[n]$. We can view
this as the algorithm having access to an oracle for all of its operations,
which provides the value of the variable $R$.

  2. 2.

Random tape: In this case, the initial state, transition function, and output
function are all random, but they are uncorrelated; each step $i$ of the
algorithm has associated random variables $R_{i,\tau}$ and $R_{i,\omega}$, and
all of these variables are independent of each other and of the initial state
$s_{\mathrm{init}}$. The transition function of the algorithm is
$\tau(s,a)=f(s,a,R_{i,\tau})$ for some $f$, and the output function is
$\omega(s)=g(s,R_{i,\omega})$ for some $g$. If the algorithm visits a state
twice, the transitions and outputs from that state will be independent.
Intuitively, with this type of access to randomness, the algorithm can always
sample fresh random bits (i.e, reading forward on a tape full of random bits),
but cannot remember them for free.

  3. 3.

Random seed: Here the initial state $s_{\mathrm{init}}$ may be chosen
randomly, but the transition function and output function are deterministic.
The algorithm only has access to the randomness it had when it started.

  4. 4.

Deterministic: The initial state is fixed, and the transition function and
output function are deterministic.

These variations are listed in decreasing order of strength; the random oracle
model can emulate the random tape model, which is stronger than the random
seed model, which is stronger than the deterministic model. Note that the
random oracle model, while inconvenient to implement exactly due to the need
to store all the random bits used, can be approximated in practice, since a
cryptographically secure random number generator can be used to generate all
the random bits from a small random seed.333As the space cost of this seed can
be shared between all tasks performed by a computer, we do not account for it
in the space cost estimates for this paper. Of course, if modern CSPRNGs based
on functions like AES are broken, or one-way functions are proven not to
exist, then the random oracle model may prove unreasonable.

#### Cost measure

In this paper, the space cost of an algorithm is the worst case value, over
all possible streams or adversaries, of either the _maximum_ number of bits
used by the algorithm, or the _expected_ number of bits used by the algorithm.
The number of bits required is determined by a prefix-free encoding of the set
$\Sigma$ of states as strings in $\\{0,1\\}^{\star}$; for most models, we
measure the maximum number of bits used, which is
${\left\lceil{\log|\Sigma|}\right\rceil}$ for the best encoding.

#### Setting

The cost of an algorithm, and its probability of an error, are measured
against the type of inputs that it is given.

  1. 1.

Static: In the static setting, the algorithm should give an incorrect output,
on being queried at the end of the stream, with probability $\leq\delta$, when
it is given any fixed input stream.444This is a weaker condition than
requiring that the entire sequence of intermediate outputs of the algorithm is
correct; however, our lower bounds in static and white-box adversarial
settings only require this weaker condition.

  2. 2.

Adversarial: In the adversarial setting, we consider the algorithm as being
part of a two player game between it and an adversary; the algorithm receives
a sequence of elements $e_{1},\ldots,e_{r}$ from the adversary, and after each
element $e_{i}$, the algorithm shall produce an output $o_{i}$ corresponding
to the sequence $e_{1},\ldots,e_{i}$. The adversary chooses input $e_{i}$
based on the transcript $o_{0},e_{1},o_{1},e_{2},\ldots,o_{i-1}$ that has been
seen so far. The probability that the sequence of outputs produced by the
algorithm has an error should be be $\leq\delta$, for any adversary.

  3. 3.

White box adversarial: This is similar to the adversarial setting, except that
here the adversary chooses the next input $e_{i}$ as a function of the current
state $s_{i}$ of the algorithm. Here, the probability that the algorithm
should make a mistake when producing an output at the end of the stream should
be $\leq\delta$.

#### Extra constraints

A streaming algorithm may be required to be pseudo-deterministic; in other
words, for any input stream $\sigma=e_{1},\ldots,e_{r}$, there should be a
corresponding output $o_{\sigma}$ of the algorithm for which the algorithm is
considered to have made a mistake if it does not output $o_{\sigma}$. In other
words, the algorithm should (with probability $\geq 1-\delta)$ behave as if it
were deterministic.

A noteworthy constraint which we do not consider in the following set of
models, is the requirement that the algorithm detects when its next output is
not certain to be correct, and if so, aborts instead of producing the wrong
value. Most of the algorithms presented in this paper already have this
property – the one exception, Algorithm 2, can be patched to do so at the cost
of an extra bit of space.

#### Models

The models of this paper are described by the following table:

Model | Setting | Randomness | Cost | Extra conditions
---|---|---|---|---
Classical | Static | Oracle | Maximum space |
Robust | Adversarial | Oracle | Maximum space |
Zero error | Static | Oracle | Expected space | $\delta=0$
Deterministic | Static | Deterministic | Maximum space |
White box robust | White-box adv. | Tape | Maximum space |
Pseudo-deterministic | Static | Oracle | Maximum space | Pseudo-deterministic
Random start | Adversarial | Seed | Maximum space |

A brief note on the “Zero error” model; this is a special case where the
algorithm may be randomized, but is required to always give correct output for
any input stream; unlike the deterministic model, the cost of the algorithm is
the _expected_ number of bits of space used by the algorithm. We include this
model because, in many cases, a computer may run many independent instances of
a streaming algorithm, and it is often more important that the instances do
not fail than that they hold to strict space limits. In this scenario, as long
as the expected space used by each algorithm is limited, and the worst case
space usage is not too extreme, by the Chernoff bound it is unlikely that the
total space used by all the instances exceeds the expected space by a
significant amount. Unlike the case for time complexity, where a Las-Vegas
algorithm can be obtained by repeating a Monte-Carlo algorithm until the
solution is verifiably correct, there is no simple way to construct a single-
pass, zero-error streaming algorithm from one with nonzero error.

We use the following notation for the space complexities of these models. The
$\delta$-error space complexity of the classical model for a task $T$ is
$S_{\delta}(T)$; for the robust model, $S^{AR}_{\delta}(T)$, for the zero
error model, $S_{0}(T)$; for the deterministic model, $S^{det}(T)$; for the
white box robust model, $S^{WB}_{\delta}(T)$; for the pseudo-deterministic
model, $S^{PD}_{\delta}(T)$, and the random start model, $S^{RS}_{\delta}(T)$.
The following relationships follow from the definitions of the models:

$\displaystyle S^{AR}_{\delta}(T)$ $\displaystyle\leq S^{RS}_{\delta}(T)$
$\displaystyle S^{RS}_{\delta}(T)$ $\displaystyle\leq S^{det}(T)$
$\displaystyle S_{\delta}(T)$ $\displaystyle\leq S^{AR}_{\delta}(T)$
$\displaystyle S^{AR}_{\delta}(T)$ $\displaystyle\leq S^{WB}_{\delta}(T)$
$\displaystyle S^{WB}_{\delta}(T)$ $\displaystyle\leq S^{det}(T)$
$\displaystyle S^{AR}_{\delta}(T)$ $\displaystyle\leq S^{PD}_{\delta}(T)$
$\displaystyle S^{PD}_{\delta}(T)$ $\displaystyle\leq S^{det}(T)$
$\displaystyle S_{0}(T)$ $\displaystyle\leq S^{det}(T)$

For problems in communication complexity, we write
$R^{\rightarrow}_{\delta}(T)$ for the one-way randomized $\delta$-error
communication complexity of task $T$, and $D^{\rightarrow}(T)$ for the
deterministic communication complexity.

###  3.2 Lemmas

#### The $\textsc{avoid}(t,a,b)$ communication task

This one-way communication game was introduced by [CGS22]. In it, Alice is
given $S\subseteq[t]$ with $|S|=a$, and sends a message to Bob, who must
produce $T\subseteq[t]$ with $|T|=b$ where $T$ is disjoint from $S$.

######  Lemma 1.

(From [CGS22], Lemma 6) The public-coin $\delta$ error one-way communication
complexity of $\textsc{avoid}(t,a,b)$ is at least
$\log(1-\delta)+\log(\binom{t}{a}/\binom{t-b}{a})$. Because

$\displaystyle\binom{t}{a}/\binom{t-b}{a}=\frac{t!(t-a-b)!}{(t-a)!(t-b)!}\geq
2^{\frac{ab}{t\ln 2}}$

we have the weaker but more convenient lower bound
$R^{\rightarrow}_{\delta}(\textsc{avoid}(t,a,b))\geq\frac{ab}{t\ln
2}+\log(1-\delta)$

The above lower bound is mainly useful when $ab\in[t,t^{2}]$. For smaller
inputs:

######  Lemma 2.

The public-coin $\delta$-error one-way communication complexity of
$\textsc{avoid}(t,a,b)$ satisfies

$\displaystyle
R^{\rightarrow}_{\delta}(\textsc{avoid}(t,a,b))\geq\min\left(\log(a+1),\log\frac{\ln(1/\delta)}{\ln(et/a)}\right)\,.$

For the deterministic case, we have
$D^{\rightarrow}(\textsc{avoid}(t,a,b))\geq\log(a+1)$.

###### Proof.

Say we have a public coin one-way randomized protocol $\Pi$ for
$\textsc{avoid}(t,a,b)$ with error $\delta$; by the averaging argument, there
exists a fixing of the randomness of the protocol, which is correct on $\geq
1-\delta$ of the sets in $\binom{[t]}{a}$. Let $\Psi$ be this deterministic
protocol, and let $\hat{m}$ be the number of distinct messages sent by $\Psi$.
Each message $i\in[\hat{m}]$ corresponds to some set $B_{i}$ that Bob outputs
on receiving the message. Let $E:=\\{e_{1},\ldots,e_{m}\\}$ be a hitting set
for $\\{B_{i}\\}_{i\in[\hat{m}]}$ of size $m\leq\hat{m}$; i.e, for all
$B_{i}$, there is some $e_{j}\in B_{i}$. Let
$\mathcal{C}\subseteq\binom{[t]}{a}$ be the set of inputs for which $\Psi$ is
correct; we note that no inputs in $\mathcal{C}$ can contain all of $E$,
because if $A\supseteq E$, then every $B_{i}$ intersects $A$, making the
protocol fail. Assuming $m\leq a$, we have:

$\displaystyle\delta$ $\displaystyle\geq
1-|\mathcal{C}|/\binom{t}{a}\geq|\\{A\in\binom{t}{a}:A\supseteq
E\\}|/\binom{t}{a}$
$\displaystyle=\binom{t-m}{a-m}/\binom{t}{a}=\frac{a\cdot(a-1)\cdots(a-m+1)}{t\cdot(t-1)\cdots(t-m+1)}\geq\left(\frac{a/e}{t}\right)^{m}\,,$

where the last step is derived from the well known inequality
$a!\geq(a/e)^{a}$. Rearranging gives $m\geq\ln(1/\delta)/\ln(et/a))$. In the
case where $m>a$, this argument does not work, because then
$\binom{t-m}{a-m}=0$. Combining the two cases gives: $\hat{m}\geq
m\geq\min(a+1,\ln(1/\delta)/\ln(et/a)))$. Thus
$R^{\rightarrow}_{\delta}(\textsc{avoid}(t,a,b))\geq\log(\min(a+1,\ln(1/\delta)/\ln(et/a)))$.

For general deterministic protocols, we reuse the analysis of randomized
protocols with $\delta=0$, concluding that
$D^{\rightarrow}(\textsc{avoid}(t,a,b))\geq\log(a+1)$. ∎

The following lemma is a simple variation of Chernoff’s and Azuma’s
inequalities; for completeness, we present a proof in Appendix A.

######  Lemma 3 (Modified Azuma’s inequality).

Let $X_{1},\ldots,X_{n}$ be $\\{0,1\\}$ random variables, with
$\mathbb{E}[X_{i}\mid X_{1}=x_{1},\ldots,X_{i-1}=x_{i-1}]\leq p$ for all $i$
and all $x_{1},\ldots,x_{n}\in\\{0,1\\}^{n}$. Then

$\displaystyle\Pr\left[\sum_{i=1}^{n}{X_{i}}\geq
np(1+\delta)\right]\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{np}\leq
e^{-\frac{\delta^{2}}{2+\delta}np}\,.$

A number of versions of Brouwer’s fixed point theorem have been proven; in
this paper, we will use the following, which is equivalent to Corollary 2.15
of [Hat02].

######  Lemma 4 (Brouwer’s fixed point theorem).

Every continuous map from a space homeomorphic to an $n$ dimensional-ball to
itself has a fixed point.

##  4 Classical model

######  Theorem 5.

For any $\delta\leq 1/(2n)$, the space complexity for an algorithm solving
$\textsc{mif}(n,r)$ with error $\leq\delta$ is
$S_{\delta}(\textsc{mif}(n,r))\geq
S^{\textsc{det}}(\textsc{mif}({\left\lceil{\frac{n}{t}}\right\rceil},{\left\lfloor{\frac{r}{t}}\right\rfloor}))$,
for $t={\left\lceil{\frac{r\log n}{\log\frac{1}{2\delta}}}\right\rceil}$. If
we apply the upcoming lower bound from Theorem 11 on the deterministic space
complexity of mif, we get:

$\displaystyle S_{\delta}(\textsc{mif}(n,r))$
$\displaystyle\geq\Omega\left(\sqrt{\min\left(r,\frac{\log(1/\delta)}{\log
n}\right)}+\min\left(r,\frac{\log(1/\delta)}{\log
n}\right)\frac{1}{1+\log(n/r)}\right)$

###### Proof.

Let $t$ be an integer satisfying
${\left\lceil{\frac{n}{t}}\right\rceil}^{\left\lfloor{\frac{r}{t}}\right\rfloor}<\frac{1}{\delta}$;
setting $t={\left\lceil{\frac{r\log n}{\log\frac{1}{2\delta}}}\right\rceil}$
suffices, because

$\displaystyle\log\left({\left\lceil{\frac{n}{t}}\right\rceil}^{\left\lfloor{\frac{r}{t}}\right\rfloor}\right)\leq{\left\lfloor{\frac{r}{t}}\right\rfloor}\log{\left\lceil{\frac{n}{t}}\right\rceil}\leq\frac{r}{t}\log
n\leq\frac{r}{{\left\lceil{r\log n/\log(1/2\delta)}\right\rceil}}\log
n\leq\frac{\log(1/2\delta)}{\log n}\log n<\log\frac{1}{\delta}\,.$

Note also that because $\delta\leq 1/(2n)$, $t\leq r$, and
${\left\lfloor{\frac{r}{t}}\right\rfloor}\geq 1$.

Given a randomized algorithm $\Pi$ that solves $\textsc{mif}(n,r)$ with error
$\leq\delta$ on any input stream, we will show how to construct a randomized
algorithm $\Psi$ which solves
$\textsc{mif}({\left\lceil{n/t}\right\rceil},{\left\lfloor{r/t}\right\rfloor})$
with the same error probability. As there are only
${\left\lceil{n/t}\right\rceil}^{\left\lfloor{r/t}\right\rfloor}$ possible
input streams for the
$\textsc{mif}({\left\lceil{n/t}\right\rceil},{\left\lfloor{r/t}\right\rfloor})$
task, the probability (over randomness used by $\Psi$) of the event $E$ than
an instance $A$ of $\Psi$ succeeds on _any_ of the streams in
$[{\left\lceil{n/t}\right\rceil}]^{\left\lfloor{r/t}\right\rfloor}$ is $\geq
1-\delta{\left\lceil{\frac{n}{t}}\right\rceil}^{\left\lfloor{\frac{r}{t}}\right\rfloor}>0$.
Therefore, by fixing the random bits of $\Psi$ to some value for which the
event $E$ occurs, we obtain a deterministic protocol $\Phi$ for
$\textsc{mif}({\left\lceil{n/t}\right\rceil},{\left\lfloor{r/t}\right\rfloor})$.

We now explain the construction of $\Psi$ given $\Pi$. Let
$f:[n]\mapsto[{\left\lceil{n/t}\right\rceil}]$ be the function given by
$f(x)={\left\lfloor{x/t}\right\rfloor}$. For any
$y\in[{\left\lceil{n/t}\right\rceil}]$, we have that $f^{-1}(y)$ is a nonempty
set of size $\leq t$. The protocol $\Psi$ starts by initializing an instance
$A$ of $\Pi$, and sending it $r-t{\left\lfloor{r/t}\right\rfloor}$ arbitrary
stream elements.

When $\Psi$ receives an element $e\in[{\left\lceil{n/t}\right\rceil}]$, it
sends a sequence of $t$ elements of $[n]$ to $A$, namely, the elements of
$f^{-1}(e)$, in arbitrary order, repeating elements if $|f^{-1}(e)|<t$. To
output an element, $\Psi$ queries $A$ to obtain $i\in[n]$, and reports $f(i)$.
Assuming $A$ did not fail, $f(i)$ is guaranteed to be a correct answer. If we
assume for sake of contradiction that $f(i)=e$ for some element $e$ sent to
$\Psi$ earlier, then $A$ must have been sent all elements in $f^{-1}(e)$ –
which implies that $i\in f^{-1}(e)$ and that $A$ gave an incorrect output,
contradicting the assumption that $f(i)=e$. Thus, we have proven that $\Psi$
fails with no greater probability than $\Pi$, which is all that is needed to
complete this part of the proof.

Having shown that $S_{\delta}(\textsc{mif}(n,r))\geq
S^{\textsc{det}}(\textsc{mif}({\left\lceil{\frac{n}{t}}\right\rceil},{\left\lfloor{\frac{r}{t}}\right\rfloor}))$,
we now substitute in the lower bound from Theorem 11.

$\displaystyle S_{\delta}(\textsc{mif}(n,r))$ $\displaystyle\geq
S^{\textsc{det}}\left(\textsc{mif}\left({\left\lceil{\frac{n}{t}}\right\rceil},{\left\lfloor{\frac{r}{t}}\right\rfloor}\right)\right)\geq\Omega\left(\max\left(\sqrt{{\left\lfloor{\frac{r}{t}}\right\rfloor}},\frac{{\left\lfloor{r/t}\right\rfloor}}{1+\log({\left\lceil{n/t}\right\rceil}/{\left\lfloor{r/t}\right\rfloor})}\right)\right)$

Because
${\left\lfloor{r/t}\right\rfloor}=\Theta\left(\min\left(r,\frac{\log(1/\delta)}{\log
n}\right)\right)$, and
${\left\lceil{n/t}\right\rceil}/{\left\lfloor{r/t}\right\rfloor}=\Theta(n/r)$,
and $\Omega(\max(a,b))=\Omega(a+b)$, this simplifies to:

$\displaystyle
S_{\delta}(\textsc{mif}(n,r))=\Omega\left(\sqrt{\min\left(r,\frac{\log(1/\delta)}{\log
n}\right)}+\min\left(r,\frac{\log(1/\delta)}{\log
n}\right)\frac{1}{1+\log(n/r)}\right)$

∎

###  4.1 Upper bound: a sampling algorithm

Figure 1: This diagram shows the behavior of Algorithm 2 on an example input.
The top row of squares corresponds to the set $[n]$, ordered so that the
leftmost squares corresponds to the elements $L_{1}$, $L_{2}$, $\ldots$,
$L_{t+1}$ from Algorithm 2. In the top row, cells contain a pink dot if the
corresponding element has already been seen in the stream. In the bottom row,
each of the cells is shaded dark if the corresponding entry in the vector $x$
is equal to $1$ – except for $L_{t+1}$, whose state Algorithm 2 does not
track.

######  Theorem 6.

Algorithm 2 solves $\textsc{mif}(n,r)$ with error $\leq\delta$ on any fixed
input stream, and uses $s\leq\min(r,\frac{\log(1/\delta)}{\log(n/r)})$ bits of
space. (This assumes oracle access to $O((s+1)\log n)$ random bits.)

Algorithm 2 A streaming algorithm for $\textsc{mif}(n,r)$ with error rate
$\leq\delta$ on any input stream

1:Let $t=\min(r,{\left\lfloor{\log(1/\delta)/\log(n/r)}\right\rfloor})$

2:

3:Initialization:

4:Let $L=\\{L_{1},\ldots,L_{t+1}\\}$ be a fixed sequence of elements in
$[n]^{t+1}$ without repetitions, chosen uniformly at random. (This can be
stored explicitly using $O((t+1)\log n)$ bits, or computed on demand as a
function of $O((t+1)\log n)$ oracle random bits.)

5:$x\leftarrow\\{0,\ldots,0\\}$, a vector in $\\{0,1\\}^{t}$

6:

7:Update($e\in[n]$):

8:if $\exists j\in[t]:L_{j}=e$ then

9: $x_{j}\leftarrow 1$

10:

11:Query:

12:if $\exists j\in[t]:x_{j}=0$ then

13: output: $L_{j}$

14:else

15: output: $L_{t+1}$

###### Proof.

First, we observe that Algorithm 2 gives an incorrect output only when the
input stream $\sigma=(e_{1},\ldots,e_{r})$ contains every element of $L$.
Otherwise, either the first $t$ elements of $L$ are in $\sigma$, and $L_{t+1}$
isn’t – in which case Line 15 returns $L_{t+1}$ – or there is some $j\in[t]$
where $L_{j}$ has not been seen in the stream so far, in which case Line 13
correctly returns $L_{j}$. Given a fixed input stream $\sigma\in[n]^{r}$, the
probability that Algorithm 2 fails is:

$\displaystyle\Pr[L\subseteq\sigma]=\binom{|\sigma|}{t+1}\big{/}\binom{n}{t+1}\leq\binom{r}{t+1}\big{/}\binom{n}{t+1}=\frac{r(r-1)\cdots(r-t)}{n(n-1)\cdots(n-t)}\leq\left(\frac{r}{n}\right)^{t+1}$

Thus $\Pr[L\subseteq\sigma]$ is $\leq\delta$ when
$t={\left\lfloor{\log(1/\delta)/\log(n/r)}\right\rfloor}$, and is equal to $0$
when $t=r$, because no set of size $r$ can contain a set of size $r+1$. ∎

##  5 Adversarially robust model

######  Theorem 7.

Any algorithm which solves $\textsc{mif}(n,r)$ against adaptive adversaries
with total error $\delta$ requires
$\geq\log(\binom{n}{{\left\lceil{r/2}\right\rceil}}/\binom{n-{\left\lceil{r/2}\right\rceil}}{{\left\lfloor{r/2}\right\rfloor}+1})+\log(1-\delta)$
bits of space; or less precisely, $\Omega(r^{2}/n+\log(1-\delta))$.

###### Proof.

We prove this by reducing the communication task
$\textsc{avoid}(n,{\left\lceil{r/2}\right\rceil},{\left\lfloor{r/2}\right\rfloor}+1)$
(see Section 3) to $\textsc{mif}(n,r)$.

Say Alice is given the set $A\subseteq[n]$ of size
${\left\lceil{r/2}\right\rceil}$. They instantiate an instance $\mathcal{X}$
of the given algorithm for $\textsc{mif}(n,r)$, and runs it on the partial
stream of length ${\left\lceil{r/2}\right\rceil}$ containing the elements of
$A$ in some arbitrary order. Alice then sends the state of $\mathcal{X}$ to
Bob; since this is a public coin protocol, all randomness can be shared for
free. Bob then runs the following adversary against $\mathcal{X}$; it queries
$\mathcal{X}$ for an element $b_{0}$, and then provides that element back to
$\mathcal{X}$, repeating this process ${\left\lfloor{r/2}\right\rfloor}+1$
times to recover elements
$b_{0},b_{1},\ldots,b_{{\left\lfloor{r/2}\right\rfloor}}$. The instance will
fail to give correct answers to this adversary with total probability
$\leq\delta$. If it succeeds, then by the definition of the Missing Item
Finding problem, $b_{0}\notin A$, $b_{1}\notin\\{b_{1}\\}\cup A$, and so on;
thus Bob can report
$B:=\\{b_{0},\ldots,b_{{\left\lfloor{r/2}\right\rfloor}+1}\\}$ as a set of
${\left\lfloor{r/2}\right\rfloor}+1$ elements which are disjoint from $A$.

This avoid protocol implementation uses the same number of bits of
communication as $\mathcal{X}$ does of space. By Lemma 1, it follows
$\mathcal{X}$ needs:

$\displaystyle\geq\log\left(\binom{n}{{\left\lceil{r/2}\right\rceil}}/\binom{n-{\left\lfloor{r/2}\right\rfloor}-1}{{\left\lceil{r/2}\right\rceil}}\right)+\log(1-\delta)$
$\displaystyle\geq\frac{{\left\lceil{r/2}\right\rceil}({\left\lfloor{r/2}\right\rfloor}+1)}{n\ln
2}+\log(1-\delta)\geq\frac{r^{2}}{4n\ln 2}+\log(1-\delta)\,,$

bits of space. ∎

###  5.1 Upper bound: the hidden list algorithm

Figure 2: This diagram shows the behavior of Algorithm 3 on an example input.
The top row of squares corresponds to the set $[n]$, ordered so that the
leftmost squares corresponds to the elements $L_{1}$, $L_{2}$, $\ldots$,
$L_{r+1}$ from Algorithm 3. In the top row, cells contain a pink dot if the
corresponding element has already been seen in the stream. In the bottom row,
the letter C indicates the cell corresponding to $L_{c}$. Cells that are
shaded dark blue indicate the values contained in $J$. The third cell from the
left is included in $J$ because, at the time the element $L_{3}$ was added by
the adversary, $c$ was less than or equal to $2$.

######  Theorem 8.

Algorithm 3 solves $\textsc{mif}(n,r)$ against adaptive adversaries, with
error $\delta$, and can be implemented using
$O(\min(r,\left(1+\frac{r^{2}}{n}+\ln\frac{1}{\delta}\right)\cdot\log r))$
bits of space. (It assumes oracle access to $(r+1)\log n$ random bits.)

Algorithm 3 An adversarially robust algorithm for $\textsc{mif}(n,r)$ with
error $\leq\delta$

1:Let
$t=\min(r,{\left\lceil{3\frac{r^{2}}{n}+\ln\frac{1}{\delta}}\right\rceil})$

2:

3:Initialization:

4:Let $L=\\{L_{1},\ldots,L_{r+1}\\}$ be a fixed sequence of elements in
$[n]^{r+1}$ without repetitions, chosen uniformly at random. (Assuming oracle
access to $O(r\log n)$ random bits, the value of $L$ can be computed on
demand, instead of stored.)

5:$c\leftarrow 1$, an integer in the range $\\{1,\ldots,r+1\\}$

6:$J\leftarrow\emptyset$, a subset of $\\{L_{1},\ldots,L_{r}\\}$ of size $\leq
t$

7:

8:Update($e\in[n]$):

9:while $e=L_{c}$ or $L_{c}\in J$ do

10: $c\leftarrow c+1$

11:if $e\in\\{L_{c+1},\ldots,L_{r}\\}$ then

12: $J\leftarrow J\cup\\{e\\}$

13:if $|J|>t$ then

14: abort

15:

16:Query:

17:output: $L_{c}$

###### Proof.

First, we observe that the only way that Algorithm 3 can fail is if it aborts.
At any point in the stream, the set $J$ includes the intersection of the
earlier elements from the stream, with the list $\\{L_{c+1},\ldots,L_{r}\\}$
of possible future outputs. The while loop ensures that the element $L_{c}$
emitted will neither be equal to the current element nor collide with any past
stream elements (those in $J$). It is not possible for $c$ to go out of
bounds, because each element in the stream can lead to an increase in $c$ of
at most one; either immediately when the element arrives, if $e=L_{c}$; or
delayed slightly, if $e\in\\{L_{c+1},\ldots,L_{r}\\}$. Since the stream
contains $r$ elements, $c$ will increase by at most $r$, to a value of $r+1$.
Note that if $c$ has reached the value $r+1$, then the entire stream was a
permutation of $\\{L_{1},\ldots,L_{r}\\}$, making $L_{r+1}$ is a safe output.

This algorithm needs $\log(r+1)$ bits to store $c$, but the main space usage
is in storing $J$. We will show that $|J|\leq t$ with probability $\geq
1-\delta$, in which case $J$ can be stored as either a bit vector of length
$r$, or a list of $\leq t$ indices in $[r]$, using $O(\min(r,t\log r))$ bits
of space.

We observe that after $i-1$ elements have been received (and up to $i$
distinct elements emitted), the probability that the $i$th element chosen by
the adversary will be newly stored in $J$ will be $\leq 2\frac{r}{n}$, no
matter what the earlier elements were or what the adversary picks. If $r\geq
n/2$, this is immediate. Otherwise, write $E_{i-1}$ for the set containing the
first $i-1$ elements of the stream, $e_{i}$ for the $i$th element, and let
$c_{i}$ be the value of the variable $c$ as of Line 11. Let $X_{i}$ denote the
indicator random variable for the event that $e_{i}$ was not in $J$ before,
but has been added now.

Because the adversary has only been given outputs deriving from $L_{\leq
c_{i}}:=(L_{1},\ldots,L_{c_{i}})$, if we condition on the random variable
$L_{\leq c_{i}}$, then the element $e_{i}$ and set $E_{i-1}$ are independent
of $L_{>c_{i}}:=\\{L_{c_{i}+1},\ldots,L_{r}\\}$. Given $E_{i-1}$, the values
$X_{1},\ldots,X_{i-1}$ determine whether or not each element of $E_{i-1}$ is
in $L_{>c_{i}}$. Then, conditioning on $L_{\leq c_{i}},e_{i},E_{i-1}$, and
$X_{1},\ldots,X_{i-1}$, we have that $L_{>c_{i}}\setminus E_{i-1}$ is a set of
size $r-c_{i}-|L_{>c_{i}}\cap E_{i-1}|$ chosen uniformly at random from
$[n]\setminus L_{\leq c_{i}}\setminus E_{i-1}$. Thus, if $e_{i}\notin L_{\leq
c_{i}}\cup E_{i-1}$, the probability that $X_{i}=1$ is precisely the
probability that $e_{i}$ is contained in $L_{>c_{i}}\setminus E_{i-1}$, so:

$\displaystyle\Pr\left[X_{i}=1\mid(X_{j})_{j=1}^{i-1},e_{i},E_{i-1},L_{\leq
c_{i}},\\{e_{i}\notin L_{\leq c_{i}}\cup E_{i-1}\\}\right]$
$\displaystyle=\frac{r-c_{i}-|L_{>c_{i}}\cap
E_{i-1}|}{n-c_{i}-|E_{i-1}\setminus L_{\leq c_{i}}|}$
$\displaystyle\leq\frac{r-c_{i}}{n-c_{i}-r}\leq\frac{r}{n-r}\leq\frac{2r}{n}\,.$

On the other hand, the event $e_{i}\in L_{\leq c_{i}}\cup E_{i-1}$, implies
$X_{i}=0$ always. Together, these imply
$\Pr[X_{i}=1\mid(X_{j})_{j=1}^{i-1}]\leq 2r/n$.

Then applying the (modified, see Lemma 3) Azuma’s inequality bound, we find
that with $z:=\max\\{1,\frac{3n}{2r^{2}}\ln{\frac{1}{\delta}}\\}$:

$\displaystyle\Pr[\sum_{i\in[r]}X_{i}$
$\displaystyle\leq\frac{2r^{2}}{n}(1+z)]\leq
e^{-\frac{z}{2+z}z\frac{2r^{2}}{n}}$ $\displaystyle\leq
e^{-z\frac{2r^{2}}{3n}}$ since $z\geq 1$ $\displaystyle\leq
e^{-\ln{\frac{1}{\delta}}}=\delta\,.$ since
$z\geq\frac{3n}{2r^{2}}\ln{\frac{1}{\delta}}$

This implies that the probability that $|J|$ exceeds $2r^{2}/n+3\ln(1/\delta)$
will be $\leq\delta$. Consequently, our bound for the total space usage of the
algorithm is:

$\displaystyle O(\log r)$
$\displaystyle+O(\min(r,\left(\frac{r^{2}}{n}+\ln\frac{1}{\delta}\right)\log
r))$
$\displaystyle=O(\min(r,\left(1+\frac{r^{2}}{n}+\ln\frac{1}{\delta}\right)\cdot\log
r))$

∎

While it is possible to reduce the space usage of Algorithm 3 by removing all
elements from the set $J$ that are less or equal than $c$, this only changes
the constant factor.

##  6 Zero error model

######  Theorem 9.

All algorithms solving $\textsc{mif}(n,r)$ with zero error on any stream
require $\Omega(r^{2}/n)$ bits of space, in expectation over the randomness of
the algorithm.

###### Proof.

First, we prove that if there is a zero-error algorithm $\Phi$ for
$\textsc{mif}(n,r)$ using exactly $s$ bits, in expectation, then there is a
communication protocol for
$\textsc{avoid}(n,{\left\lceil{r/2}\right\rceil},{\left\lfloor{r/2}\right\rfloor}+1)$
using prefix-encoded messages with an expected length of $s$ bits. The
construction is the same as for Theorem 7. Alice, on being given a set
$A\subseteq[n]$ of size ${\left\lceil{r/2}\right\rceil}$, initializes an
instance $X$ of $\Phi$, and runs it on an input stream $\alpha$ of length
${\left\lceil{r/2}\right\rceil}$ containing each element of $A$ in some
arbitrary order. Any random bits used by $X$ are shared publicly with Bob.
They send the encoding of $X$’s state to Bob, who queries $X$ to find an
element $b_{0}\notin\alpha$, updates $X$ with $b_{0}$, queries it to find
$b_{1}\notin\alpha\cup\\{b_{0}\\}$, and so on until Bob has recovered
$B=\\{b_{0},\ldots,b_{{\left\lfloor{r/2}\right\rfloor}}\\}$. Because the
algorithm is guaranteed to never fail on any input stream, it must in
particular succeed on Bob’s adaptively chosen continuation of $\alpha$. This
ensures that $B\cap A=\emptyset$ holds with probability $1$.

Next, we prove that any zero error randomized communication protocol $\Pi$ for
$\textsc{avoid}(t,a,b)$ requires $\geq ab/(t\ln 2)$ bits _in expectation_.
Following the argument from Lemma 6 of [CGS22], we observe that there must
exist a fixing of the public randomness of $\Pi$ for which the expected number
of bits used when inputs $A$ are drawn uniformly at random from
$\binom{[t]}{a}$, is at least as large as when $\Pi$ is run unmodified. Let
$\Upsilon$ be the deterministic protocol with this property, and let $M$ be
the set of all messages sent by $\Upsilon$. Each message $m\in M$ has a length
$|m|$, probability (over the random choice of $A$) $p_{m}$ of being sent, and
makes Bob output the set $B_{m}$. For all $m\in M$, we have:

$\displaystyle p_{m}=\Pr[\text{$m$ is sent}]\leq\Pr[\text{$B_{m}$ is a correct
output}]=\Pr[A\cap B_{m}=\emptyset]\leq\binom{t-a}{b}/\binom{t}{a}\leq
2^{-\frac{ab}{t\ln 2}}.$

Let $\Upsilon(A)\in M$ be the message sent by $\Upsilon$ for a given value of
$A$. Then the entropy

$\displaystyle H(\Upsilon(A))=\sum_{m\in
M}p_{m}\log\frac{1}{p_{m}}=\mathbb{E}_{A\in\binom{[t]}{a}}\log\frac{1}{p_{\Upsilon(A)}}\geq\mathbb{E}_{A\in\binom{[t]}{a}}\frac{ab}{t\ln
2}=\frac{ab}{t\ln 2}\,.$

By the source coding theorem,

$\displaystyle\mathbb{E}_{A\in\binom{[t]}{a}}\mathbb{E}|\Upsilon(A)|\geq
H(\Upsilon(A))\geq\frac{ab}{t\ln 2}\,.$

Applying the above lower bound to the task
$\textsc{avoid}(n,{\left\lceil{r/2}\right\rceil},{\left\lfloor{r/2+1}\right\rfloor})$,
we conclude that $\Phi$ requires $\geq\frac{r^{2}}{4n\ln 2}$ bits of space in
expectation.

∎

######  Theorem 10.

There is an algorithm solving $\textsc{mif}(n,r)$ with zero error against
adaptive adversaries, which uses $O((1+r^{2}/n)\log r)$ bits of space, in
expectation over the randomness of the algorithm.

###### Proof.

We use a slight variation of Algorithm 3, in which internal parameter $t$ is
instead set to $r$. This ensures that the algorithm will never abort; the
proof of Theorem 8 has established that Algorithm 3 will then always give a
correct output for the $\textsc{mif}(n,r)$ task.

The counter $c$ can be encoded in binary using at most
${\left\lceil{\log(r+1)}\right\rceil}$ bits. We encode the set $J$ by
concatenating the binary value of $|J|$, followed by the binary values of the
indices $i_{1},\ldots,i_{|J|}$ in $[r]$ for which $L_{i_{k}}$ is equal to the
$k$th smallest element of $J$. (As both the encodings of $c$ and $J$ are
prefix codes, so too is the encoding of the algorithm’s state formed by
concatenating them.) The total space $S$ used by the algorithm (excluding
random bits) is then:

$\displaystyle
S={\left\lceil{\log(r+1)}\right\rceil}+{\left\lceil{\log{r}}\right\rceil}(1+|J|)\,.$

As in the proof of Theorem 8, let $X_{i}$ be the indicator random variable for
the event that the $i$th element that the adversary chooses for the stream is
stored in $J$; we showed that for all $i\in[r]$, $\Pr[X_{i}=1\mid
X_{i-1},\ldots,X_{1}]\leq\frac{r-1}{n}$, which implies
$\mathbb{E}[X_{i}]\leq\frac{r-1}{n}$. By linearity of expectation,

$\displaystyle\mathbb{E}S$
$\displaystyle={\left\lceil{\log(r+1)}\right\rceil}+{\left\lceil{\log{r}}\right\rceil}\left(1+\mathbb{E}\sum_{i\in[r]}X_{i}\right)$
$\displaystyle\leq{\left\lceil{\log(r+1)}\right\rceil}+{\left\lceil{\log{r}}\right\rceil}\left(1+\frac{r(r-1)}{n}\right)=O((1+\frac{r^{2}}{n})\log
r)\,.$

∎

##  7 Deterministic model

###  7.1 Lower bound: an embedded instance of Avoid

Figure 3:  In the proof of Theorem 11, the quantities $F_{\sigma}$ (defined in
Eq. 1) are entirely determined by the values of $\Sigma[\sigma]$ and
$r-|\sigma|$. More precisely, we have
$F_{\sigma}=G_{\Sigma[\sigma],r-|\sigma|}$, where
$G_{s,i}:=\\{\omega_{x}:\exists\alpha\in[n]^{i}:\tau(s,\alpha)=x\\}$. This
diagram shows the values of $G_{s,i}$ for Algorithm 1 solving the
$\textsc{mif}(4,2)$ problem. The sets $G_{s,i}$ are represented by the dark
squares in the array of four cells. The transition function between states is
indicated by the colored arrows; for example, green colored arrows (those
emitting from squared numbered with a 3) correspond to transitions where the
next stream element is a 3, i.e, from state $s$ to state
$s^{\prime}=\tau(s,3)$.

######  Theorem 11.

Every deterministic streaming algorithm for $\textsc{mif}(n,r)$ requires
$\Omega(\sqrt{r}+\frac{r}{1+\log(n/r)})$ bits of space.

###### Proof.

Let $\Sigma$ be the set of states of the algorithm, and let $s_{\text{init}}$
be the initial state. Let $\tau:\Sigma\times[n]^{\star}\mapsto\Sigma$ be the
transition function of the algorithm, where $\tau(s,e_{1},\ldots,e_{k})=x$
means that if the algorithm is at state $s$, and the next $k$ elements in the
stream are $e_{1},\ldots,e_{k}$, then after processing those elements the
algorithm will reach state $x$. For each partial stream
$\sigma\in[n]^{\star}$, abbreviate $\tau(s_{\text{init}},\sigma)$ as
$\Sigma[\sigma]$. For each state $s\in\Sigma$, we associate the output
$\omega_{s}\in[n]$ which the algorithm would emit if the state is reached at
the end of the stream. (If there is no stream of length $r$ leading to state
$s$, we let $\omega_{s}$ be arbitrary.)

For each partial stream $\sigma\in[n]^{\star}$, let

$\displaystyle F_{\sigma}=\\{i:\exists
x\in\Sigma,\exists\alpha\in[n]^{r-|\sigma|}:\tau(\Sigma[\sigma],\alpha)=x\land\omega_{x}=i\\}$
(1)

be the set of possible outputs of the algorithm when $\sigma$ is extended to a
stream of length $r$. Because there are only $|\Sigma|$ states, and only $[n]$
possible output values, $|F_{s}^{i}|\leq m$, where $m=\min(|\Sigma|,n)$.

Let $t,q$ be integers chosen later, so that

$\displaystyle tq\leq r-m/2^{q}\,.$ (2)

We claim that there exists a partial stream $\sigma\in[n]^{\star}$ satisfying
$\forall\alpha\in[n]^{t}:|F_{\sigma.\alpha}|\geq\frac{1}{2}|F_{\sigma}|$.

Such a state can be found by an iterative process. Let $\tau_{0}$ be the empty
stream $\epsilon$; for $i=1,2,3,....$ , if there exists $\alpha\in[n]^{t}$ for
which $|F_{\tau_{i}.\alpha}|\leq\frac{1}{2}|F_{\tau_{i}}|$, let
$\tau_{i+1}=\tau_{i}.\alpha$. Otherwise, stop, and let $\sigma=\tau_{i}$. This
process must terminate before $i=q$, because otherwise we would have
$|F_{\tau_{q}}|\leq m/2^{q}\leq r-qt$. Then letting $\gamma\in[n]^{r-qt}$ be a
sequence of elements containing every element of $F_{\tau_{q}}$, we observe
that the algorithm cannot possibly output a correct answer for the stream
$\tau_{q}.\gamma$. By the definition of $F_{\tau_{q}}$, we must have
$\omega_{\tau_{q}.\gamma}\in F_{\tau_{q}}$; but to be a correct missing item
finding solution, we need $\omega_{\tau_{q}.\gamma}\notin\gamma$, hence
$\omega_{\tau_{q}.\gamma}\notin F_{\tau_{q}}$, a contradiction. Thus,
$\sigma=\tau_{i}$ for some $i\leq q-1$. Thus $|\sigma|\leq(q-1)t\leq r-t$,
which ensures that the terms $\sigma.\alpha$ are streams of length $\leq r$
and therefore well defined. Finally, the stopping condition of the process
implies
$\forall\alpha\in[n]^{t}:|F_{\sigma.\alpha}|\geq\frac{1}{2}|F_{\sigma}|$.

We will now construct a deterministic protocol for
$\textsc{avoid}(|F_{\sigma}|,t,{\left\lceil{\frac{1}{2}|F_{\sigma}|}\right\rceil})$
using $\leq\log|\Sigma|$ bits of communication. Alice, on being given a set
$A\in\binom{F_{\sigma}}{t}$, arbitrarily orders it to form a sequence $\alpha$
in $(F_{\sigma})^{t}$; and then sends the state
$s^{\prime}=\tau(\Sigma[\sigma],\alpha)$ to Bob. This can be done using
$\log|\Sigma|$ bits of space. Bob uses the encoded state to find
$F_{\sigma.\alpha}$, by evaluating $\omega_{\tau(s^{\prime},\beta)}$ for all
sequences $\beta\in[n]^{|\sigma|-t}$, and reports the first
${\left\lceil{\frac{1}{2}|F_{\sigma}|}\right\rceil}$ elements of this set as
$B$. This protocol works because as claimed above, we are guaranteed
$|F_{\sigma.\alpha}|\geq|F_{\sigma}|$; and furthermore, $F_{\sigma.\alpha}$
must be disjoint from $A$; if it is not, then there exists some continuation
of $\sigma$ concatenated with $\alpha$ which leads the algorithm to a state
$z$ with $\omega_{z}\in A$, contradicting the correctness of the $MIF$
protocol. Finally, applying the communication lower bound from Lemma 1, we
find

$\displaystyle\log|\Sigma|\geq\frac{1}{\ln
2}t{\left\lceil{\frac{1}{2}|F_{\sigma}|}\right\rceil}/|F_{\sigma}|\geq t/(2\ln
2)$ (3)

We now determine values of $t$ and $q$ satisfying Eq. 2. We can set

$\displaystyle q={\left\lceil{1+\log(m/r)}\right\rceil}\qquad\text{ and
}\qquad
t={\left\lfloor{\frac{1}{q}\left(r-\frac{m}{2^{q}}\right)}\right\rfloor}$

We must have $m\geq r+1$, as otherwise $|F_{\epsilon}|\leq m\leq r$, in which
case we could easily make the algorithm give an incorrect output by running it
on a stream $\gamma\in[n]^{r}$ which contains all elements of $F_{\epsilon}$.
Thus $\log(m/r)\geq 0$, and hence $q\geq 1$, making $t$ well defined. Since
$m=\min(|\Sigma|,n)$, we are also guaranteed $\log|\Sigma|\geq\log(r+1)$.
Combining this with Eq. 3 gives:

$\displaystyle\log|\Sigma|$
$\displaystyle\geq\max\left(\log(r+1),\frac{1}{2\ln
2}{\left\lfloor{\frac{1}{q}\left(r-\frac{m}{2^{q}}\right)}\right\rfloor}\right)$
$\displaystyle\geq\max\left(1,\frac{1}{2\ln
2}{\left\lfloor{\frac{r}{2q}}\right\rfloor}\right)$ since $2^{q}\geq 2m/r$ and
$r\geq 1$ $\displaystyle\geq\frac{1}{1+2\ln 2}\cdot\frac{r}{2q}$ since
$\min(1,(z-1)/y)\geq\frac{z}{1+y}$
$\displaystyle\geq\frac{r}{10+5\log(m/r)}\,.$ since $1+2\ln 2\leq 5/2$ (4)

As $m=\min(|\Sigma|,n)$, we have $m\leq|\Sigma|$, so

$\displaystyle\log|\Sigma|\geq\frac{r/5}{2+\log|\Sigma|-\log
r}\qquad\implies\qquad(\log|\Sigma|)^{2}+(2-\log r)\log|\Sigma|-r/5\geq 0\,.$

Solving the quadratic inequality gives:

$\displaystyle\log|\Sigma|\geq\sqrt{\frac{r}{5}+\left(1-\frac{\log(r)}{2}\right)^{2}}-\left(1-\frac{\log(r)}{2}\right)\geq\begin{cases}\sqrt{r/5}&\text{if
$r\geq 4$}\\\ 0&\text{otherwise}\end{cases}$

As $\log|\Sigma|\geq\log(r+1)\geq\sqrt{r/5}$ also holds for $r\leq 4$, it
follows that $\log|\Sigma|\geq\sqrt{r/5}$ for all values of $r$. Combining
this result, Eq. 4, and the inequality $m\leq n$, we conclude:

$\displaystyle\log|\Sigma|\geq\max\left(\sqrt{\frac{r}{5}},\frac{r}{10+5\log(n/r)}\right)=\Omega\left(\sqrt{r}+\frac{r}{1+\log(n/r)}\right)\,.$

∎

Note: instead of associating “forward” looking sets of outputs $F_{s}$ with
each state $s\in\Sigma$, we could instead use “backward” looking states
$B_{s}$ defined (roughly) as $[n]\setminus\\{i:\exists\text{$\sigma$ leading
to $s$ with $i\in\sigma$}\\}$.

###  7.2 Upper bound: the iterated pigeonhole algorithm

Figure 4: This diagram shows the behavior of Algorithm 4, with $s=5$ and
$t=2$, on an example input. The pink circles and diamonds mark the elements
currently covered by the stream. Cells shaded dark gray are those which are no
longer possible outputs due to the current values of $\ell$ and $a$. Cells
shaded light green are no longer possible outputs due to the value of the
vector $x$. Cells shaded white are possible output values. The algorithm
proceeds in $t$ phases; in this example, for the first phase, it maintained a
bit vector tracking which of the $s$ rows of the set $[n]$ contained an
element from the stream; after the first five elements (1, 10, 11, 17, 24 in
some order) arrived, only one row was left available, and the algorithm
proceeded to the second phase – maintaining a bit vector $x$ that records
which columns within the chosen row may be unavailable.

######  Theorem 12.

Algorithm 4 is a deterministic algorithm that solves $\textsc{mif}(n,r)$ using
$O(\sqrt{r\log r}+\frac{r\log r}{\log n})$ bits of space.

Algorithm 4 A deterministic algorithm for $\textsc{mif}(n,r)$

1:Let $s,t$ be integers satisfying $s^{t}\leq n$, and $t(s-1)\geq r$.

2:

3:Initialization:

4:$x\leftarrow(0,\ldots,0)$ is a vector in $\\{0,1\\}^{s}$.

5:$(\ell,a)\leftarrow(1,0)$ is an element of
$\bigcup_{j\in[t]}\\{j\\}\times\\{0,\ldots,s^{j}-1\\}$

6:

7:Update($e\in[n]$):

8:Let $i\leftarrow\left({\left\lfloor{(e-1)/s^{\ell-1}}\right\rfloor}\bmod
s\right)+1$

9:$x_{i}\leftarrow 1$

10:if $\ell<t$ and there is exactly one $y\in[s]:x_{y}=0$ then

11: $x\leftarrow(0,\ldots,0)$

12: $\ell\leftarrow\ell+1$

13: $a\leftarrow a+(y-1)s^{\ell-1}$

14:

15:Query:

16:Let $i$ be the least value in $[s]$ for which $x_{i}=0$

17:output: $a+(i-1)s^{\ell-1}+1$

###### Proof.

First, we establish that the variables $(\ell,a)$ of the algorithm stay in
their specified bounds. The condition in Line 10 ensures that $\ell$ will not
be increased beyond $t$. At the time Line 13 is executed, $a<s^{\ell-1}$;
since $y\in[s]$, it follows $a+(y-1)s^{\ell-1}<(1+(s-1))s^{\ell-1}\leq
s^{\ell}$, so the pair $(\ell,a)$ stays in
$\bigcup_{j\in[t]}\\{j\\}\times\\{0,\ldots,s^{j}-1\\}$.

Next, we establish that the algorithm is correct; that the output from Line 17
does not overlap with current stream $e_{1},\ldots,e_{k}$. For each element
$e_{j}$ in the stream, let $\ell_{j}$ be the value of $\ell$ at the time the
element was added (i.e., at the start of the Update function). For all
$h\in[t]$, define $C_{h}:=\\{j\in[t]:\ell_{j}=h\\}$ to indicate the elements
for which $\ell_{j}=h$. Because Line 10 only triggers when $x$ has one zero
entry, and $x$ is reset to the all zero vector immediately afterwards, and
each new element sets at most one entry of $x$ to $1$ (Line 9), we have
$|C_{h}|\geq s-1$ for all $h$ less than or equal to the current value of
$\ell$.

Let $c=a+(i-1)s^{\ell-1}$ be the current output of the algorithm (Line 17),
minus 1. Note that $c\leq s^{t}-1\leq n-1$, so the output is in $[n]$. The
value of $c$ can be written in base $s$ as $(c_{1},\ldots,c_{t})$, so that
$c=\sum_{j=1}^{t}c_{j}s^{j-1}$. For $h$ less than the current value of $\ell$,
$c_{h}$ is equal to the value of $y$ at the time the condition of Line 10
evaluated to true; in other words, at that time, $x_{c_{h}}=0$. Now, for each
$j\in C_{h}$, consider the value $e_{j}-1$ written in base $s$ as
$(b_{1},\ldots,b_{t})$. When $e_{j}$ was added, Line 8 set $i$ equal to
$b_{h}$, and so Line 9 ensured $x_{b_{h}}=1$. Since $x_{c_{h}}=0$ held
afterwards, when the condition of Line 10 evaluated to true, it follows
$b_{h}\neq c_{h}$. This implies $e_{j}-1\neq c$ holds for all $j\in C_{h}$. A
similar argument will establish that for $j\in C_{\ell}$, we have $e_{j}-1\neq
c$; since $C_{1}\cup\ldots\cup C_{\ell}$ contains the entire stream so far, it
follows the current output of the algorithm does not equal any of the
$\\{e_{j}\\}_{j=1}^{k}$, and is thus correct.

Finally, we determine values of $s$ and $t$ which for which the algorithm uses
little space. The vector $x$ can be stored using $s$ bits; since there are
$\sum_{i=0}^{t-1}s^{i}\leq s^{t}$ possible values of $(\ell,a)$, this
algorithm can be implemented using $\leq s+t\log s+1$ bits of space.

Now let

$\displaystyle q=\min\left(\sqrt{r\log(r+1)},\log
n\right)\qquad\text{and}\qquad
t={\left\lfloor{\frac{q}{\log(r+1)}}\right\rfloor}\qquad\text{and}\qquad
s={\left\lceil{\frac{r}{t}}\right\rceil}+1\,,$

Because $r\geq\log(r+1)$, and $\log n\geq\log(r+1)$, it follows $t\geq 1$.
This implies $s\leq r+1$. Then $t(s-1)=t{\left\lceil{r/t}\right\rceil}\geq r$,
and

$\displaystyle
s^{t}\leq(r+1)^{{\left\lfloor{q/\log(r+1)}\right\rfloor}}\leq(r+1)^{q/\log(r+1)}\leq
2^{q}\leq n\,,$

so the values of $s$ and $t$ satisfy the required conditions $s^{t}\leq n$ and
$t(s-1)\geq r$. With these parameters, the space usage of the algorithm is:

$\displaystyle s+t\log s+1$
$\displaystyle\leq{\left\lceil{\frac{r}{t}}\right\rceil}+2+{\left\lfloor{\frac{q}{\log(r+1)}}\right\rfloor}\log({\left\lceil{\frac{r}{t}}\right\rceil}+1)$
$\displaystyle\leq\frac{r}{{\left\lfloor{q/\log(r+1)}\right\rfloor}}+3+\frac{q}{\log(r+1)}\log(r+1)$
$\displaystyle\leq\frac{2r\log(r+1)}{q}+q+3$
$\displaystyle=\max\left(2\sqrt{r\log(r+1)},\frac{2r\log(r+1)}{\log
n}\right)+\min\left(\sqrt{r\log(r+1)},\log n\right)+3$
$\displaystyle=O\left(\sqrt{r\log r}+\frac{r\log r}{\log n}\right)\,.$

∎

##  8 White box model

Figure 5:  In the proof of Theorem 13, the quantities $\nu_{\sigma,i}$ defined
as fixed points of Eq. 6 are shown for the state diagram of Algorithm 1 for
the problem $\textsc{mif}(4,2)$. The distributions $\nu_{\sigma,i}$ are
represented by the gray bar charts in each rectangle; for example, the
distribution $\nu_{s_{01},1}$ has weight $0.5$ on value $1$ and weight $0.5$
on value $3$. The transition function between states is indicated by the
colored arrows; for example, green colored arrows (those emitting from squared
numbered with a 3) correspond to transitions where the next stream element is
a 3, i.e, from state $s$ to state $s^{\prime}=\tau(s,3)$.

######  Theorem 13.

Every streaming algorithm for $\textsc{mif}(n,r)$ which has error $\delta\leq
1/\left(16n\right)^{2\log n+7}=1/2^{\Omega(\log n)^{2}}$ against white-box
adversaries requires $\Omega\left(\frac{r}{(\log n)^{4}}\right)$ bits of
space.

This proof relies on the following Lemma, whose proof we will defer for later.

######  Lemma 14.

Let $\nu$ be a distribution on $[n]$, and $p=1+1/\log(n)$. Let
$\delta\leq\frac{1}{n^{3}}$. Let $R$ be a random variable with values in
$\Omega$. If there is a map $M:[n]^{t}\times\Omega\rightarrow\triangle[n]$ so
that $\mathbb{E}_{x\sim\nu^{t},R}M(x,R)=\nu$, and:

$\displaystyle\Pr_{x\sim\nu^{t},R}\left[\|M(x,R)\|_{p}^{p}\leq
D^{p-1}{\left\|{\nu}\right\|}_{p}^{p}\land\left(\forall
j\in[t]:M(x,R)(x_{j})\leq\delta\right)\right]\geq 1-\frac{1}{2^{6}n^{2}}$ (5)

Then $\log|\operatorname{range}(M)|\geq\frac{t}{2^{9}D(\log
n)^{2}}-2\log(n)-6$.

###### Proof.

Proof of Theorem 13.

We can safely assume that $r\geq\log n+1$, as for any $r=O((\log n)^{3})$ the
claimed lower bound is trivial.

Let $\ell={\left\lceil{\log n+1}\right\rceil}$,
$t={\left\lfloor{\frac{r}{\ell}}\right\rfloor}$, and let $\hat{r}=t\ell$. We
can use a protocol for $\textsc{mif}(n,r)$ to solve $\textsc{mif}(n,\hat{r})$
instead, by padding the start of the stream with a fixed sequence of
$r-\hat{r}$ arbitrary inputs. Let $\mathcal{A}$ be this new algorithm.

Let $\Sigma$ be the set of all states of $\mathcal{A}$, and let
$\tau:\Sigma\times[n]\rightarrow\Sigma$ be the _randomized_ transition
function between states. For each state $s\in\Sigma$, let $\omega_{s}$ be the
distribution over $[n]$ from which the final output value is drawn when the
final state of the algorithm is $s$. (If $s$ can never occur at the end of the
stream, we let $\omega_{s}$ be arbitrary.) To each pair
$(s,i)\in\Sigma\times\\{0,\ldots,\ell\\}$, we will associate a distribution
$\nu_{s,i}$ over $[n]$. These distributions are recursively defined; if
$i=\ell$, we let $\nu_{s,\ell}=\omega_{s}$, i.e., the output distribution for
state $s$. For $i<\ell$, define $f_{s,i}:\triangle[n]\rightarrow\triangle[n]$
as:

$\displaystyle
f(\phi)=\mathbb{E}_{x\sim\phi^{t}}\mathbb{E}_{s^{\prime}\sim\tau(s,x)}\nu_{s^{\prime},i+1}=\sum_{x\in[n]^{t}}\left(\prod_{i\in[t]}\phi(x_{i})\right)\sum_{s^{\prime}\in\Sigma}\Pr[\tau(s,x)=s^{\prime}]\nu_{s^{\prime},i+1}$
(6)

Because this function is continuous, and $\triangle[n]$ is homeomorphic to an
$(n-1)$-dimensional ball, we can apply Brouwer’s fixed point theorem (Lemma 4)
to find a distribution $\nu_{s,i}\in\triangle[n]$ satisfying
$\nu_{s,i}=f_{s,i}(\nu_{s,i})$.

With the distributions $\nu_{s,i}$ as defined above, we can define an
adversary which, we can prove, will trick $\mathcal{A}$ into outputting an
element that was present in the stream with probability
$\geq\frac{1}{(16n)^{2\log n+7}}$. The adversary proceeds in $\ell$ rounds:
for each $i\in\\{0,\ldots,\ell-1\\}$, they identify the current state $s_{i}$
of the algorithm, sample $\alpha\sim\nu_{s_{i},i}$, and send $\alpha$ to
$\mathcal{A}$.

Let $p=1+1/\log n$; the quantity ${\left\|{\nu_{s,i}}\right\|}_{p}^{p}$ is a
measure of the concentration of the output distribution associated with $s$
and $i$. Assume for sake of contradiction that
$\log|\Sigma|\leq\frac{t}{2^{9}(\log n)^{2}}-2\log n-6$. Then we shall prove
by induction, for all $i\in\\{0,\ldots,\ell\\}$, the statement $P(i)$ that for
all $s\in\Sigma$, if ${\left\|{\nu_{s,i}}\right\|}_{p}^{p}\geq
2^{i(p-1)}/n^{p-1}$, then the probability that $\mathcal{A}$ will give an
incorrect answer when the remaining $(\ell-i)t$ elements of the stream are
provided by the adversary is $\geq 1/(16n)^{2(\ell-i)+3})$. The base case of
the induction, at $i=\ell$, holds vacuously, because
${\left\|{\nu_{s,i}}\right\|}_{p}^{p}\geq 2^{i(p-1)}/n^{p-1}\geq
2^{({\left\lceil{\log n}\right\rceil}+1)(p-1)}/n^{p-1}\geq 2^{p-1}>1$ is never
true.

Now, for the induction step. Assume $P(i+1)$ holds; we would like to prove
$P(i)$ is true. Assume the current state $s$ of the algorithm satisfies
${\left\|{\nu_{s,i}}\right\|}_{p}^{p}\geq 2^{i(p-1)}/n^{p-1}$. The adversary
samples $x\sim\nu_{s,i}^{t}$ and sends it to the algorithm, which transitions
to the state $s^{\prime}\sim\tau(s,x)$. If it is the case that

$\displaystyle\Pr[\text{$\nu$ too
concentrated}]:=\Pr[{\left\|{\nu_{s^{\prime},i+1}}\right\|}_{p}^{p}\geq
2^{(i+1)(p-1)}/n^{p-1}]\geq\frac{1}{2^{7}n^{2}}\,,$ (7)

then, by applying $P(i+1)$, it follows:

$\displaystyle\Pr[\text{$\mathcal{A}$ fails}]$
$\displaystyle\geq\Pr[\text{$\mathcal{A}$ fails}\mid\text{$\nu$ too
concentrated}]\Pr\left[\text{$\nu$ too concentrated}\right]$
$\displaystyle\geq\frac{1}{(16n)^{2(\ell-i-1)+3}}\cdot\frac{1}{2^{7}n^{2}}\geq\frac{1}{(16n)^{2(\ell-i)+3}}$

It remains to prove $P(i+1)$ assuming Eq. 7 does not hold. If that is the
case, let $M:[n]^{t}\times\Omega\rightarrow\triangle[n]$ be the randomized map
in which $M(x,R)=\nu_{s^{\prime},i+1}$ where $s^{\prime}$ is randomly chosen
according to $\tau(s,x)$; the random variable $R$ encapsulates the randomness
of $\tau$. Note that $\mathbb{E}_{x\sim\nu_{s,i}^{t},R}M(x,R)=\nu_{s,i}$, by
the definition of $\nu_{s,i}$. Applying Lemma 14 to $M$, $\nu_{s,i}$, $p$,
$D=2$, and $\delta=1/n^{3}$ we observe that since we have assumed that
$|\Sigma|\geq\log|\operatorname{range}(M)|$ is smaller than the Lemma
guarantees, and $\mathbb{E}_{x\sim\nu_{s,i}^{t}}\mathbb{E}M(x)=\nu_{s,i}$
holds, it must be that Eq. 5 is incorrect. Thus:

$\displaystyle\Pr_{x\sim\nu^{t}}\left[{\left\|{M(x,R)}\right\|}_{p}^{p}\leq
2^{p-1}{\left\|{\nu_{s,i}}\right\|}_{p}^{p}\land(\forall
j\in[t]:M(x,R)(x_{j})\leq\frac{1}{n^{3}})\right]\leq 1-\frac{1}{2^{6}n^{2}}$

and since Eq. 7 does not hold, we have

$\displaystyle\Pr_{x\sim\nu^{t}}\left[{\left\|{\nu_{s^{\prime},i+1}}\right\|}_{p}^{p}\leq
2^{p-1}{\left\|{\nu_{s,i}}\right\|}_{p}^{p}\right]\geq\Pr_{x\sim\nu^{t}}\left[{\left\|{\nu_{s^{\prime},i+1}}\right\|}_{p}^{p}\leq
2^{(i+1)(p-1)}/n^{p-1}\right]\geq 1-\frac{1}{2^{7}n^{2}}$

which implies:

$\displaystyle\Pr_{x\sim\nu^{t},s^{\prime}\sim\tau(s,x)}\left[\exists
j\in[t]:\nu_{s^{\prime},i+1}(x_{j})\geq\frac{1}{n^{3}}\right]\geq\frac{1}{2^{7}n^{2}}\,.$

The definition of $\nu_{s^{\prime},i+1}$ ensures that $\nu_{s^{\prime},i+1}$
is precisely the distribution of output values if the algorithm and adversary
are run for $t(\ell-i-1)$ steps starting from state $s^{\prime}$. The
probability that the algorithm fails because the final output overlaps with
$x$ is then

$\displaystyle\Pr_{x\sim\nu_{s,i}^{t},s^{\prime}\sim\tau(s,x),y\sim\nu_{s^{\prime},i+1}}[\exists
j\in[t]:x_{j}=y]$
$\displaystyle=\mathbb{E}_{x\sim\nu_{s,i}^{t},s^{\prime}\sim\tau(s,x)}\Pr_{y\sim\nu_{s^{\prime},i+1}}[\exists
j\in[t]:x_{j}=y]$
$\displaystyle=\mathbb{E}_{x\sim\nu_{s,i}^{t},s^{\prime}\sim\tau(s,x)}\sum_{j\in[t]}\nu_{s^{\prime},i+1}(x_{j})$
$\displaystyle\geq\mathbb{E}_{x\sim\nu_{s,i}^{t},s^{\prime}\sim\tau(s,x)}\max_{j\in[t]}\nu_{s^{\prime},i+1}(x_{j})$
$\displaystyle\geq\frac{1}{n^{3}}\Pr_{x\sim\nu_{s,i}^{t},s^{\prime}\sim\tau(s,x)}\left[\max_{j\in[t]}\nu_{s^{\prime},i+1}(x_{j})\geq\frac{1}{n^{3}}\right]$
$\displaystyle\geq\frac{1}{n^{3}}\cdot\frac{1}{2^{7}n^{2}}=\frac{1}{2^{7}n^{5}}$

Thus, the failure probability of the algorithm as of $(s,i)$ is $\geq
1/(2^{7}n^{5})\geq 1/(16n)^{5}\geq 1/(16n)^{2(\ell-i)+3}$; this completes the
proof of $P(i)$.

With the proof by induction complete, the statement $P(0)$ implies that for
any $s\in\Sigma$, because
${\left\|{\nu_{s,0}}\right\|}_{p}^{p}\geq\frac{1}{n^{p-1}}$ always holds, the
probability that $\mathcal{A}$ gives an incorrect answer when run against the
adversary on a stream of length $t\ell=\hat{r}$ is $\geq
1/(16n)^{2\ell+3}\geq\frac{1}{(16n)^{2\log n+7}}$. This contradicts the given
fact that $\mathcal{A}$’s error is less than this, so the assumption that
$\log|\Sigma|\leq\frac{t}{2^{9}(\log n)^{2}}-2\log n-6$ must be incorrect; and
instead we must have

$\displaystyle\log|\Sigma|$ $\displaystyle\geq\frac{t}{2^{9}(\log
n)^{2}}-2\log n-6\geq\frac{{\left\lfloor{r/{\left\lceil{\log
n+1}\right\rceil}}\right\rfloor}}{2^{9}(\log n)^{2}}-2\log n-6$
$\displaystyle=\Omega(r/(\log n)^{3}-\log n)\,.$ (8)

To handle the case of small $r$, we note that a white-box algorithm
$\mathcal{B}$ for $\textsc{mif}(n,r)$ with error $\delta\leq
1/\left(16n\right)^{2\log n+7}$ can be used to solve the
$\textsc{avoid}(n,r,1)$ communication task. Here, Alice, on being given a set
$A\subseteq\binom{[n]}{r}$, runs an instance of $\mathcal{B}$ on a sequence
containing the elements of $A$ in some order; she then sends the state of the
instance to Bob, who queries the instance for an output, and reports that
value. This communication protocol has the same error probability as
$\mathcal{B}$; by Lemma 2, it requires

$\displaystyle\geq\min\left(\log(r+1),\log\frac{\log{1/\delta}}{\log{en/r}}\right)\geq\log(\min(r+1,2\log
n+7))\geq 1$

bits of communication; thus $\mathcal{B}$ requires at least one bit of state.
Since $\max(1,z/a-b)\geq z/(a(1+b))$, this lets us find a more convenient
corollary for Eq. 8; that $\log|\Sigma|=\Omega(r/(\log n)^{4})$. ∎

We will now prove Lemma 14. It relies on the following technical claim about
probability distributions; which _roughly_ implies that when a distribution is
split into a small number of regions on which it is approximately uniform, a
specific sum of powers of the weight and density of each region has a lower
bound.

######  Claim 15.

Define $m_{\phi}(K)$ to be the minimum value of distribution $\phi$ on the set
$K$, so $m_{\phi}(K):=\min_{i\in K}\phi(i)$.

Let $p>1$, $\beta\in(0,1]$, and $n\geq 2$. For any distribution $\nu$ on
$[n]$, there exists a collection of disjoint sets $\\{H_{i}\\}_{i\in J}$ for
some $|J|\leq\frac{3}{\beta}\log n$ where:

$\displaystyle\sum_{i\in
J}(m_{\nu}(H_{i}))^{p-1}\frac{(\nu(H_{i}))^{p}}{\|\nu\|_{p}^{p}}$
$\displaystyle\geq\frac{(1-\frac{1}{n})^{p}}{2^{\beta(2p-1)}|J|^{(p-1)p/(2p-1)}n^{(p-1)^{2}/(2p-1)}}$
(9)
$\displaystyle\geq\frac{(1-\frac{1}{n})^{p}}{2^{\beta(2p-1)}|J|^{(p-1)}n^{(p-1)^{2}}}\,.$
(10)

Furthermore, we have $\max_{i\in J}m_{\nu}(H_{i})\geq 1/(n2^{\beta})$, and
$\min_{i\in J}m_{\nu}(H_{i})\geq 1/n^{2}$.

###### Proof.

(Of Lemma 14.) In order to avoid awkward expressions like $M(x,R)(i)$, we
define $\widetilde{\mu}_{x}:=M(x,R)$. We also use the notation
$a^{+}:=\max(0,a)$. Throughout the proof we shall assume $n\geq 2$, as in the
case $n=1$ it is easy to prove that no such map $M$ exists.

This proof has two main stages. The first establishes that, for a small
fraction of vectors $x$ drawn from $\nu^{t}$, the distribution
$\widetilde{\mu}_{x}$ will probably have significant mass in the same area as
$\nu^{t}$, while not being much more concentrated (according to
${\left\|{\cdot}\right\|}_{p}^{p}$) than $\widetilde{\mu}_{x}$, and avoids
$x$. The second part will show that such distributions can avoid only small
fraction of vectors sampled from $\nu^{t}$; together, these stages imply the
range of $M$ must be large.

Given a real random variable $W$, with $\mathbb{E}W\geq y$, and $0\leq
W\leq\eta y$, we have

$\displaystyle\Pr[W\geq\alpha y]=1-\Pr[W\leq\alpha y]\geq 1-\Pr[(\eta
y-W)\geq(\eta-\alpha)y]\geq 1-\frac{\eta
y-y}{(\eta-\alpha)y}\geq\frac{1-\alpha}{\eta}\,.$ (11)

Let $\beta\in(0,1]$ be a parameter chosen later. Apply 15 to $\nu$ with this
$\beta$ and the given $p$, producing disjoint sets $\\{H_{i}\\}_{i\in J}$. For
any $i\in J$, we have
$\mathbb{E}_{X\sim\nu^{t},R}\widetilde{\mu}_{X}=\nu(H_{i})$. Now applying
Jensen’s inequality to convex functions of the form $f(a)=((a-b)^{+})^{p}$
gives:

$\displaystyle\mathbb{E}_{X\sim\nu^{t},R}((\widetilde{\mu}_{X}(H_{i})-\delta|H_{i}|)^{+})^{p}$
$\displaystyle\geq((\nu(H_{i})-\delta|H_{i}|)^{+})^{p}\qquad\text{which
implies}$ $\displaystyle\mathbb{E}_{X\sim\nu^{t},R}[\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\widetilde{\mu}_{X}(H_{i})-\delta|H_{i}|)^{+})^{p}]$
$\displaystyle\geq\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\nu(H_{i})-\delta|H_{i}|)^{+})^{p}\,.$

Next, for any $x\in[n]^{t}$,

$\displaystyle\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\widetilde{\mu}_{x}(H_{i})-\delta|H_{i}|)^{+})^{p})\leq\max_{i\in
J}m_{\nu}(H_{i})^{p-1}\leq(4n)^{p}\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}(\nu(H_{i})-\delta|H_{i}|)^{p})\,,$

because as noted in 15, for the $i$ maximizing $m_{\nu}(H_{i})$, we have
$\nu(H_{i})\geq|H_{i}|\frac{1}{n2^{\beta}}\geq\frac{|H_{i}|}{2n}$, so
$\nu(H_{i})-\delta|H_{i}|\geq|H_{i}|(\frac{1}{2n}-\frac{1}{n^{3}})\geq 1/4n$.
Note that $(4n)^{p}\leq 4^{2}(n^{1+1/\log n})=2^{5}n$. Applying Eq. 11 thus
yields:

$\displaystyle\Pr_{X\sim\nu^{t},R}\left[\begin{aligned} &\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\widetilde{\mu}_{X}(H_{i})-\delta|H_{i}|)^{+})^{p}\quad\geq\\\
&\quad\left(1-\frac{1}{n}\right)\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\nu(H_{i})-\delta|H_{i}|)^{+})^{p}\end{aligned}\right]\geq\frac{1}{n}\cdot\frac{1}{(4n)^{p}}\geq\frac{1}{2^{5}n^{2}}\,.$

Intersecting this event with that of Eq. 5 implies the probability that all
three of the following conditions hold is $\geq\frac{1}{2^{6}n^{2}}$:

$\displaystyle\text{(a)}:\qquad$
$\displaystyle{\left\|{\widetilde{\mu}_{X}}\right\|}_{p}^{p}\leq
D^{p-1}{\left\|{\nu}\right\|}_{p}^{p}$ $\displaystyle\text{(b)}:\qquad$
$\displaystyle\forall j\in[t]:\widetilde{\mu}_{X}(X_{j})\leq\delta$
$\displaystyle\text{(c)}:\qquad$ $\displaystyle\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\widetilde{\mu}_{X}(H_{i})-\delta|H_{i}|)^{+})^{p}\geq(1-\frac{1}{n})\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\nu(H_{i})-\delta|H_{i}|)^{+})^{p}\,.$

By the averaging argument, there must exist a value $R^{\prime}\in\Omega$ for
which, when $R=R^{\prime}$, the above three conditions hold with at least the
same probability. In other words, when replacing $\widetilde{\mu}_{X}$ with
$\mu_{X}:=M(x,R^{\prime})$, the conditions still holds with probability $\geq
1/{2^{6}n^{2}}$. Now let $G:=\\{\mu_{x}:x\in[n]^{t}\text{ satisfies
(a),(c)}\\}$ and define $L_{\pi}:=\\{i\in[n]:\pi(i)\leq\delta\\}$. Therefore,

$\displaystyle\frac{1}{2^{6}n^{2}}$
$\displaystyle\leq\Pr_{X\sim\nu^{t}}[\mu_{X}\in G\land(\forall
j\in[t]:\mu_{X}(X_{j})\leq\delta)]$ $\displaystyle=\sum_{y\in
G}\Pr_{X\sim\nu^{t}}[\mu_{X}=\mu_{y}\land(\forall
j\in[t]:\mu_{X}(X_{j})\leq\delta)]$ $\displaystyle\leq\sum_{y\in
G}\Pr_{X\sim\nu^{t}}[(\forall j\in[t]:\mu_{y}(X_{j})\leq\delta)]$
$\displaystyle=\sum_{y\in
G}\prod_{j\in[t]}\Pr_{X_{j}\sim\nu}[\mu_{y}(X_{j})\leq\delta]=\sum_{y\in
G}(\nu(L_{\mu_{y}}))^{t}$ (12)

We will now prove an upper bound on $\nu(L_{\mu_{y}})$ for any given $y\in G$.
Observe that for any sequence $a_{1},\ldots,a_{\ell}$ of nonnegative real
numbers,
$\sum_{i=1}^{\ell}a_{i}^{p}\geq(\sum_{i=1}^{\ell}a_{i})^{p}/\ell^{p-1}$; this
follows from Hölder’s inequality. As the sets $H_{i}\setminus L_{\mu_{y}}$ are
disjoint,

$\displaystyle{\left\|{\mu_{y}}\right\|}_{p}^{p}=\sum_{i\in[n]}\mu_{y}(i)^{p}\geq\sum_{i\in
J}\frac{\mu_{y}(H_{i}\setminus L_{\mu_{y}})^{p}}{|H_{i}\setminus
L_{\mu_{y}}|^{p-1}}\,.$

The definition of $L_{\mu_{y}}$ implies $\mu_{y}(H_{i}\setminus
L_{\mu_{y}})\geq\max(0,\mu_{y}(H_{i})-\delta|H_{i}|)$. Also, because the
minimum value of $\nu$ on $H_{i}\setminus L_{\mu_{y}}$ is at least
$m_{\nu}(H_{i})$, we have

$\displaystyle|H_{i}\setminus L_{\mu_{y}}|\leq\frac{\nu(H_{i}\setminus
L_{\mu_{y}})}{m_{\nu}(H_{i})}\leq\frac{1-\nu(L_{\mu_{y}})}{m_{\nu}(H_{i})}$

Therefore,

$\displaystyle{\left\|{\mu_{y}}\right\|}_{p}^{p}$ $\displaystyle\geq\sum_{i\in
J}\frac{((\mu_{y}(H_{i})-\delta|H_{i}|)^{+})^{p}}{(1-\nu(L_{\mu_{y}}))^{p-1}/m_{\nu}(H_{i})^{p-1}}$
$\displaystyle=\frac{1}{(1-\nu(L_{\mu_{y}}))^{p-1}}\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\mu_{y}(H_{i})-\delta|H_{i}|)^{+})^{p}$
$\displaystyle\geq\frac{1-1/n}{(1-\nu(L_{\mu_{y}}))^{p-1}}\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}((\nu(H_{i})-\delta|H_{i}|)^{+})^{p}\qquad\text{by
condition (c)}$
$\displaystyle\geq\frac{1-1/n}{(1-\nu(L_{\mu_{y}}))^{p-1}}\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}\left(\left(1-\frac{1}{n}\right)\nu(H_{i})\right)^{p}$

The last step uses the fact that for all $i\in J$,
$\delta|H_{i}|\leq\frac{1}{2n^{3}}|H_{i}|\leq\frac{1}{n}|H_{i}|\min_{j\in\bigcup
H_{i}}\nu(j)\leq\frac{1}{n}\nu(H_{i})$. We now apply condition (a), and divide
both sides by ${\left\|{\nu}\right\|}_{p}^{p}$:

$\displaystyle D^{p-1}$
$\displaystyle\geq\frac{{\left\|{\mu_{y}}\right\|}_{p}^{p}}{{\left\|{\nu}\right\|}_{p}^{p}}\geq\frac{(1-1/n)^{p+1}}{(1-\nu(L_{\mu_{y}}))^{p-1}}\sum_{i\in
J}m_{\nu}(H_{i})^{p-1}\frac{(\nu(H_{i}))^{p}}{{\left\|{\nu}\right\|}_{p}^{p}}$
$\displaystyle\geq\frac{(1-1/n)^{p+1}}{(1-\nu(L_{\mu_{y}}))^{p-1}}\frac{(1-1/n)^{p}}{2^{\beta(2p-1)}(\frac{2}{\beta}\log
n)^{(p-1)}n^{(p-1)^{2}}}\,.\qquad\text{by
\lx@cref{creftypecap~refnum}{claim:distribution-helper}}$

Rearranging this inequality to isolate $\nu(L_{\mu_{y}})$ reveals:

$\displaystyle\nu(L_{\mu_{y}})\leq
1-\frac{1}{D}\left(\frac{(1-1/n)^{(2p-1)/(p-1)}}{2^{\beta(2p-1)/(p-1)}(\frac{2}{\beta}\log
n)n^{(p-1)}}\right)$ (13)

The right hand side is close to its minimum when $\beta=p-1=1/\log n$: Thus:

$\displaystyle\nu(L_{\mu_{y}})$ $\displaystyle\leq
1-\frac{1}{D}\left(\frac{(1-1/n)^{2+\log n}}{2^{(2+\log n)/\log n}(2(\log
n)^{2})2^{\log n/\log n}}\right)$ $\displaystyle\leq
1-\frac{1}{D}\left(\frac{(1-1/n)^{2+\log n}}{16\cdot 2^{2/\log
n}}\right)\frac{1}{(\log n)^{2}}$ $\displaystyle\leq 1-\frac{1}{2^{9}D(\log
n)^{2}}$

since $(1-1/n)^{2+\log n}/(16\cdot 2^{2/\log n})$ is increasing in $n$, and
when evaluated at $n=2$ gives $2^{-9}$. Now we are in a position to simplify
Eq. 12; with this upper bound.

$\displaystyle\frac{1}{2^{6}n^{2}}\leq\sum_{y\in
G}\left(1-\frac{1}{2^{9}D(\log
n)^{2}}\right)^{t}=|G|\left(1-\frac{1}{2^{9}D(\log
n)^{2}}\right)^{t}\leq|G|\exp\left(-\frac{t}{2^{9}D(\log n)^{2}}\right)\,.$

Since $G$ is a subset of $\operatorname{range}(M)$, we have
$\log|\operatorname{range}(M)|\geq\log|G|$; rearranging the above to isolate
$|G|$ gives:

$\displaystyle\log|\operatorname{range}(M)|$
$\displaystyle\geq\log|G|\geq\frac{t}{2^{9}(\ln 2)D(\log
n)^{2}}-\log(2^{6}n^{2})$ $\displaystyle\geq\frac{t}{2^{9}D(\log
n)^{2}}-2\log(n)-6\,.$

∎

Finally, we prove 15:

###### Proof.

For all $i\in\mathbb{Z}_{\geq 0}$, let $w_{i}:=2^{i\beta}/n^{2}$, and let
$H_{i}:=\\{j\in[n]:\nu(j)\in[w_{i},w_{i+1})$. Define
$J:=\\{i\in\mathbb{Z}_{\geq 0}:H_{i}\neq\emptyset\\}$. We first prove some
basic properties of $J$ and the $H_{i}$.

  * •

If $i\geq{\left\lfloor{\frac{3}{\beta}\log n}\right\rfloor}$, then $w_{i}\geq
2^{{\left\lfloor{\frac{3}{\beta}\log
n}\right\rfloor}\beta}/n^{2}>2^{\frac{2}{\beta}(\log n)\beta}/n^{2}\geq 1$;
since $\max_{j\in[n]}\nu(j)\leq 1$, it follows such $H_{i}$ must be empty.
Thus $J\subseteq\\{0,\ldots,{\left\lfloor{\frac{3}{\beta}\log
n}\right\rfloor}-1\\}$, and hence $|J|\leq\frac{3}{\beta}\log n$.

  * •

Because $\min_{j\in[n]}\nu_{(}j)\geq 1/n$, we are guaranteed that for some $i$
with $w_{i}\geq 1/(n2^{\beta})$, $H_{i}\neq\emptyset$. Thus $\max_{i\in
J}m_{\nu}(H_{i})\geq 1/(n2^{\beta})$. Similarly, $\min_{i\in
J}m_{\nu}(H_{i})\geq\min_{i\in J}w_{i}\geq 1/n^{2}$.

Now, to prove the main part of the result, Eq. 10. Let
$K=[n]\setminus\bigcup_{i\in J}H_{i}=\\{j\in[n]:\nu(j)<1/n^{2}\\}$. First, we
observe that the contribution of the $j\in K$ to
${\left\|{\nu}\right\|}_{p}^{p}$ is small and can be easily be accounted for:

$\displaystyle n\frac{1}{n^{p}}$
$\displaystyle\leq\sum_{j\in[n]}\nu(j)^{p}=\sum_{j\in\bigcup_{i\in
J}H_{i}}\nu(j)^{p}+\sum_{j\in K}\nu(j)^{p}\leq\sum_{j\in\bigcup_{i\in
J}H_{i}}\nu(j)^{p}+n\left(\frac{1}{n^{2}}\right)^{p}$
$\displaystyle\leq\sum_{j\in\bigcup_{i\in
J}H_{i}}\nu(j)^{p}+\frac{1}{n^{p}}\sum_{j\in[n]}\nu(j)^{p}\,.$

This implies
${\left\|{\nu}\right\|}_{p}^{p}\leq(1-1/n^{p})^{-1}\sum_{j\in\bigcup_{i\in
J}H_{i}}\nu(j)^{p}\leq(1-1/n)^{-1}\sum_{j\in\bigcup_{i\in J}H_{i}}\nu(j)^{p}$.

Now, writing $n_{i}=|H_{i}|$, we have $n_{i}w_{i}\leq\nu(H_{i})\geq
2^{\beta}n_{i}w_{i}$, and so:

$\displaystyle\sum_{i\in
J}(m_{\nu}(H_{i}))^{p-1}\frac{(\nu(H_{i}))^{p}}{{\left\|{\nu}\right\|}_{p}^{p}}\geq\frac{(1-1/n)\sum_{i\in
J}w_{i}^{p-1}(w_{i}n_{i})^{p}}{\sum_{i\in
J}n_{i}(2^{\beta}w_{i})^{p}}=\frac{1-1/n}{2^{\beta p}}\frac{\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}}{\sum_{i\in J}w_{i}^{p}n_{i}}\,.$ (14)

We shall later need the following inequality:

$\displaystyle\sum_{i\in J}n_{i}w_{i}\geq 2^{-\beta}\sum_{j\in\bigcup_{i\in
J}H_{i}}\nu(j)\geq 2^{-\beta}(\sum_{j\in[n]}\nu(j)-\sum_{j\in K}\nu(j))\geq
2^{-\beta}\left(1-\frac{1}{n}\right)\,.$ (15)

With this and properties of the $n_{i}$, we can lower bound Eq. 14 by using
Hölder’s inequality several times:

$\displaystyle\sum_{i\in J}w_{i}^{p}n_{i}$ $\displaystyle=\sum_{i\in
J}\left(w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{p}{2p-1}}\left(n_{i}^{-(p-1)}\right)^{\frac{p-1}{2p-1}}$
$\displaystyle\leq\left(\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{p}{2p-1}}\left(\sum_{i\in
J}n_{i}^{-(p-1)}\right)^{\frac{p-1}{2p-1}}$ by Hölder
$\displaystyle\leq\left(\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{p}{2p-1}}|J|^{\frac{p-1}{2p-1}}$ since
$n_{i}\geq 1$ (16) $\displaystyle\sum_{i\in J}w_{i}n_{i}$
$\displaystyle=\sum_{i\in
J}\left(w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{1}{2p-1}}\left(n_{i}^{1/2}\right)^{\frac{2p-2}{2p-1}}$
$\displaystyle\leq\left(\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{1}{2p-1}}\left(\sum_{i\in
J}n_{i}^{1/2}\right)^{\frac{2p-2}{2p-1}}$ by Hölder
$\displaystyle\leq\left(\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{1}{2p-1}}\left(\left(\sum_{i\in
J}n_{i}\right)^{1/2}|J|^{1/2}\right)^{\frac{2p-2}{2p-1}}$ by Cauchy-Schwarz
$\displaystyle\leq\left(\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}\right)^{\frac{1}{2p-1}}n^{\frac{p-1}{2p-1}}|J|^{\frac{p-1}{2p-1}}$
since $\sum_{i\in J}n_{i}\leq n$. (17)

Multiplying Eq. 16 by Eq. 17 raised to the $(p-1)$st power gives:

$\displaystyle\left(\sum_{i\in J}w_{i}^{p}n_{i}\right)\left(\sum_{i\in
J}w_{i}n_{i}\right)^{p-1}$ $\displaystyle\leq\left(\sum_{i\in
J}w_{i}^{2p-1}n_{i}^{p}\right)|J|^{\frac{p-1}{2p-1}}(n^{\frac{p-1}{2p-1}})^{p-1}(|J|^{\frac{p-1}{2p-1}})^{p-1}\,,$

which implies

$\displaystyle\frac{\sum_{i\in J}w_{i}^{2p-1}n_{i}^{p}}{\sum_{i\in
J}w_{i}^{p}n_{i}}\geq\frac{\left(\sum_{i\in
J}w_{i}n_{i}\right)^{p-1}}{|J|^{\frac{(p-1)p}{2p-1}}n^{\frac{(p-1)^{2}}{2p-1}}}\geq\frac{(1-\frac{1}{n})^{p-1}}{2^{\beta(p-1)}|J|^{\frac{(p-1)p}{2p-1}}n^{\frac{(p-1)^{2}}{2p-1}}}\,.$

Substituting this into Eq. 14 gives:

$\displaystyle\sum_{i\in
J}(m_{\nu}(H_{i}))^{p-1}\frac{(\nu(H_{i}))^{p}}{{\left\|{\nu}\right\|}_{p}^{p}}\geq\frac{(1-\frac{1}{n})^{p}}{2^{\beta(2p-1)}|J|^{\frac{(p-1)p}{2p-1}}n^{\frac{(p-1)^{2}}{2p-1}}}\,.$

∎

##  9 Random start and pseudo-deterministic models

######  Theorem 16.

The space needed for an algorithm in the random-start model to solve
$\textsc{mif}(n,r)$ against adaptive adversaries, with error
$\leq\delta\leq\frac{1}{6}$, satisfies $s\geq
S^{PD}_{1/3}(n,{\left\lfloor{r/(2s+2)}\right\rfloor})$.

This theorem implies that _if_ it is the case that
$S^{PD}_{1/3}(\textsc{mif}(n,r))=\Omega(r^{c}/\operatorname{polylog}(n))$ for
some constant $c>0$, then it follows that
$S^{RS}_{1/6}(\textsc{mif}(n,r))=\Omega(r^{c/(1+c)}/\operatorname{polylog}n)$.
Specifically, if $s=S^{RS}_{1/6}(\textsc{mif}(n,r))$, then Theorem 16 would
imply $s\geq
S^{PD}_{1/3}(n,{\left\lfloor{r/(2s+2)}\right\rfloor})=\Omega((r/s)^{c}/\operatorname{polylog}(n))$;
multiplying both sides by $s^{c}$ and raising them to the $1/(c+1)$st power
gives $s\geq\Omega(r^{c/(1+c)}/\operatorname{polylog}(n))$.

###### Proof.

Let $\Sigma$ be the set of all states of the random-start algorithm
$\mathcal{A}$, and let $\mathcal{D}$ be the distribution of the initial states
of the algorithm. Write $B\sim\mathcal{A}$ to indicate that $B$ is an instance
of $\mathcal{A}$, i.e., with initial state drawn from distribution
$\mathcal{D}$. Let $\ell=2{\left\lceil{\log(|\Sigma|)}\right\rceil}+2$, and
let $t={\left\lfloor{r/\ell}\right\rfloor}$. For any partial stream $\sigma$
of elements, and instance $B$ of $\mathcal{A}$, we let $B(\sigma)$ be the
sequence of $|\sigma|$ outputs made by $B$ after it processes each element in
$\sigma$.

Consider an adversary $E$ which does the following. Given $\sigma$ the stream
it has already passed to the algorithm, and $\omega$ the sequence of outputs
that $\mathcal{A}$ produced in response to $\sigma$, the adversary checks if
there exists any $x\in[n]^{t}$ for which

$\displaystyle\forall
y\in[n]^{t}:\Pr_{B\sim\mathcal{A}}[B(\sigma.x)=\omega.y\mid
B(\sigma)=\omega]\leq\frac{2}{3}\,.$ (18)

If so, it sends $x$ to $\mathcal{A}$, appends $x$ to $\sigma$ and the returned
$t$ elements to $\omega$, and repeats the process. If no such $x$ exists, then
the adversary identifies the $z\in[n]^{t}$ which maximizes:

$\displaystyle\Pr_{B\sim\mathcal{A}}[B(\sigma.z)\text{ is incorrect}\mid
B(\sigma)=\omega]\,.$ (19)

and sends it to the algorithm. (The adversary gives up if either the algorithm
manages to give a valid output after $z$, or after it has sent $\ell$ sets of
$t$ elements to the algorithm.)

We claim that if $\log|\Sigma|<S^{PD}_{1/3}(\textsc{mif}(n,t))$, then $E$
makes the algorithm fail with probability $\geq 1/6$. There are two ways that
$E$ can be forced to give up: if it tries more than $\ell-1$ times to find a
point where there is no $x\in[n]^{t}$ satisfying Eq. 18, or if the $z$ it
sends fails to produce an error.

Assume that the adversary finds a value of $x$ satisfying Eq. 18, for each of
the $\ell$ tries it makes. Let $x_{1},\ldots,x_{\ell}\in[n]^{t}$ be these
values, and let $y_{1},\ldots,y_{\ell}\in[n]^{t}$ be the outputs of the
algorithm. By applying Eq. 18 repeatedly, we have:

$\displaystyle\Pr_{B\sim\mathcal{A}}[B(x_{1}.\ldots.x_{\ell})=y_{1}.\ldots.y_{\ell}]$
$\displaystyle=\Pr_{B\sim\mathcal{A}}[B(x_{1}.\ldots.x_{\ell})=y_{1}.\ldots.y_{\ell}\mid
B(x_{1}.\ldots.x_{\ell-1})=y_{1}.\ldots.y_{\ell-1}]$
$\displaystyle\qquad\cdot\Pr_{B\sim\mathcal{A}}[B(x_{1}.\ldots.x_{\ell-1})=y_{1}.\ldots.y_{\ell-1}\mid
B(x_{1}.\ldots.x_{\ell-2})=y_{1}.\ldots.y_{\ell-2}]$
$\displaystyle\qquad\cdot\Pr_{B\sim\mathcal{A}}[B(x_{1})=y_{1}]$
$\displaystyle\leq(2/3)^{\ell}\,.$

Let $C\subseteq\Sigma$ be the set of initial states of the algorithm for which
the adversary finds a sequence satisfying Eq. 18, $\ell$ times. Because the
algorithm is deterministic after the initial state is chosen, each $s\in C$
has a corresponding transcript
$(\sigma_{s},\omega_{s})\in[n]^{t\ell}\times[n]^{t\ell}$ that occurs when $E$
is run against an instance of $\mathcal{A}$ started from $s$. Therefore,

$\displaystyle\Pr_{s\sim\mathcal{D}}[s\in C]$ $\displaystyle=\sum_{s\in
C}\Pr_{s^{\prime}\sim cD}[s=s^{\prime}]\leq\sum_{s\in
C}\Pr_{B\sim\mathcal{A}}[B(\sigma_{s})=\omega_{s}]$
$\displaystyle\leq|\Sigma|\left(\frac{2}{3}\right)^{\ell}\leq
2^{\log|\Sigma|}\left(\frac{2}{3}\right)^{2\log(|\Sigma|)+2}\leq\left(\frac{2}{3}\right)^{2}\leq\frac{1}{2}$

Thus, the chance that $E$ fails to find a point where no $x$ satisfying Eq. 18
exists is $\leq\frac{1}{2}$.

To bound the second way in which $E$ can fail, we let $(\sigma,\omega)$ be a
partial transcript of the algorithm for which no $x\in[n]^{t}$ satisfies Eq.
18. Assume the probability that $z$ produces an error is $<1/3$. Then we have:

$\displaystyle\forall z\in[n]^{t},\exists y_{z}\in[n]^{t}:\qquad$
$\displaystyle\Pr_{B\sim\mathcal{A}}[B(\sigma.z)=\omega.y_{z}\mid
B(\sigma)=\omega]\geq\frac{2}{3}$ (20) $\displaystyle\forall
z\in[n]^{t}:\qquad$ $\displaystyle\Pr_{B\sim\mathcal{A}}[B(\sigma.z)\text{ is
correct}\mid B(\sigma)=\omega]\geq\frac{2}{3}\,.$ (21)

These conditions together imply that $\omega.y_{z}$ is a correct
$\textsc{mif}(n,r)$ output sequence for $\sigma.z$. As a result, we can use
$\mathcal{A}$’s behavior after $(\sigma,\omega)$ to construct a pseudo-
deterministic algorithm $\Psi$ for $MIF(n,t)$. To initialize $\Psi$, we sample
an initial state $B\sim\mathcal{A}$ conditioned on the event that
$B(\sigma)=\omega$, and then send the elements of $\sigma$ to $B$. After this,
when $\Psi$ receives an element $e$, we send $e$ to $B$, and report the
element $B$ outputs as the output of $\Psi$. By Eqs. 20 and 21, the sequence
of outputs produced by $\Psi$ on any input $x$ in $[n]^{t}$ will, with
probability $\geq 2/3$, be the (valid) output $y_{z}$. Thus, $\Psi$ solves
$MIF(n,t)$ with $\leq 1/3$ error – which, under the assumption that
$\log|\Sigma|<S^{PD}_{1/3}(\textsc{mif}(n,t))$, is impossible. Thus the $z$
chosen by the adversary makes the algorithm err with probability $\geq 1/3$,
conditional on it having found $(\sigma,\omega)$ with no $x\in[n]^{t}$
satisfying Eq. 18. The probability that the the adversary succeeds is then
$\geq\nicefrac{{1}}{{3}}\cdot\nicefrac{{1}}{{2}}=1/6$; this contradicts the
assumption that $\mathcal{A}$ has error $\leq 1/6$ against any adversary,
which implies that we must instead have $\log|\Sigma|\geq
S^{PD}_{1/3}(\textsc{mif}(n,t))$. ∎

We now present a random-start algorithm whose total space with random bits
included improves slightly on Algorithm 3.

######  Theorem 17.

Algorithm 5 solves $\textsc{mif}(n,r)$ against adaptive adversaries, with
error $\delta$, and can be implemented using
$O\left(\left(\sqrt{r}+\frac{r^{2}}{n}\right)\log n\right)$ bits of space,
_including_ all random bits used.

Figure 6: This diagram shows the behavior of Algorithm 5 on an example input,
if we were to set $w=3$ and $t=4$. The top row of squares corresponds to the
set $[n]$. In the top row, cells contain a pink dot if the corresponding
element has already been seen in the stream. For the bottom row, we have
assumed for ease of presentation that $(L_{1},L_{2},L_{3},L_{4})=(1,2,3,4)$.
The four wide blocks correspond to the sets $\\{w(L_{j}-1)-1,\ldots,wL_{j}\\}$
for each $j\in[4]$. The blocks shaded dark blue (here only one) indicate the
blocks whose indices are contained in $J$. The vector $x$ tracks which
elements in the current block ($L_{c}$ at $c=2$) were seen in the stream. For
indices $>c$, $J$ tracks which blocks contain elements from the stream. If the
stream elements in this example had arrived in a different order (say,
elements 4 and 6 arriving first), then $J$ might have had the value
$\\{2,3\\}$.  Algorithm 5 An adversarially robust, “random-start” algorithm
for $\textsc{mif}(n,r)$ with error $\leq\delta$

1:Assume $r<n/32$ and $\delta\geq e^{-r/6}$ – otherwise, use Algorithm 1

2:Let $w={\left\lfloor{\min(\sqrt{r\log n},\frac{n}{32r},\frac{r}{6\ln
1/\delta})}\right\rfloor}$, the block size

3:Let $t={\left\lceil{2r/w}\right\rceil}$

4:

5:Initialization:

6:Let $L=\\{L_{1},\ldots,L_{t}\\}$ be a sequence of $t$ elements from
$[{\left\lfloor{n/w}\right\rfloor}]$ without repetitions, chosen uniformly at
random.

7:$c\leftarrow 1$, an integer in the range $\\{1,\ldots,t\\}$

8:$J\leftarrow\emptyset$, a subset of $[t]$

9:$x\leftarrow(0,\ldots,0)$, a vector in $\\{0,1\\}^{w}$

10:

11:Update($e\in[n]$):

12:Let $h={\left\lceil{e/w}\right\rceil}$

13:if $\exists j:L_{j}=h$ and $j>c$ then

14: $J\leftarrow J\cup\\{j\\}$

15:if $h=L_{c}$ then

16: $x_{e-w(h-1)}\leftarrow 1$

17:if $x=(1,1,\ldots,1)$ then

18: $c\leftarrow c+1$

19: while $c\in J$ do

20: $c\leftarrow c+1$

21: $x\leftarrow(0,0,\ldots,0)$.

22:if $c>t$ then

23: abort

24:

25:Query:

26:Let $j$ be the least value in $[w]$ for which $x_{j}=0$.

27:output: $w(L_{c}-1)+j$

###### Proof.

By the $k$th block, we refer to the set
$B_{k}=\\{w(L_{k}-1)+1,\ldots,wL_{k}\\}$.

First, we observe that unless Algorithm 5 aborts, it will always output a
valid value. At all times, the integer $c$ indicates a value $L_{c}$ for which
the set $B_{c}$ is not entirely contained by the stream. The contents of the
vector $x$ are updated by Lines 15 and 16 to ensure that iff some $e\in B_{c}$
was given by the stream since the last time $c$ was changed, then the vector
entry $x_{e-w(c-1)}$ corresponding to element $e$ has value $1$. On the other
hand, when the value of $c$ changes, Lines 18 through 20 ensure that for the
new value of $c$, no element of $B_{c}$ was in the stream so far. This works
because the variable $J$ includes (by Lines 13 and 14) all blocks $B_{d}$ for
$d>c$ which contain a stream element. Thus, after each update, $B_{c}$ always
contains at least one element which was not in the stream so far; and since
the vector $x$ tracks precisely which elements in $B_{c}$ were in the stream,
the query procedure for Algorithm 5 always gives a valid result.

Next, we evaluate the probability that Algorithm 5 aborts. This only happens
if $c>t$. The variable $c$ can increase in two different ways: on Line 20,
which can happen at most once every $w$ elements when the vector $x$ fills up;
and on Line 20, which occurs at most once for each element in $J$. Thus $c\leq
1+{\left\lfloor{r/w}\right\rfloor}+|J|$.

In much the same way that Theorem 8 bounded $|J|$ for Algorithm 3, we prove
here that $|J|\leq t-1-{\left\lfloor{r/w}\right\rfloor}$ with probability
$1-\delta$. Without loss of generality, assume that the adversary is
deterministic, and picks the next element of the stream as a function of the
outputs of the algorithm so far. Denote the elements of the stream by
$e_{1},\ldots,e_{r}$ – these are random variables depending on the algorithm’s
random choices. Say that $i-1$ elements have been processed so far, and the
algorithm receives the $i$th element. Let $X_{i}$ be the indicator random
variable for the event that the size of $J$ will increase. Matching Line 12,
let $h_{i}={\left\lfloor{e_{i}/w}\right\rfloor}$. Abbreviate
$H_{<i}:=\\{h_{1},\ldots,h_{i-1}\\}$, $L_{\leq
c_{i}}:=\\{L_{1},\ldots,L_{c_{i}}\\}$,
$L_{>{c_{i}}}:=\\{L_{{c_{i}}+1},\ldots,L_{t}\\}$; here $c_{i}$ is the value of
the variable $c$ as of Line 12. Then by Line 13, $X_{i}=1$ iff $h_{i}\in
L_{>c_{i}}\setminus H_{<i}$.

Critically, $H_{<i}$ and $h_{i}$ only depend on what the adversary has seen so
far – algorithm outputs whose computation has only involved
$L_{1},\ldots,L_{c_{i}}$ – and not on the contents of $L_{>c_{i}}$.
Conditioning on $(X_{1},\ldots,X_{i-1})$ does constrain $L_{>c_{i}}$, but only
in that it fixes the value of $L_{>c_{i}}\cap H_{<i}$. If we condition on
$L_{\leq c_{i}}$ and $(X_{1},\ldots,X_{i-1})$ (and hence also on $h_{i}$ and
$H_{<i}$), then the set $L_{>c_{i}}\setminus H_{<i}$ is a uniform random
subset of $[{\left\lfloor{n/w}\right\rfloor}]\setminus L_{\leq c_{i}}\setminus
H_{<i}$. The probability that $h_{i}$ is contained in $L_{>c_{i}}\setminus
H_{<i}$ and will be added to $J$ is then:

$\displaystyle\Pr[X_{i}=1\mid X_{1},\ldots,X_{i-1},L_{\leq c_{i}}]$
$\displaystyle=\begin{cases}0&h_{i}\in H_{<i}\cup L_{\leq c_{i}}\\\
\frac{t-c_{i}-|H_{<i}\cap
L_{>c_{i}}|}{{\left\lfloor{n/w}\right\rfloor}-c_{i}-|H_{<i}\setminus L_{\leq
c_{i}}|}&\text{otherwise}\end{cases}$ $\displaystyle\leq\frac{t-|H_{<i}\cap
L_{>c_{i}}|}{{\left\lfloor{n/w}\right\rfloor}-|H_{<i}\setminus L_{\leq
c_{i}}|}\leq\frac{t}{{\left\lfloor{n/w}\right\rfloor}-i}\leq\frac{2t}{{\left\lfloor{n/w}\right\rfloor}}\,.$

In the last step, we used the inequality $i\leq r\leq
16r\leq\frac{1}{2}{\left\lfloor{n/w}\right\rfloor}$. Taking the (conditional)
expectation over $L_{\leq c_{i}}$ yields $\mathbb{E}[X_{i}\mid
X_{1},\ldots,X_{i-1}]\leq 2t/{\left\lfloor{n/w}\right\rfloor}\leq 4tw/n$
Applying the variant on Azuma’s inequality, Lemma 3, with
$z=\max(1,\frac{3n}{4rtw}\ln\frac{1}{\delta})$ gives:

$\displaystyle\Pr\left[\sum_{i=1}^{r}X_{i}\geq r\frac{4tw}{n}(1+z)\right]$
$\displaystyle\leq\exp(-z^{2}/(2+z)r\frac{4tw}{n})$
$\displaystyle\leq\exp(-\frac{4zrtw}{3n})\leq\delta\,.$

We now observe that:

$\displaystyle\frac{4rtw(1+z)}{n}$
$\displaystyle\leq\frac{8rtw}{n}\max\left(1,\frac{3n\ln\frac{1}{\delta}}{2rtw}\right)$
defn. of $z$ $\displaystyle\leq\max\left(\frac{8rtw}{n},6\ln(1/\delta)\right)$
$\displaystyle\leq\max\left(\frac{32r^{2}}{n},6\ln(1/\delta)\right)$ since
$t\leq\frac{4r}{w}$
$\displaystyle\leq\max\left(\frac{r}{w},\frac{r}{w}\right)$ since
$w\leq\frac{n}{32r}$ and $w\leq\frac{r}{6\ln(1/\delta)}$ $\displaystyle\leq
t-{\left\lfloor{r/w}\right\rfloor}\,.$ since $t\geq\frac{2r}{w}$

This implies that at the end of the stream,

$\displaystyle\Pr\left[|J|\geq
t-{\left\lfloor{r/w}\right\rfloor}\right]\leq\Pr\left[|J|=\sum_{i=1}^{r}X_{i}\geq\frac{4rtw(1+z)}{n}\right]\leq\delta\,,$

thereby proving that the algorithm aborts with probability $\leq\delta$.

Finally, we compute the space used by the algorithm. The set $L$ can be stored
as a list of integers, using $t\log n$ bits; the counter $c$ with $\log n$
bits; set $J$ with $t$ bits; and vector $x$ with $w$ bits. The total space
usage $s$ of the algorithm is then:

$\displaystyle s$ $\displaystyle\leq t(1+\log n)+w+\log n$ (22)
$\displaystyle\leq\frac{10r\log n}{w}+w$ since $t\leq\frac{4r}{w}$ and $\log
n\leq\frac{2r\log n}{w}$ (23) $\displaystyle\leq\frac{20r\log n}{w}$ since
$w\leq\sqrt{r\log n}$ (24) $\displaystyle\leq\max\left(40\sqrt{r\log
n},\frac{600r^{2}\log n}{n},240\log\frac{1}{\delta}\log n\right)$ (25)
$\displaystyle=O\left(\sqrt{r\log n}+\frac{r^{2}}{n}\log
n+\log\frac{1}{\delta}\log n\right)\,.$ (26)

Algorithm 5 requires $r<n/32$ and $\delta\geq e^{-r/6}$. If either of these
conditions do not hold, then it is better to use Algorithm 1 instead. When
$r>n/32$, we have $\frac{r^{2}}{n}\log n=\Omega(n\log n)$, and when
$\delta\leq e^{-r/6}$, we have $\log\frac{1}{\delta}\log n=\Omega(r\log n)$,
so using Algorithm 1 here does not worsen the upper bound from Eq. 26.
Consequently, by choosing the better of Algorithm 5 and Algorithm 1, we can
obtain the upper bound from Eq. 26 unconditionally. ∎

It is possible to reduce the space cost of this even further when $r$ is
sufficiently smaller than $n$, by replacing the logic used to find a missing
element inside a given block. When $r=O(\log n)$, one can obtain an
$O\left(r^{1/3}(\log r)^{2/3}\right)$-space algorithm by changing the block
size to be $\hat{w}=\widetilde{O}(n/r^{2})$ instead of $w$, and running a
nested copy of Algorithm 4 configured for $\textsc{mif}(\hat{w},r^{2/3}(\log
r)^{1/3})$ inside each block instead of tracking precisely which elements in
$\\{w(L_{c}-1)+1,\ldots,wL_{c}\\}$ have been seen before.

##  10 Acknowledgements

We thank Amit Chakrabarti and Prantar Ghosh for many helpful discussions.

## References

  * [AB+22] Miklós Ajtai, , Vladimir Braverman, T.S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou.  The white-box adversarial data stream model.  In Proc. 41st ACM Symposium on Principles of Database Systems, page 15–27, 2022.
  * [ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna.  Sublinear algorithms for ($\Delta$\+ 1) vertex coloring.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767–786, 2019.
  * [ACS22] Sepehr Assadi, Andrew Chen, and Glenn Sun.  Deterministic graph coloring in the streaming model.  In Proc. 54th Annual ACM Symposium on the Theory of Computing, pages 261––274, 2022.
  * [BJWY20] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev.  A framework for adversarially robust streaming algorithms.  In Proc. 39th ACM Symposium on Principles of Database Systems, page 63–80, 2020.
  * [BY20] Omri Ben-Eliezer and Eylon Yogev.  The adversarial robustness of sampling.  In Proc. 39th ACM Symposium on Principles of Database Systems, pages 49–62. ACM, 2020.
  * [CGS22] Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl.  Adversarially robust coloring for graph streams.  In Proc. 13th Conference on Innovations in Theoretical Computer Science, pages 37:1–37:23, 2022.
  * [Fei19] Uriel Feige.  A randomized strategy in the mirror game.  arXiv preprint arXiv:1901.07809, 2019.
  * [GGMW20] Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff.  Pseudo-Deterministic Streaming.  In Proc. 20th Conference on Innovations in Theoretical Computer Science, volume 151, pages 79:1–79:25, 2020.
  * [GIPS21] Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam.  On the pseudo-deterministic query complexity of np search problems.  In Proc. 36th Annual IEEE Conference on Computational Complexity, pages 36:1–36:22, 2021.
  * [GS18] Sumegha Garg and Jon Schneider.  The Space Complexity of Mirror Games.  In Proc. 10th Conference on Innovations in Theoretical Computer Science, pages 36:1–36:14, 2018.
  * [Hat02] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, 2002.  Available online at https://pi.math.cornell.edu/~hatcher/AT/ATpage.html. Accessed 2022-07-14.
  * [HKM+20] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer.  Adversarially robust streaming algorithms via differential privacy.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [HW13] Moritz Hardt and David P. Woodruff.  How robust are linear sketches to adaptive inputs?  In Proc. 45th Annual ACM Symposium on the Theory of Computing, pages 121–130, 2013.
  * [JST11] Hossein Jowhari, Mert Saglam, and Gábor Tardos.  Tight bounds for $l_{p}$ samplers, finding duplicates in streams, and related problems.  In Proc. 30th ACM Symposium on Principles of Database Systems, pages 49–58, 2011.
  * [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 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 94–121. Springer, 2021.
  * [KNP+17] Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, and Mobin Yahyazadeh.  Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science, pages 475–486, 2017.
  * [MN22] Boaz Menuhin and Moni Naor.  Keep that card in mind: Card guessing with limited memory.  In Proc. 13th Conference on Innovations in Theoretical Computer Science, pages 107:1–107:28, 2022.
  * [Mut05] S. Muthukrishnan.  Data streams: Algorithms and applications.  Found. Trends Theor. Comput. Sci., 1(2):117–236, 2005.
  * [NY19] Moni Naor and Eylon Yogev.  Bloom filters in adversarial environments.  ACM Trans. Alg., 15(3):35:1–35:30, 2019.
  * [Tar07] Jun Tarui.  Finding a duplicate and a missing item in a stream.  In Proc. 4th International Conference on Theory and Applications of Models of Computation, pages 128–135, 2007.
  * [WZ22] David P. Woodruff and Samson Zhou.  Tight bounds for adversarially robust streams and sliding windows via difference estimators.  In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 1183–1196, 2022.

##  Appendix A Appendix

###### Proof.

In this proof of Lemma 3, we essentially repeat the proof of the Chernoff
bound, with slight modifications to account for the dependence of $X_{i}$ on
its predecessors. Here $t$ is a positive real number chosen later.

$\displaystyle\Pr$ $\displaystyle\left[\sum_{i=1}^{n}X_{i}\geq
np(1+\delta)\right]$ $\displaystyle=\Pr\left[e^{t\sum_{i=1}^{n}X_{i}}\geq
e^{tnp(1+\delta)}\right]$
$\displaystyle\leq\mathbb{E}[e^{t\sum_{i=1}^{n}X_{i}}]/e^{tnp(1+\delta)}$
$\displaystyle=e^{-tnp(1+\delta)}\mathbb{E}[e^{tX_{1}}\mathbb{E}[e^{tX_{2}}\cdots\mathbb{E}[e^{tX_{n}}\mid
X_{1}=X_{1},\ldots,X_{n-1}=X_{n-1}]\mid X_{1}=X_{1}]$ $\displaystyle\leq
e^{-tnp(1+\delta)}\mathbb{E}[e^{tX_{1}}\mathbb{E}[e^{tX_{2}}\cdots\mathbb{E}[e^{tX_{n-1}}(pe^{t}+(1-p))\mid
X_{1}=X_{1},\ldots,X_{n-2}=X_{n-2}]\mid X_{1}=X_{1}]$ $\displaystyle\leq
e^{-tnp(1+\delta)}\mathbb{E}[e^{tX_{1}}\mathbb{E}[e^{tX_{2}}\cdots\mathbb{E}[e^{tX_{n-2}}(pe^{t}+(1-p))^{2}\mid
X_{1}=X_{1},\ldots,X_{n-3}=X_{n-3}]\mid X_{1}=X_{1}]$ $\displaystyle\leq
e^{-tnp(1+\delta)}(pe^{t}+(1-p))^{n}=\left(\frac{pe^{t}+(1-p)}{e^{tp(1+\delta)}}\right)^{n}$
$\displaystyle\leq\left(\frac{e^{p(e^{t}-1)}}{e^{tp(1+\delta)}}\right)^{n}=\left(\frac{e^{e^{t}-1}}{e^{t(1+\delta)}}\right)^{np}\qquad\text{since
$1+x\leq e^{x}$}$
$\displaystyle=\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{np}\qquad\text{picking
$t=\ln(1+\delta)$}$
$\displaystyle\leq\exp\left(-\frac{\delta^{2}np}{2+\delta}\right)\,.\qquad\text{since
$x-(1+x)\ln(1+x)\leq-x^{2}/(2+x)$}$

∎