# The White-Box Adversarial Data Stream Model

Miklós Ajtai Hungarian Academy of Sciences. E-mail<EMAIL_ADDRESS>Vladimir Braverman Google Research. E-mail<EMAIL_ADDRESS>T.S. Jayram
Lawrence Livermore National Laboratories. E-mail<EMAIL_ADDRESS>Sandeep
Silwal MIT. E-mail<EMAIL_ADDRESS>Alec Sun Carnegie Mellon University.
E-mail<EMAIL_ADDRESS>David P. Woodruff Carnegie Mellon University.
E-mail<EMAIL_ADDRESS>Samson Zhou Carnegie Mellon University.
E-mail<EMAIL_ADDRESS>
###### Abstract

There has been a flurry of recent literature studying streaming algorithms for
which the input stream is chosen adaptively by a black-box adversary who
observes the output of the streaming algorithm at each time step. However,
these algorithms fail when the adversary has access to the internal state of
the algorithm, rather than just the output of the algorithm.

We study streaming algorithms in the _white-box adversarial model_ , where the
stream is chosen adaptively by an adversary who observes the entire internal
state of the algorithm at each time step. We show that nontrivial algorithms
are still possible. We first give a randomized algorithm for the $L_{1}$-heavy
hitters problem that outperforms the optimal deterministic Misra-Gries
algorithm on long streams. If the white-box adversary is computationally
bounded, we use cryptographic techniques to reduce the memory of our
$L_{1}$-heavy hitters algorithm even further and to design a number of
additional algorithms for graph, string, and linear algebra problems. The
existence of such algorithms is surprising, as the streaming algorithm does
not even have a secret key in this model, i.e., its state is entirely known to
the adversary. One algorithm we design is for estimating the number of
distinct elements in a stream with insertions and deletions achieving a
multiplicative approximation and sublinear space; such an algorithm is
impossible for deterministic algorithms.

We also give a general technique that translates any two-player deterministic
communication lower bound to a lower bound for randomized algorithms robust to
a white-box adversary. In particular, our results show that for all $p\geq 0$,
there exists a constant $C_{p}>1$ such that any $C_{p}$-approximation
algorithm for $F_{p}$ moment estimation in insertion-only streams with a
white-box adversary requires $\Omega(n)$ space for a universe of size $n$.
Similarly, there is a constant $C>1$ such that any $C$-approximation algorithm
in an insertion-only stream for matrix rank requires $\Omega(n)$ space with a
white-box adversary. These results do not contradict our upper bounds since
they assume the adversary has unbounded computational power. Our algorithmic
results based on cryptography thus show a separation between computationally
bounded and unbounded adversaries.

Finally, we prove a lower bound of $\Omega(\log n)$ bits for the fundamental
problem of deterministic approximate counting in a stream of 0’s and 1’s,
which holds even if we know how many total stream updates we have seen so far
at each point in the stream. Such a lower bound for approximate counting with
additional information was previously unknown, and in our context, it shows a
separation between multiplayer deterministic maximum communication and the
white-box space complexity of a streaming algorithm.

##  1 Introduction

In the streaming model of computation, one wants to compute or approximate a
predetermined function on a dataset. The dataset is implicitly defined through
a sequence of updates, and the goal is to use total space that is sublinear in
the size of the dataset. The streaming model captures key resource
requirements of algorithms for many database and network tasks where the size
of the data is significantly larger than the available storage, such as logs
for network traffic, IoT sensors, financial markets, commercial transactions,
and scientific data, e.g., astronomy or bioinformatics.

In the classical _oblivious_ streaming model, there exists a stream $S$ of
updates $u_{1},\ldots,u_{m}$ that defines an underlying dataset, such as a
frequency vector, a graph, or a set of points in Euclidean space. The sequence
of updates may be worst-case, but the dataset is fixed in advance and is
oblivious to any algorithmic design choices. Although there are examples of
fundamental streaming algorithms that are deterministic, many streaming
algorithms crucially utilize randomness to achieve meaningful guarantees in
sublinear space. For example, the famous AMS sketch [AMS99] for $F_{2}$
estimation initializes a random sign vector $Z$, maintains $\langle
Z,f\rangle$ in the stream, and outputs $\langle Z,f\rangle^{2}$ which is an
unbiased estimator to $\|f\|_{2}^{2}$, where $f$ is the underlying frequency
vector defined by the stream. However, the analysis demands that the
randomness used to generate the sign vector $Z$ is independent of the
frequency vector $f$ and in general, the analysis of many randomized
algorithms assumes that the randomness of the algorithm is independent of the
input. However, such an assumption may not be reasonable [MNS11, GHS+12,
BMSC17, NY19, AMYZ19, CN20]; even if the stream is not adversarially
generated, a user may need to repeatedly query and update a database based on
the responses to previous queries. For example in typical optimization
procedures such as stochastic gradient descent, each time step can update the
eventual output by an amount based on a previous query. In recommendation
systems, a user may choose to remove some suggestions based on personal
preference and then query for a new list of recommendations.

##### (Black-box) adversarial streaming model.

Recently, a large body of research has been devoted to studying the (black-
box) adversarial streaming model as a means of modeling adversarial data
streams. In the (black-box) adversarial streaming model [BY20, BJWY21, HKM+20,
WZ21, ABD+21, KMNS21, BHM+21, MN21, ACSS21, BEO22, CGS22], the sequence of
updates $u_{1},\ldots,u_{m}$ is chosen adaptively rather than being fixed. In
particular, the input is chosen by an adversary who repeatedly queries the
streaming algorithm for a fixed property of the underlying dataset at each
time $t\in[m]$ and determines the update $u_{t+1}$ only after seeing the
output of the algorithm after time $t$. The streaming algorithm must still be
correct at all times. In the black-box adversarial streaming model, [BY20,
ABD+21] show that Bernoulli sampling and reservoir sampling can approximately
preserve statistics such as densities of certain subsets of the universe and
[BHM+21] shows that importance sampling can use independent public randomness
to approximately solve problems such as $k$-means centering, linear
regression, and graph sparsification.

However, for other important problems such as $F_{p}$ moment estimation,
matrix rank, or estimating the number of distinct elements in the stream,
[BJWY21, HKM+20, WZ21, ACSS21, BEO22, CGS22] crucially use the fact that the
adversary who chooses the input can only see the output of the algorithm.
These algorithms essentially work by arguing that it is possible to have the
output of the algorithm change only a small number of times, and so only a
small amount of internal randomness is revealed, which allows such algorithms
to still be correct. However, these algorithms completely fail if the internal
state of the algorithm at each point in time is also revealed to an adversary.

##### White-box adversarial streaming model.

In this paper, we introduce the _white-box_ adversarial streaming model, where
the sequence of updates $u_{1},\ldots,u_{m}$ is chosen adaptively by an
adversary who sees the full internal state of the algorithm at all times,
including the parameters and the previous randomness used by the algorithm.
More formally, we define the white-box adversarial model as a two-player game
between ${\mathsf{StreamAlg}}$, the streaming algorithm, and
${\mathsf{Adversary}}$. Prior to the beginning of the game, a query
${\mathcal{Q}}$ is fixed, which asks for a fixed function of some underlying
dataset implicitly defined by the stream. The game then proceeds across $m$
rounds, where in the $t$-th round:

  1. (1)

${\mathsf{Adversary}}$ computes an update $u_{t}$ for the stream, which
depends on all previous stream updates, all previous internal states of
${\mathsf{StreamAlg}}$, and all previous randomness used by
${\mathsf{StreamAlg}}$ (and thus also, all previous outputs of
${\mathsf{StreamAlg}}$).

  2. (2)

${\mathsf{StreamAlg}}$ uses $u_{t}$ to update its data structures $D_{t}$,
acquires a fresh batch $R_{t}$ of random bits, and outputs a response $A_{t}$
to the query ${\mathcal{Q}}$.

  3. (3)

${\mathsf{Adversary}}$ observes the response $A_{t}$, the internal state
$D_{t}$ of ${\mathsf{StreamAlg}}$, and the random bits $R_{t}$.

The goal of ${\mathsf{Adversary}}$ is to make ${\mathsf{StreamAlg}}$ output an
incorrect response $A_{t}$ to the query ${\mathcal{Q}}$ at some time $t\in[m]$
throughout the stream. By nature of the game, only a single pass over the
stream is permitted.

##### Applications of white-box adversaries.

The white-box adversarial model captures the ability of an adversary to adapt
to internal processes of an algorithm, which the black-box adversarial model
is incapable of capturing. This property allows us to model richer adversarial
scenarios. For example in the area of dynamic algorithms, the goal is to
maintain a data structure that always outputs a correct answer at all times
$t\in[m]$ across updates $u_{1},\ldots,u_{m}$ that arrive sequentially, while
minimizing either the overall running time or the worst-case update time. In
some settings, the dynamic model also places a premium on space so that
algorithms must use space sublinear in the size of the input, but generally
this may not be required. The dynamic model often considers an adaptive
adversary [Cha10, Waj20, CH21, RSW22] that generates the updates
$u_{1},\ldots,u_{m}$ upon seeing the entire data structure maintained by the
algorithm after the previous update, i.e., a white-box adversary.

In general, the algorithm’s internal state can be used as part of a procedure
that will ultimately generate future inputs. For example, consider a
distributed streaming setting where a centralized server wants to collect
statistics on a database generated by a number of remote users. The
centralized server wants to minimize its space usage and therefore does not
want to store each update by the remote users. Moreover, the server may want
to limit communication over the network and thus it sends components of its
internal state $S$ (such as initialized random variables) to the remote users
in order to optimize the information sent from the remote users back to the
centralized server. The remote users may use $S$ in some process that
ultimately affects how the data downstream is generated. Thus in this case,
the future input data depends on (components) of the internal state $S$ of the
streaming algorithm of the central coordinator; this scenario is captured by
the white-box adversarial model. Furthermore, one of the remote users could be
malicious and would like to use the state $S$ to cause the central coordinator
to fail. In this case, the data is not only dependent on $S$ but also
adversarially generated; this scenario is also captured by the white-box
adversarial model. Finally, in the case that there is no central coordinator,
the entire internal state may be stored on a cloud, which would be visible to
all users.

The pan-private streaming model [DNP+10] lets the internal state of the
algorithm be partially or completely revealed. This model is often motivated
by distributed users such as hospitals, government agencies, or search engine
providers. [DNP+10] notes that any data curator “can be pressured to permit
data to be used for purposes other than that for which they are collected”,
including uses that may ultimately affect the distribution of future input
data to the curator. In fact, [MMNW11] specifically considers the problem of
counting distinct elements and detecting heavy-hitters on a data stream when
the internal state of the algorithm is revealed, giving the motivating example
of an insider manipulating traffic flow while trying to find flaws in a
systems administration database that tracks user visit statistics. It could be
argued that although the goal of [MMNW11] is just to preserve the privacy of
the users, they should also consider the white-box adversarial model where the
future inputs depend on previous information rather than their assumption that
the input is independent of the internal information.

In machine learning, robust algorithms and adversarial attacks have captured
the attention of recent research. In 2017, Google Brain organized a
competition at NeurIPS 2017 for producing effective adversarial attacks, in
which many of the most successful attacks used knowledge of the internal
algorithmic parameters and training weights to minimize some loss function in
a small neighborhood around the original input [BCM+13, SZS+14, GSS14]. More
recently, white-box attacks have generated adversarial inputs by modifying
existing data in such a minor way that is almost imperceptible to the human
eye, either in images [SZS+14, HPG+17] or in the physical world [KGB16,
SBBR16, AEIK18]. However, the modified data results in an incorrect
classification by a machine learning algorithm. As a result, a large body of
recent literature has focused on adversarial robustness of machine learning
models against white-box attacks, e.g., [IEM18, MMS+18, SST+18, TKP+18,
CZM+18, KGB17, LCLS17].

In persistent data structures, the goal is to provide version control to an
evolving data structure while minimizing either the space or time to view each
version, e.g., [DSST89, FK03, Kap04]. For example, the ability to quickly
access previous versions of information stored in an online repository shared
across multiple collaborators is an invaluable tool that many services already
provide. Moreover, the internal persistent data structures used to provide
version control may be accessible and thus visible to all users of the
repository. These users may then update the persistent data structure in a
manner that is not independent of the previous states.

###  1.1 Our Contributions

In this paper, we study the abilities and limitations of streaming algorithms
robust to white-box adversaries, which are significantly more powerful than
black-box adversaries. An insightful example of this is the work [HW13], which
develops a sophisticated attack for a black-box adversary to iteratively learn
the matrix used for a linear sketch in the black-box adversarial model. On the
other hand, the white-box adversary immediately sees the sketching matrix when
the algorithm is initiated. More generally, techniques such as differential
privacy, which are widely employed in black-box adversarial settings to hide
internal information, will not work against white-box adversaries.

The main contributions of this paper can be summarized as introducing general
tools to design algorithms robust to white-box adversaries as well as
presenting a framework for proving strong lower bounds in the white-box
adversarial model. In more detail, our contributions are the following:

  * •

White-box adversarial streaming model: We introduce and formalize the white-
box adversarial model for data streams as a means of modeling richer
adversarial settings found in a wide variety of application areas which are
not captured by the black-box adversarial model.

  * •

Robust algorithms and diverse applications: We provide streaming algorithms
robust against white-box adversaries for problems across many different
domains, e.g., statistical problems such as heavy-hitters, graph algorithms,
applications in numerical linear algebra, and string algorithms, with wide-
ranging applications. For example, estimating $F_{p}$ moments has applications
in databases, computer networks, data mining, and other contexts such as in
determining data skewness, which is important in parallel database
applications [DNSS92] or determining the output of self-joins in databases
[Goo89]. $L_{0}$ estimation is used by query optimizers to find the number of
unique values of some attribute without having to perform an expensive sort.
This statistic is further useful for selecting a minimum-cost query plan
[SAC+79], database design [Lig18], OLAP [PBM+03, SDNR96], data integration
[BHM+05, DJMS02], data warehousing [AGPR99], and packet tracing and database
auditing [CDIM03]. For more details, see Section 1.1.1.

  * •

Use of cryptography in robust algorithms: A key toolkit we widely employ to
design our robust algorithms comes from cryptography. Leveraging computational
assumptions commonly used for the design of cryptographic protocols allows us
to use powerful algorithmic tools such as collision resistant hash functions
and sketching matrices for which it is computationally hard to find a “short”
vector in their kernel. We believe our work opens up the possibility of using
cryptography much more broadly for streaming algorithms, beyond the white-box
adversarial setting.

  * •

A general lower bound framework: We give a general reduction from two-player
communication problems to space lower bounds in the white-box adversarial
model. Corollaries of our reduction include lower bounds for $F_{p}$ moment
estimation in data streams. For more details, see Section 3.1.

  * •

Lower bounds for deterministic counting: Lastly, we provide a space lower
bound for deterministic algorithms which count the number of ones in a binary
stream in the oblivious model, even if the algorithm has access to a timer
that reports how many total stream updates it has seen so far. This lower
bound serves two purposes. First, it shows that our general lower bound
framework of Section 3.1 does not extend to multiparty (greater than two)
communication protocols. Second, it provides strong lower bounds for the
fundamental problem of approximately counting in a stream, which has wide
applications (see Section 3.2).

####  1.1.1 Robust Algorithms

Any deterministic algorithm is naturally robust in the white-box adversarial
streaming model, but deterministic algorithms are often inefficient in a
stream. We first show that the $\varepsilon$-$L_{1}$-heavy hitters problem can
be solved using space strictly less than that of any deterministic algorithm
in the white-box adversarial streaming model. In this problem, the goal is to
output all indices $i$ such that $f_{i}>\varepsilon\,L_{1}$, where
$L_{1}=\|f\|_{1}$ is the $\ell_{1}$ norm of the underlying freqeuncy vector
defined by the stream.

######  Theorem 1.1.

There exists a white-box adversarially robust algorithm that reports all
$\varepsilon$-$L_{1}$-heavy hitters with probability at least $3/4$ and uses
space $\mathcal{O}\left(\frac{1}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}\right)+\log\log m\right)$.

By comparison, the well-known Misra-Gries data structure [MG82] is a
deterministic algorithm and thus robust against white-box adversaries, but
uses $\mathcal{O}\left(\frac{1}{\varepsilon}(\log m+\log n)\right)$ bits of
space. Our algorithm offers similar guarantees to Misra-Gries in the sense
that it returns a list of $\mathcal{O}\left(\frac{1}{\varepsilon}\right)$
items that contains all $\varepsilon$-$L_{1}$-heavy hitters as well as an
approximate frequency for each item in the list with additive error
$\varepsilon\,L_{1}$. Note that in the $\varepsilon$-$L_{1}$-heavy hitters
problem, the gap between the frequencies of items that appear in the list can
be as large as $\Omega(\varepsilon)\cdot L_{1}$. On the other hand, the
$(\varphi,\varepsilon)$-$L_{1}$-heavy hitter problem demands that we find all
$\varphi$-$L_{1}$-heavy hitters, but report no items whose frequency is below
$(\varphi-\varepsilon)\,L_{1}$, thereby parametrizing the threshold of the
“false positives” that are reported in the list. We give an algorithm with the
following guarantees for the $(\varphi,\varepsilon)$-$L_{1}$-heavy hitter
problem against white-box adversaries with total runtime $T$, i.e., $T$-time
bounded adversaries:

######  Theorem 1.2.

There exists an algorithm robust against white-box $T$-time bounded
adversaries that solves the $(\varphi,\varepsilon)$-$L_{1}$-heavy hitter
problem with probability at least $3/4$ and uses total space

$\mathcal{O}\left(\frac{1}{\varepsilon}\left(\log\log
n+\log\frac{1}{\varepsilon}\right)+\frac{1}{\varphi}\log n+\log\log m\right)$

for $T<\operatorname*{poly}\left(\log n,\frac{1}{\varepsilon}\right)$ and
total space

$\mathcal{O}\left(\frac{1}{\varepsilon}\min(\log n,\log
T)+\frac{1}{\varphi}\log n+\log\log m\right)$

for $T\geq\operatorname*{poly}\left(\log n,\frac{1}{\varepsilon}\right)$.

We remark that the proof of Theorem 1.2 uses collision-resistant hash
functions and hence only guarantees robustness against white-box adversaries
with polynomially bounded computation time. Theorem 1.2 is not information-
theoretically secure against white-box adversaries with unbounded computation
time.

We obtain qualitatively similar results to that of Theorem 1.1 for the
_Hierarchical Heavy Hitters_ problem, which generalizes $L_{1}$-heavy-hitters.
We also obtain similar results for the vertex neighborhood identification
problem, where the task is for an algorithm to identify all vertices of a
graph with identical neighborhoods, in the vertex arrival model, where each
update of the stream is a vertex of the graph along with a list of all of its
neighbors.

######  Theorem 1.3.

There exists an algorithm robust against white-box polynomial-time adversaries
that reports all vertices with identical neighborhoods with probability at
least $3/4$, using space $\mathcal{O}\left(n\log n\right)$.

We also prove a lower bound for deterministic algorithms for the vertex
neighborhood identification problem, even on oblivious data streams:

######  Theorem 1.4.

Any deterministic algorithm that reports all vertices with identical
neighborhoods uses space $\Omega\left(\frac{n^{2}}{\log n}\right)$.

Together, Theorem 1.3 and Theorem 1.4 show a strong separation between
deterministic algorithms and randomized algorithms robust against white-box
adversaries with polynomial runtime. We further utilize cryptographic tools to
obtain robust algorithms for other fundamental streaming problems. In
particular, assuming the hardness of the Short Integer Solution (SIS) problem
of lattice cryptography (see Definition 2.15 and Theorem 2.16), we can obtain
a sublinear space algorithm for the $L_{0}$ estimation problem on _turnstile
streams_ , where the stream updates are allowed to be positive and negative.

######  Theorem 1.5.

Let $c\in(0,1/2)$ and assume the adversary cannot solve the SIS problem of
Definition 2.15 with parameter $\beta_{\infty}=\operatorname*{poly}(n)$ in
Theorem 2.16 for sufficiently large $n$. Then Algorithm 5 returns a
$n^{\varepsilon}$ multiplicative approximation to the $L_{0}$ estimation
problem on turnstile streams. Furthermore, the algorithm uses space
$\tilde{\mathcal{O}}(n^{1-\varepsilon+c\varepsilon}+n^{(1+c)\varepsilon})$. In
the random oracle model, the algorithm uses space
$\tilde{\mathcal{O}}(n^{1-\varepsilon+c\varepsilon})$.

Note that the above result also guarantees robustness against a
computationally bounded adversary, formalized in Assumption 2.17. With no such
assumptions, we can provably show that approximating general $F_{p}$ moments
up to constant factors in data streams is impossible in sublinear space (see
Theorem 1.9 below). Using the same cryptographic assumption, we also obtain
streaming algorithms for the rank-decision problem in linear algebra.

######  Theorem 1.6.

Suppose $A$ is a $n\times n$ matrix. There exists a constant $0<c<1$ such that
the rank decision problem for $A$ can be solved in
$\tilde{\mathcal{O}}\left(nk^{2}\right)$ bits of space for any $k\leq n^{c}$
under the random oracle model assuming a computationally bounded adversary.

Corollaries of this result include streaming algorithms for other linear
algebra based applications such as computing a linearly independent basis.
Lastly, we also obtain white-box robust algorithms for string pattern matching
applications.

######  Theorem 1.7.

For an input string $P$ with given period $p$, followed by a string $U$, there
exists a streaming algorithm that, with probability at least
$1-\frac{1}{\operatorname*{poly}(n)}$, finds all instances of $P$ within $U$.
This streaming algorithm is robust against $T$-time white-box adversaries and
uses $\mathcal{O}\left(\log T\right)$ bits of space.

####  1.1.2 A General Reduction for Lower Bounds

A natural question is whether there exist robust streaming algorithms against
white-box adversaries for more complex problems, such as $F_{p}$ estimation or
matrix rank. To that end, we give a general technique to prove lower bounds
for randomized algorithms robust to white-box algorithms through two-player
deterministic communication problems.

######  Theorem 1.8.

(Informal) Suppose there exists a white-box adversarially robust streaming
algorithm using $S(n,\varepsilon)$ space that can be used to solve a one-way
two-player communication game with $S(n,\varepsilon)$ bits of communication
with probability $p\in(1/2,1]$. Then there exists a deterministic protocol for
the two-player communication game using $S(n,\varepsilon)$ bits of
communication.

###### Proof.

Over all choices of randomness, at least $p$ fraction of the possible random
strings chosen by the first player is correct over all possible inputs to the
second player and at least $p$ fraction of the possible random strings chosen
by the second player for each input. The first player can enumerate over all
possible inputs to the second player as well as all possible random strings to
select a state that uses $S(n,\varepsilon)$ space to represent and always
succeeds. The first player can then send the state of the algorithm to the
second player, who will then update the algorithm with their input and a fixed
string, thereby resulting in a deterministic protocol that solves the one-way
two-player communication game with $S(n,\varepsilon)$ bits of communication. ∎

We remark that Theorem 1.8 is especially powerful because it can be used to
prove lower bounds for randomized algorithms robust against white-box
adversaries using reductions from deterministic communication problems, which
can often have much higher communication complexity than their randomized
counterparts. For example, the deterministic complexity of the Equality
problem, in which Alice must send Bob a message to determine whether their
strings $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{n}$ are equal, is $\Theta(n)$.
However, the randomized complexity of the Equality problem is $\Theta(\log n)$
for a constant probability of success. Thus Theorem 1.8 can show significantly
stronger lower bounds for randomized algorithms robust against white-box
adversaries over the standard streaming model. In particular, we first obtain
the following hardness of approximation for $F_{p}$ moment estimation from
Theorem 1.8:

######  Theorem 1.9.

For each $p\geq 0$ and $p\neq 1$, there exists a constant $C_{p}>1$ such that
any white-box adversarially robust algorithm that reports a
$C_{p}$-approximation to the frequency moment $F_{p}$ of an underlying
frequency vector with probability at least $2/3$ must use space $\Omega(n)$.

We also obtain the following hardness of approximation for matrix rank
estimation from Theorem 1.8:

######  Theorem 1.10.

There exists a constant $C>1$ such that any white-box adversarially robust
algorithm that reports a $C$-approximation to the rank of an underlying matrix
with probability at least $2/3$ must use space $\Omega(n)$.

####  1.1.3 Lower Bound for Deterministic Counting

The “basic” problem of counting the number of ones in a binary stream, or
equivalently the number of stream updates, is arguably the most fundamental
streaming problem with both practical and theoretical applications. While
there exists a straightforward $\mathcal{O}\left(\log n\right)$ space
algorithm that explicitly maintains the actual count over the stream, there
exist randomized algorithms, notably the Morris counters, which achieve
$\mathcal{O}\left(\log\log n\right)$ bits. This savings is particularly
meaningful when considering applications such as counting the number of visits
to a popular website such as Wikipedia. In these applications, it is common to
maintain many counters rather than one, and thus optimizing the space usage
per counter has a measurable overall impact.

The basic counting problem is a key subroutine in many streaming problems in
the oblivious model, such as $F_{p}$ estimation in an insertion-only stream
[JW19], approximate reservoir sampling [GS09], approximating the number of
inversions in a permutation [AJKS02], and $L_{1}$-heavy hitters in insertion
streams [BDW19].

We show that any deterministic problem in the oblivious model for counting
must asymptotically use the same amount of space as the trivial algorithm,
even when the algorithm knows the identity of the current position in the
stream. That is, even if the streaming algorithm is augmented with a “timer”
which tells it at any time how many stream updates it has seen, the algorithm
still cannot approximate the number of 1’s in a binary stream up to a constant
factor unless it uses $\Omega(\log n)$ bits of memory. Note that having a
timer is what makes our lower bound nontrivial: without a timer, with $o(\log
n)$ bits of memory there are fewer than say, $n/10$ states of the algorithm,
so after seeing $n/10$ 1’s, the algorithm necessarily revisits a state it has
seen before. Since the algorithm is deterministic, it gets stuck in a cycle
and thus can produce at best a $10$-approximation. A timer will also be useful
for our application, described momentarily.

######  Theorem 1.11.

Given a constant $\varepsilon>0$, any deterministic algorithm that outputs a
$(1+\varepsilon)$-approximation to the number of ones in a length-$n$ stream
of bits must use $\Omega(\log n)$ bits of space, even if the algorithm has a
timer which tells it how many stream updates it has seen so far.

Surprisingly, Theorem 1.11 shows that our technique translating two-player
deterministic communication lower bounds to white-box adversary lower bounds
in Theorem 1.8 cannot extend to an arbitrary number $n$ of players. Recall
that Theorem 1.8 implies the white-box space complexity is at least the two-
player one-way deterministic communication of the underlying communication
problem, which is just the maximum communication of any player (since only one
player speaks). A natural question is whether the white-box space complexity
is at least the maximum communication of the underlying $n$-player
deterministic communication game. This is false, since in the white-box
adversarial model we can count using Morris counters with
$\mathcal{O}\left(\log\log n\right)$ bits. However, given Theorem 1.11, the
maximum communication of the underlying $n$-player deterministic communication
game is $\Omega(\log n)$ bits. Note that in a communication game, each player
knows its identity and can behave differently than other players, and thus the
assumption that the algorithm has a timer in Theorem 1.11 is needed.

###  1.2 Overview of our Techniques

#####  $L_{1}$-heavy hitters.

To find all $\varepsilon$-$L_{1}$-heavy hitters, we first recall that the
well-known Misra-Gries algorithm is deterministic and maintains approximate
frequencies to each of the possible heavy hitters using space
$\mathcal{O}\left(\frac{1}{\varepsilon}(\log m+\log n)\right)$, which is
expensive for $m\gg 2^{n}$. Thus if we can reduce the stream length from $m$
to some $m^{\prime}=\operatorname*{poly}\left(\frac{1}{\varepsilon},n\right)$,
then we can run Misra-Gries on the smaller stream. If the stream length $m$
were known, we can use Bernoulli sampling on each update in the stream with
probability roughly $\frac{\log n}{\varepsilon^{2}m}$ to preserve the
$\varepsilon$-$L_{1}$-heavy hitters; this sampling probability was shown to be
secure against a white-box adversary in [BY20]. Thus it remains to resolve the
issue of not knowing the stream length $m$ in advance.

A natural approach is to make a number of exponentially increasing guesses for
the length of the stream $m$. However, not only does this approach induce a
multiplicative overhead of $\mathcal{O}\left(\log n\right)$ in the number of
simultaneous instances, corresponding to each guess for the length, but also
even tracking the length $m$ of the stream exactly requires
$\mathcal{O}\left(\log m\right)$ bits, which we would like to avoid. We
instead observe that Morris counters are white-box adversarially robust and
use them to estimate the length of the stream at all times within a constant
factor with space $\mathcal{O}\left(\log\log m\right)$. Moreover, we
simultaneously only maintain two guesses for the length of the stream,
corresponding to increasing powers of $\left(\frac{16}{\varepsilon}\right)$,
since when an instance of the algorithm is initiated with a guess for $m$, at
most $\frac{\varepsilon}{16}\,m$ updates have been missed by the algorithm, so
any items $i$ that are $\varepsilon$-$L_{1}$-heavy hitters of the stream will
still be $\mathcal{O}\left(\varepsilon\right)$-$L_{1}$-heavy hitters of the
stream seen by the algorithm. Similar techniques also work for the
Hierarchical Heavy Hitters problem.

##### Computationally-bounded white-box adversaries.

We can further improve our guarantees if the white-box adversary has bounded
computational time through the use of collision-resistant hash functions.
Namely, we can solve the $(\varphi,\varepsilon)$-$L_{1}$-heavy hitters problem
by using a collision-resistant hash function to hash the sampled items into a
universe of size $\operatorname*{poly}\left(\log
n,\frac{1}{\varepsilon},T\right)$ for white-box adversaries with computation
time at most $T$. Similarly, we can achieve a streaming algorithm for the
vertex neighborhood identification problem that is robust against polynomial-
time white-box adversaries by hashing a Boolean vector representing the
neighborhood of each vector into a universe of size
$\operatorname*{poly}(n,T)$. Thus it suffices to maintain $n$ hashes
corresponding to the $n$ neighborhoods, using total space
$\mathcal{O}\left(n\log nT\right)$. By comparison, we can use the OR Equality
problem to show any deterministic algorithm that solves the vertex
neighborhood identification problem requires $\Omega\left(\frac{n^{2}}{\log
n}\right)$ space. We similarly use collision-resistant hash functions to
obtain robust algorithms for problems in linear algebra and strings.

##### Two-player communication lower bounds.

To acquire a tool for proving lower bounds for white-box adversarially robust
algorithms, we first note that a standard technique for proving lower bounds
in the oblivious streaming model is to consider the randomized communication
complexity of certain problems, such as Equality. However, the deterministic
communication complexity of many of these problems can be a lot higher.
Surprisingly, we show that randomized algorithms that are robust against
white-box adversaries can be used for deterministic protocols, thereby proving
significantly stronger lower bounds for white-box adversarially robust
algorithms than their counterparts in the oblivious streaming model. In
particular, if there exists a randomized algorithm that is robust against
white-box adversaries, then it can be used in a two-player communication game
as follows. The first player reads their input and creates the stream as
usual. Rather than generating internal randomness for the algorithm, the first
player notes that there exists a choice of the internal randomness such that
for any possible input to the second player, the algorithm succeeds on $9/10$
of the possible strings used for randomness by the second player. The first
player can then enumerate over all possible inputs and all possible strings
used for the randomness to the second player and choose the first internal
randomness for the first player such that the guarantee holds. The first
player can then run the algorithm on the created stream with this
deterministic choice of randomness and pass the state to the second player,
who can now run their input over all choices of randomness for the second part
of the stream, and take a majority vote. Note that this results in a
deterministic protocol and thus must respect any deterministic lower bound for
a communication problem. In particular, we can choose the communication
problem to be Gap Equality (which is just the Equality problem with the
promise that when the two input strings are not equal, they differ in a
constant fraction of positions) problem to show both Theorem 1.9 and Theorem
1.10. Unfortunately, we prove that this technique cannot be generalized to
show lower bounds for white-box adversarially robust algorithms through
multiplayer communication.

##### Lower bounds for deterministic counting with a timer.

A streaming algorithm is just a read-once branching program. Theorem 1.11 is
proven by bounding the number of counts that a single state of the branching
program can correctly represent, which translates to an upper bound on the
length of an interval on a worst-case stream that each state can correctly
represent. We then show that there exists some $t_{0}$ such that after $t_{0}$
updates in the stream, all read-once branching programs require at least
$\operatorname*{poly}(n)$ states to approximate the number of ones in a length
$n$ stream to within a constant factor. See Section 3.2 for a more detailed
description.

###  1.3 Notation

For an integer $n>0$, $[n]$ denotes the set of integers $\\{1,\ldots,n\\}$. We
use $\operatorname*{poly}(n)$ to denote a fixed constant degree polynomial in
$n$ and $\frac{1}{\operatorname*{poly}(n)}$ to denote an arbitrary degree
polynomial in $n$ that can be determined from setting constants appropriately.
For a vector $v\in\mathbb{R}^{n}$, we use $v_{k}$ with $k\in[n]$ to denote its
$k$-th coordinate. Given vectors $u,v\in\mathbb{R}^{n}$, we write their inner
product as $\langle u,v\rangle=\sum_{k=1}^{n}u_{k}v_{k}$. For a string $S$, we
use $S[i:j]$ to denote the substring formed from the $i$-th character of $S$
to the $j$-th character of $S$, inclusive. We use $S\circ T$ to denote the
concatenation of a string $S$ with a string $T$.

##  2 Upper Bounds

In this section, we present streaming algorithms relevant to statistics that
are robust to white-box adversaries.

We first describe a crucial data structure for our algorithms: the Morris
counter [Mor78]. This is a data structure for the approximate counting
problem, where a nonnegative integer $Z=\sum_{t=1}^{m}u_{t}$ is defined
through updates $u_{1},\ldots,u_{m}$ such that $u_{t}\in\\{0,1\\}$ for each
$t\in[m]$. Given an accuracy parameter $\varepsilon>0$, the goal of the
approximate counting problem is to estimate $Z$ to within a
$(1+\varepsilon)$-approximation. Our first result is that Morris counters are
robust in the white-box adversarial model.

######  Lemma 2.1.

Morris counters output a $(1+\varepsilon)$-approximation to the frequency of
an item $i$ in the white-box adversarial streaming model with probability at
least $1-\delta$, using total space

$\mathcal{O}\left(\log\log n+\log\frac{1}{\varepsilon}+\log\log
m+\log\frac{1}{\delta}\right).$

###  2.1 Heavy-Hitters

In this section, we present randomized algorithms for
$\varepsilon$-$L_{1}$-heavy hitters that provide better guarantees than the
well-known deterministic Misra-Gries data structure. In the $F_{p}$ moment
estimation and $L_{p}$ norm estimation problems, an underlying frequency
vector $f\in\mathbb{R}^{n}$ is defined through updates $u_{1},\ldots,u_{m}$
such that $u_{t}\in[n]$ for each $t\in[m]$. The resulting frequency vector $f$
is then defined so that $f_{k}=|\\{t\,|\,u_{t}=k\\}|$ for each $k\in[n]$. For
$p>0$, the $F_{p}$ moment of $f$ is defined to be
$F_{p}(f)=\sum_{i=1}^{n}(f_{k})^{p}$. The $L_{p}$ norm of $f$ is
$\|f\|_{p}=(F_{p}(f))^{1/p}$. We use both $F_{0}$ and $L_{0}$ to denote the
number of nonzero coordinates of $f$, i.e.,
$F_{0}(f)=\|f\|_{0}=|\\{k\,|\,f_{k}\neq 0\\}|$. Given a threshold parameter
$\varepsilon>0$, the goal of the $F_{p}$ moment estimation problem is to
provide a $(1+\varepsilon)$-approximation to $F_{p}(f)$ and the goal of the
$\varepsilon$-$L_{p}$-heavy hitters problem is to find all coordinates $k$
such that $f_{k}\geq\varepsilon\,L_{p}(f)$. In the
$(\varphi,\varepsilon)$-$L_{p}$-heavy hitter problem, the goal is to report
all coordinates $k$ such that $f_{k}\geq\varphi\,L_{p}(f)$ but also no
coordinate $j$ such that $f_{j}\leq(\varphi-\varepsilon)\,L_{p}(f)$.

######  Theorem 2.2.

[MG82] Given a threshold parameter $\varepsilon>0$, there exists a
deterministic one-pass streaming algorithm MisraGries that uses
$\mathcal{O}\left(\frac{1}{\varepsilon}(\log m+\log n)\right)$ bits of space
on a stream of length $m$ and outputs a list $L$ of size
$\frac{1}{\varepsilon}$ that includes all items $i$ such that
$f_{i}>\varepsilon m$. Moreover, the algorithm returns an estimate
$\widehat{f_{i}}$ for each $i\in L$ such that $f_{i}-\varepsilon
m\leq\widehat{f_{i}}\leq f_{i}$.

To output the identities of $\frac{1}{\varepsilon}$ heavy-hitters,
$\Omega\left(\frac{1}{\varepsilon}\log n\right)$ space is clearly necessary.
On the other hand, it is not clear that the dependence on $\log m$ for Misra-
Gries in Theorem 2.2 is needed. It is known that we can essentially preserve
the $\varepsilon$-$L_{1}$-heavy hitters by sampling a small number of updates
in a stream.

######  Theorem 2.3.

[BY20] There exists a constant $C>0$ such that for any
$\varepsilon,\delta\in(0,1/2)$, universe size $n$, and stream length $m$,
Bernoulli sampling each item of the stream with probability
$p\geq\frac{C\log(n/\delta)}{\varepsilon^{2}m}$ solves the heavy hitters
problem with error $\varepsilon$ in the white-box adversarial model.

We remark that Theorem 2.3 was proven in [BY20] against black-box adversaries,
but their proof extends naturally to white-box adversaries because there is no
additional private randomness maintained by the algorithm. On the other hand,
Theorem 2.3 requires that the length of the stream is known a priori, which is
an assumption that we would like to remove by running multiple instances of
the algorithm in parallel, with exponentially increasing guesses for the
length of the stream. However, even to track the length of the stream requires
$\mathcal{O}\left(\log m\right)$ bits of space. Instead, only an approximation
to the length of the stream is required and thus we use Morris counters to
remove the dependence on $\log m$. Finally, we observe that it suffices to
maintain only two active guesses for the length of the stream at any point in
time because even if we start a guess “late” in the stream, we will have only
missed a $\operatorname*{poly}(\varepsilon)$-prefix length of the stream, so
any $\varepsilon$-$L_{1}$-heavy hitters will still be
$\mathcal{O}\left(\varepsilon\right)$-heavy with respect to the substream.

A useful subroutine we will need appears in Algorithm 1, and our full
algorithm appears in Algorithm 2, which gives the full guarantees of Theorem
1.1. We can also generalize this approach to hierarchical heavy hitters.

Algorithm 1 ${\textsc{BernMG}}(n,m,\varepsilon,\delta)$

1:Universe size $n$, upper bound $m$ on the stream length, accuracy
$\varepsilon$, failure probability $\delta$, and a stream of updates
$u_{1},u_{2},\ldots$, where each $u_{i}\in[n]$ represents a single update to a
coordinate of the underlying vector $f$

2:$\varepsilon$-$L_{1}$-heavy hitters of the stream

3:Initialize an instance ${\mathcal{A}}$ of Misra-Gries with threshold
$\frac{\varepsilon}{2}$.

4:for each update $u_{t}$ with $t\in[m]$ do

5: With probability
$\mathcal{O}\left(\frac{\log(n/\delta)}{\varepsilon^{2}m}\right)$, update
${\mathcal{A}}$ with $u_{t}$

6:return the output of ${\mathcal{A}}$

Algorithm 2 Adversarially robust algorithm for $\varepsilon$-$L_{1}$-heavy
hitters

1:Universe size $n$, accuracy $\varepsilon$, and a stream of updates
$u_{1},u_{2},\ldots$, where each $u_{i}\in[n]$ represents a single update to a
coordinate of the underlying vector $f$

2:$\varepsilon$-$L_{1}$-heavy hitters of the stream

3:Run a Morris counter that outputs a
$(1+\mathcal{O}\left(\varepsilon\right))$-approximation $\widehat{t}$ to the
number of stream updates $t\in[m]$.

4:$c\leftarrow 0$, $r\leftarrow 2$,
$\delta\leftarrow\mathcal{O}\left(\frac{\varepsilon}{\log m}\right)$

5:for $i\in[r]$ do

6: Initialize an instance ${\mathcal{A}}_{i}$ of
${\textsc{BernMG}}(n,(16/\varepsilon)^{i},\varepsilon/2,\delta)$

7:for each update $u_{t}$ with $t\in[m]$ do

8: Update all instances of ${\mathcal{A}}_{i}$

9: if $\widehat{t}\geq(16/\varepsilon)^{c}$ then

10: Delete ${\mathcal{A}}_{c}$

11: $c\leftarrow c+1$

12: Initialize an instance ${\mathcal{A}}_{c}$ of

13:${\textsc{BernMG}}(n,(16/\varepsilon)^{c+1},\varepsilon/2,\delta)$

14: return the output of ${\mathcal{A}}_{c}$

Algorithm 2 also solves the $(\varphi,\varepsilon)$-$L_{1}$-heavy hitter
problem in which all items $i$ such that $f_{i}\geq\varphi\|f\|_{1}$ are
outputted and no items $j$ such that $f_{j}<(\varphi-\varepsilon)\|f\|_{1}$
are outputted, using a total space of
$\mathcal{O}\left(\frac{1}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}\right)+\log\log m\right)$ bits. [BDW19] showed
that for oblivious streams, the $\mathcal{O}\left(\frac{1}{\varepsilon}\log
n\right)$ dependence is not necessary. Similarly, we can further improve our
bounds against white-box adversaries that use $T=\operatorname*{poly}(\kappa)$
time through the following notion of collision-resistant hash functions:

######  Definition 2.4 (Family of Collision-Resistant Hash Functions).

A set of functions $H=\\{h_{i}:\\{0,1\\}^{n_{i}}\to\\{0,1\\}^{m_{i}}\\}_{i\in
I}$ is a family of collision-resistant hash functions (CRHF) if

  * •

(Efficient generation) There exists a probabilistic polynomial-time algorithm
${\mathsf{Gen}}$ such that ${\mathsf{Gen}}(1^{\kappa})\in I$ for all
$\kappa\in\mathbb{Z}^{+}$.

  * •

(Compression) $m_{i}<n_{i}$ for all $i\in I$.

  * •

(Efficient evaluation) There exists a probabilistic polynomial-time algorithm
${\mathsf{Eval}}$ such that for all $i\in I$ and $x\in\\{0,1\\}^{n}_{i}$, we
have ${\mathsf{Eval}}(x,i)=h_{i}(x)$.

  * •

(Collision-resistant) For any non-uniform probabilistic polynomial-time
algorithm ${\mathcal{A}}$, there exists a negligible function
${{\mathsf{negl}}}$ such that for all security parameters
$\kappa\in\mathbb{N}$,

$\underset{(x_{0},x_{1})\leftarrow{\mathcal{A}}(1^{\kappa},h)}{\mathbf{Pr}}\left[x_{0}\neq
x_{1}\wedge h(x_{0})=h(x_{1})\right]\leq{{\mathsf{negl}}}(\kappa).$

Here we use negligible function to mean a function ${{\mathsf{negl}}}$ such
that ${{\mathsf{negl}}}(x)=o\left(1/x^{c}\right)$ for any constant $c>0$.
There are folklore constructions of collision-resistant hash functions based
on the hardness of finding the discrete logarithm of a given composite number,
e.g., Theorem 7.73 in [KL14]:

######  Theorem 2.5.

Under the discrete log assumption, there exists a family of collision-
resistant hash functions with $m_{i}=\mathcal{O}\left(\log\kappa\right)$ for
$i={\mathsf{Gen}}(1^{\kappa})$ and uses $\mathcal{O}\left(\log\kappa\right)$
bits of storage.

Theorem 1.2 then follows from applying Theorem 2.5 to the sampled items.

We also remark that Algorithm 2 can be used to estimate the inner product of
two vectors $f$ and $g$ that are implicitly defined through two streams by
using the following observations:

######  Lemma 2.6.

[JW18] Let $f^{\prime},g^{\prime}\in\mathbb{R}^{n}$ be unscaled uniform
samples of $f$ and $g$, sampled with probability $p_{f}\geq\frac{s}{m_{f}}$
and $p_{g}\geq\frac{s}{m_{g}}$, where $s=\frac{1}{\varepsilon^{2}}$. Then with
probability at least $0.99$, we have

$\langle p^{-1}_{f}f^{\prime},p^{-1}_{g},g^{\prime}\rangle=\langle
f,g\rangle\pm\varepsilon\|f\|_{1}\|g\|_{1}.$

######  Lemma 2.7.

[NNW12] Given $f,g\in\mathbb{R}^{n}$, suppose $f^{\prime}$ and $g^{\prime}$
are vectors that satisfy

$\|f^{\prime}-f\|_{\infty}\leq\varepsilon\|f\|_{1},\qquad\|g^{\prime}-g\|_{\infty}\leq\varepsilon\|g\|_{1}.$

Then $\langle f^{\prime},g^{\prime}\rangle-\langle f,g\rangle|\leq
12\varepsilon\|f\|_{1}\|g\|_{1}$.

Combining Lemma 2.6 and Lemma 2.7, we have the following:

######  Corollary 2.8.

There exists a white-box adversarially robust algorithm that uses space

$\mathcal{O}\left(\frac{1}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}\right)+\log\log m\right)$

and outputs vectors $f^{\prime},g^{\prime}\in\mathbb{R}^{n}$ such that with
probability at least $3/4$,

$|\langle f^{\prime},g^{\prime}\rangle-\langle
f,g\rangle|\leq\varepsilon\|f\|_{1}\|g\|_{1}.$

###  2.2 Hierarchical Heavy Hitters

We now give adversarially robust algorithms for an important generalization of
the $L_{1}$-heavy hitters problem known as the hierarchical heavy hitters
(HHH) problem. We first define the notion of a hierarchical heavy hitter.

######  Definition 2.9 (Hierarchical Heavy Hitter [CKMS03]).

Let $D$ be hierarchical domain of height $h$ over $[n]$. Let elements$(T)$ be
the union of elements that are descendants of a set of prefixes $T$ of the
domain hierarchy. Given a threshold $\varepsilon$, we define the set of
Hierarchical Heavy Hitters inductively. $HHH_{0}$, the hierarchical heavy
hitters at level zero, are simply the $\varepsilon$-$L_{1}$ heavy hitters.
Given a prefix $p$ at level $i$ of the hierarchy, define $F(p)$ as $\sum
f(e):e\in elements(\\{p\\})\wedge e\not\in
elements(\cup_{\ell=0}^{i=1}HHH_{\ell})$. $HHH_{i}$ is the set of Hierarchical
Heavy Hitters at level $i$, that is, the set $\\{p|F(p)\geq\varepsilon m\\}$.
The set of of Hierarchical Heavy Hitters, HHH, is $\cup_{i=0}^{h}HHH_{i}$.

Hierarchical heavy hitters have numerous applications, ranging from real-time
anomaly detection [ZSS+04] to DDoS detection [SDS+06]. Therefore, they have
been extensively studied [CKMS03, ESV03, CKMS04, LL07, CKMS08, TG09, TMS12,
BEF+17, BEF+18, MR20].

The problem we are interested in is to find all hierarchical heavy hitters,
and their frequencies, in a data stream. However, the problem defined above
cannot be be solved exactly over data streams in general. Therefore, the
literature on HHHs on data streams focuses on the following approximate
version of the problem.

######  Definition 2.10 (HHH Problem).

Given a data stream from a hierarchical domain $D$, a threshold
$\gamma\in(0,1)$, and an error parameter $\varepsilon\in(0,\gamma)$, the
hierarchical Heavy Hitter Problem is that of identifying prefixes $p\in D$,
and estimates $f_{p}$ of their associated frequencies to satisfy the following
conditions.

  1. (1)

accuracy: $f_{p}^{*}-\varepsilon m\leq f_{p}\leq f_{p}^{*}$, where $f_{p}^{*}$
is the true frequency of $p$.

  2. (2)

coverage: All prefixes $q$ not identified as approximate HHHs have $\sum
f_{e}^{*}:e\in elements(\\{q\\})\wedge e\not\in elements(P)\leq\gamma m$, for
any supplied $\gamma\geq\varepsilon$, where $P$ is the subset of $p$’s which
are descendants of $q$.

The state of the art space bound on the HHH problem is
$\mathcal{O}\left(h/\varepsilon\right)$ words of space from [TMS12] where $h$
is the height of the domain $D$. Notably, their algorithm is _deterministic_
and hence robust against a white box adversary. In terms of bits, the total
space used by the algorithm of [TMS12] is
$\mathcal{O}\left(\frac{h}{\varepsilon}(\log m+\log n)\right)$.

######  Theorem 2.11.

Given threshold parameters $\varepsilon$ and $\gamma\geq\varepsilon$, there
exists a deterministic one-pass streaming algorithm that uses
$\mathcal{O}\left(\frac{h}{\varepsilon}(\log m+\log n)\right)$ space on a
stream of length $m$ and solves the HHH Problem according to Definition 2.10.

In this section, we present randomized and adversarially robust algorithms
which provide better guarantees than the deterministic algorithm of [TMS12].
We first note that the results of [BY20] imply the following result about
solving the HHH Problem.

######  Theorem 2.12.

[BY20] There exists a constant $C>0$ such that for any
$\varepsilon,\delta\in(0,1/2)$, universe $n$, and stream length $m$, Bernoulli
sampling each item of the stream with probability
$p\geq\frac{C\log(n/\delta)}{\varepsilon^{2}m}$ solves the HHH Problem in the
white-box adversarial model.

###### Proof.

The proof follows from letting the set of ranges $\mathcal{R}$ be equal to the
prefixes $p\in D$ in Theorem $1.2$ of [BY20]. The size of $\mathcal{R}$ is
$\mathcal{O}\left(n\right)$ since $D$ is a hierarchical domain (tree) over
$[n]$. ∎

We now present the analogous versions of Algorithm 1 and Algorithm 2 for the
HHH problem. The qualitative difference is that we can substitute calling
${\mathcal{A}}$ of Misra-Gries with the appropriate algorithm for HHH from
[TMS12].

Algorithm 3 ${\textsc{BernHHH}}(n,m,\varepsilon,\delta)$

1:Universe size $n$, upper bound $m$ on the stream length, parameters
$\varepsilon,\phi$, failure probability $\delta$, and a stream of updates
$u_{1},u_{2},\ldots$, where each $u_{i}\in[n]$ represents a single update to a
coordinate of the underlying vector $f$

2:HHHs of the stream according to Definition 2.10

3:Initialize an instance ${\mathcal{A}}$ of HHH algorithm from [TMS12] with
threshold $\frac{\varepsilon}{2}$.

4:for each update $u_{t}$ with $t\in[m]$ do

5: With probability
$\mathcal{O}\left(\frac{\log(n/\delta)}{\varepsilon^{2}m}\right)$, update
${\mathcal{A}}$ with $u_{t}$

6:return the output of ${\mathcal{A}}$

Algorithm 4 Adversarially robust algorithm for the hierarchical heavy hitters
problem

1:Universe size $n$, accuracy $\varepsilon$, and a stream of updates
$u_{1},u_{2},\ldots$, where each $u_{i}\in[n]$ represents a single update to a
coordinate of the underlying vector $f$

2:Solution to HHH Problem according to Definition 2.10

3:Run a Morris counter that outputs a
$(1+\mathcal{O}\left(\varepsilon\right))$-approximation $\widehat{t}$ to the
number of stream updates $t\in[m]$.

4:$c\leftarrow 0$, $r\leftarrow 2$,
$\delta\leftarrow\mathcal{O}\left(\frac{\varepsilon}{\log m}\right)$

5:for $i\in[r]$ do

6: Initialize an instance ${\mathcal{A}}_{i}$ of
${\textsc{BernHHH}}(n,(16/\varepsilon)^{i},\varepsilon/2,\delta)$

7:for each update $u_{t}$ with $t\in[m]$ do

8: Update all instances of ${\mathcal{A}}_{i}$

9: if $\widehat{t}\geq(16/\varepsilon)^{c}$ then

10: Delete ${\mathcal{A}}_{c}$

11: $c\leftarrow c+1$

12: Initialize an instance ${\mathcal{A}}_{c}$ of
${\textsc{BernHHH}}(n,(16/\varepsilon)^{c+1},\varepsilon/2,\delta)$

13: return the output of ${\mathcal{A}}_{c}$

######  Lemma 2.13.

With probability at least $1-\delta$, Algorithm 3 solves the HHH problem of
Definition 2.10.

###### Proof.

By the robustness of Bernoulli sampling on adversarial streams, i.e., Theorem
2.12, we have that with probability at least $1-\delta$, simultaneously for
all $p\in D$ with $f_{p}\geq\varepsilon m$, the number of instances of
elements in the stream belonging to $p$ sampled by the stream as input to the
instance ${\mathcal{A}}$ of the algorithm from [TMS12] is at least
$\frac{7\varepsilon}{8}\,m$. The proof follows by the correctness of Theorem
2.11 with threshold $\frac{\varepsilon}{2}$. ∎

######  Theorem 2.14.

There exists an algorithm robust against white-box adversaries that reports
all with probability at least $3/4$ and uses space
$\mathcal{O}\left(\frac{h}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}+\log\log\log m\right)+\log\log m\right)$.

###### Proof.

The proof of correctness follows similarly to the proof of Theorem 1.1 and
Lemma 2.13 by noting that any $p\in D$ with $f_{p}\geq\varepsilon m$ at a time
$t\in[t_{i},t_{i+1}]$ will also satisfy $f_{p}\geq 3\varepsilon/4$ at time
$t_{i}$.

We now analyze the space complexity of Algorithm 4. As stated in the proof of
Theorem 1.1, the Morris counter uses space $\mathcal{O}\left(\log\log
n+\log\frac{1}{\varepsilon}+\log\log m\right)$. Furthermore, each instance of
BernHHH uses space

$\mathcal{O}\left(\frac{h}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}+\log\log\log m\right)\right).$

Since there are at most $r=2$ such instances of BernHHH, the total space is

$\mathcal{O}\left(\frac{h}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}+\log\log\log m\right)\right).$

Combining with the space used by Morris counters gives us the total space
bound of

$\mathcal{O}\left(\frac{h}{\varepsilon}\left(\log
n+\log\frac{1}{\varepsilon}+\log\log\log m\right)+\log\log m\right).\qed$

###  2.3 $L_{0}$ Estimation

We now provide a streaming algorithm for the $L_{0}$ estimation problem, where
the goal is to estimate the number of nonzero coordinates at the end of the
stream. From the lower bound of Theorem 1.9, we cannot hope to estimate the
$L_{0}$ norm of $f$ arbitrarily well. Surprisingly, we can attain a
multiplicative approximation of $n^{\varepsilon}$ for arbitrarily small
$\varepsilon$ even in the turnstile setting if we assume a _computationally
bounded_ adversary, similar to assumptions made in cryptography. Our model of
a computationally bounded adversary will deal with the following Short Integer
Solution (SIS) problem from lattice based cryptography.

######  Definition 2.15 (Short Integer Solution (SIS) Problem).

Let $n,m,q$ be integers and let $\beta>0$. Given a uniformly random matrix
$A\in\mathbb{Z}^{n\times m}_{q}$, the SIS problem is to find a nonzero integer
vector $z\in\mathbb{Z}^{m}$ such that $Az=0\bmod q$ and $\|z\|_{2}\leq\beta$.

Starting from Ajtai’s work [Ajt96], it is known that the SIS problem enjoys an
average-case to worst-case hardness. That is, for some appropriate parameter
settings, solving the SIS problem is at least as hard as approximating several
fundamental lattice based cryptography problems in the worst case.

######  Theorem 2.16.

[MP13] Let $n$ and $m=\operatorname*{poly}(n)$ be integers, let
$\beta\geq\beta_{\infty}\geq 1$ be reals, let
$Z=\\{z\in\mathbb{Z}^{m}:\|z\|_{2}\leq\beta\text{ and
}\|z\|_{\infty}\leq\beta_{\infty}\\}$, and let $q\geq\beta\cdot n^{\delta}$
for some constant $\delta>0$. Then solving SIS on average with non-negligible
probability, and with parameters $n,m,q$ and solution set $Z\setminus\\{0\\}$,
is at least as hard as approximating lattice problems in the worst case on
$n$-dimensional lattices to within a factor of
$\gamma=\max\\{1,\beta\cdot\beta_{\infty}/q\\}\cdot\tilde{\mathcal{O}}\left(\beta\sqrt{n}\right)$.

In the cryptography literature, lattice-based cryptography schemes are
designed for any $\gamma$ smaller than $2^{o(n\log\log n/\log n)}$ and the
best approximation currently known is for
$\gamma=2^{\mathcal{O}\left(n\log\log n/\log n\right)}$ via the LLL algorithm
[Vai15]. Improving the approximation factor to any asymptotically smaller
$\gamma$ would be a major breakthrough in cryptography. Therefore, our
computational assumption is the following, which implies breaking any of our
algorithms would require a major cryptographic breakthrough:

######  Assumption 2.17.

No polynomial-time adversary can approximate worst-case $n$-dimensional
lattice problems within a $\gamma=2^{o(n(\log\log n)/\log n)}$ factor.

In the $L_{0}$ streaming algorithm, we will only rely on hardness for much
smaller values of $\gamma$. Our algorithm for the $L_{0}$ estimation problem
in data streams is the following. It first considers a partition of $[n]$ into
$n^{1-\varepsilon}$ consecutive chunks each of $n^{\varepsilon}$ coordinates.
It then keeps track of $n^{1-\varepsilon}$ vectors, one for each chunk, by
multiplying the corresponding update with a sketching matrix derived from the
SIS problem. Our final estimate is the number of our $n^{1-\varepsilon}$
sketches which are nonzero when the stream ends. Note that we use the same
sketching matrix $A$ on each chunk, as described below.

Algorithm 5 ${\textsc{Estimate-L0}}(n,m,\varepsilon)$

1:Universe size $n$, accuracy $\varepsilon$, and a stream of updates
$u_{1},u_{2},\ldots$, where each $u_{i}\in[n]$ represents a single update to a
coordinate of the underlying vector $f$, and each $u_{i}$ is an integer

2:$n^{\varepsilon}$-multiplicative estimation of $L_{0}$ of $f$

3:Consider $A\in\mathbb{Z}^{n^{c\varepsilon}\times n^{\varepsilon}}_{q}$ is a
uniformly random matrix for $q=\operatorname*{poly}(n)$ and any $1/2>c>0$

4:Keep track of $n^{1-\varepsilon}$ vectors of length $n^{c\varepsilon}$,
initially all $0$ and each associated with a specific consecutive chunk of
$n^{\varepsilon}$ coordinates of $[n]$

5:for each update $u_{t}$ with $t\in[m]$ do

6: Update the sketch vector associated with the $i$-th chunk by adding
$u_{t}\cdot A_{k}$ to it, where $A_{k}$ is the $k$-th column of $A$, and where
the stream update changes the $k$-th coordinate of the $i$-th chunk by an
additive amount $u_{t}\in\mathbb{Z}$

7:return the number of vectors that are nonzero

We now claim that if the final frequency vector $f$ satisfies
$\|f\|_{\infty}\leq\operatorname*{poly}(n)$, then we can achieve an
$n^{\varepsilon}$ multiplicative approximation for the $L_{0}$ estimation
problem. Furthermore, we can achieve improved sublinear space if we are
working in the random oracle model of cryptography, which was introduced in
the pioneering work of Bellare and Rogaway [BR93]. In the random oracle model,
we assume a publicly accessible random function which can be accessed to us
_and_ the adversary. Each query gives a uniform random value from some output
domain and repeated queries give consistent answers. The random oracle model
is a well-studied model and has been used to design numerous cryptosystems
[BR93, BR96, CGH04, KM15]. In practice, one can use SHA256 as the random
oracle.

See 1.5

We remark that we only require $\gamma=\operatorname*{poly}(n)$ for the
application of Theorem 2.16 to Theorem 1.5. Furthermore, the algorithm also
works for turnstile streams where the stream updates are allowed to be
positive and negative. This is because we only require the final frequency
vector $f$ to satisfy $\|f\|_{\infty}\leq\operatorname*{poly}(n)$ in Theorem
2.16; the signs of the entries in $f$ do not matter.

###### Proof.

By Theorem 2.16 and Assumption 2.17, we know that the adversary cannot find
any nonzero vector $x$ such that $Ax=0$ and
$\|x\|_{\infty}\leq\operatorname*{poly}(n)$. Thus if the vectors we track
using $A$ equal $0$, we know that none of the coordinates in that chunk have a
positive $f_{i}$ value at the end. Similarly if the vector is nonzero, we know
that there is at least one (and at most $n^{\varepsilon}$) coordinates
associated with that chunk that have nonzero frequency value at the end. Thus
on each chunk of coordinates, we make multiplicative error at most
$n^{\varepsilon}$ and the theorem follows.

For the space bound, note that we can generate the appropriate column of $A$
on the fly via access to the random oracle (or we can store $A$ explicitly if
we do not use the random oracle model). Thus the only space used is to keep
track of the $n^{1-\varepsilon}$ vectors of size $n^{c\varepsilon}$, each
associated with an $n^{\varepsilon}$ chunk of coordinates of $[n]$. ∎

We remark that Algorithm 5 works for turnstile streams where the stream
updates are allowed to be positive and negative because we only require the
final frequency vector $f$ to satisfy
$\|f\|_{\infty}\leq\operatorname*{poly}(n)$ in Theorem 2.16 and the sign of
the entries in $f$ does not matter.

###  2.4 Graph Algorithms

In this section, we consider graph algorithms in the white-box adversarial
streaming model. We first consider the vertex neighborhood identification
problem, where an underlying graph $G=(V,E)$ is defined through a sequence of
updates $u_{1},\ldots,u_{n}$. In the vertex arrival model, we have $|V|=n$ and
each update $u_{i}$ corresponds to a vertex $v_{i}\in V$ as well as all
vertices in $V$ incident to $v_{i}$. We say vertices $u,v\in V$ are incident
if there exists an edge $(u,v)\in E$. We define the neighborhood of $v$ by the
set of all vertices that are incident to $v$, i.e.,
$\mathcal{N}(v)=\\{u\,|\,(u,v)\in E\\}$. The goal of the vertex neighborhood
identification problem is to identify vertices $u,v\in V$ such that
$\mathcal{N}(u)=\mathcal{N}(v)$.

See 1.3

###### Proof.

Since there are $n$ vertices, there can only be $n$ different neighborhoods.
Note that each neighborhood can be represented as a binary vector of length
$n$ where the $i$-th coordinate is $1$ if the $i$-th vertex is a neighbor and
$0$ otherwise. We can thus use a collision-resistant hash function that maps
each a vector into a universe of size $\operatorname*{poly}(n)$ and with
probability at least $3/4$, each distinct vertex neighborhood will be hashed
to a different value. Hence it suffices to store the hash of the vertex
neighborhood of each vertex and compare the hash values to see whether two
vertices have the same neighborhood. Since there are $n$ vertices and each
hash value uses space $\mathcal{O}\left(\log n\right)$, then the total space
is $\mathcal{O}\left(n\log n\right)$ bits of space. ∎

We remark that Theorem 1.3 is tight, given the following one-way randomized
communication complexity:

######  Theorem 2.18 (Theorem E.1 in [MWY15]).

Suppose Alice is given strings $a_{1},\ldots,a_{n}\in\\{0,1\\}^{k}$ and Bob is
given strings $b_{1},\ldots b_{n}\in\\{0,1\\}^{k}$ along with an index
$i\in[n]$. Then Alice must send $\Omega(n\log k)$ bits of communication for
Bob to determine whether $a_{i}=b_{i}$ with probability at least $3/4$.

######  Corollary 2.19.

Any randomized algorithm that with probability at least $3/4$, simultaneously
reports all vertices with identical neighborhoods must use $\Omega(n\log n)$
bits of space.

On the other hand, if the algorithm is required to be deterministic, we can
show a stronger lower bound through the following formulation of the OR
Equality problem:

######  Definition 2.20.

In the OR Equality problem, ${\textsc{OrEq}}_{n,k}$, Alice has strings
$x_{1},\ldots,x_{k}\in\\{0,1\\}^{n}$ and Bob has strings
$y_{1},\ldots,y_{k}\in\\{0,1\\}^{n}$. Their goal is to determine the $k$-bit
string $(z_{1},\ldots,z_{k})$ where each $z_{i}=1$ if $x_{i}=y_{i}$ and
$z_{i}=0$ otherwise, for each $i\in[k]$.

######  Theorem 2.21.

[KW09] For $k\leq\frac{n}{\log n}$, the deterministic communication complexity
of ${\textsc{OrEq}}_{n,k}$ is $\Omega(nk)$, even if $x_{i}=y_{i}$ for at most
a single index $i\in[k]$.

We now show that any deterministic algorithm that reports all vertices with
identical neighborhoods uses space $\Omega\left(\frac{n^{2}}{\log n}\right)$.
By comparison, Theorem 1.3 uses space $\mathcal{O}\left(n\log n\right)$, thus
showing a separation between deterministic algorithms and randomized
algorithms against polynomially-bounded white-box adversaries.

See 1.4

###### Proof.

Given an instance of ${\textsc{OrEq}}_{n,k}$ with $k=\frac{n}{\log n}$,
consider a graph $G$ with $3n$ vertices
$u_{1},\ldots,u_{n},v_{1},\ldots,v_{n},r_{1},\ldots,r_{n}$. For $i\in[k]$ and
$j\in[n]$, we connect $u_{i}$ to $r_{j}$ if and only if the $j$-th coordinate
of $x_{i}$ is $1$. Similarly, for $i\in[k]$ and $j\in[n]$, we connect $v_{i}$
to $r_{j}$ if and only if the $j$-th coordinate of $y_{i}$ is $1$. Thus two
vertices $u_{i}$ and $v_{i}$ have the same neighborhood if and only if
$x_{i}=y_{i}$. Hence any deterministic algorithm that reports all vertices
with identical neighborhoods also solves ${\textsc{OrEq}}_{n,k}$. By Theorem
2.21 for $k=\frac{n}{\log n}$, any deterministic algorithm robust against
white-box adversaries that reports all vertices with identical neighborhoods
uses space $\Omega\left(\frac{n^{2}}{\log n}\right)$. ∎

###  2.5 Linear Algebra Algorithms

In this section, we provide algorithms robust to white-box adversaries for
problems in linear algebra. The first problem we focus on will be the Rank
Decision Problem defined as follows.

######  Problem 2.22 (Rank Decision Problem).

Given an integer $k$, and a matrix $A$, determine whether the rank of $A$ is
at least $k$.

We can also use the cryptographic hardness of the SIS problem to solve the
rank decision problem in data streams under the random oracle model. We assume
the stream is composed of integer updates to the rows of a matrix $A$ and the
updates are bounded by $\operatorname*{poly}(n)$. In the following text, we
denote $\operatorname*{poly}(n)$ to be any function bounded by $n^{C}$ for
some constant $C$ which may change from line to line. However, this is not
crucial if we assume $n$ is sufficiently large.

See 1.6

###### Proof.

The algorithm chooses a matrix $H\in\mathbb{Z}_{q}^{k\times n}$ chosen from
the same distribution as in the SIS problem of Definition 2.15. We pick the
$q$ parameter in Theorem 2.16 to be $q\geq n^{k\log n}$. The algorithm always
maintains $HA$, which is a $k\times n$ matrix. After the stream ends, it
enumerates over all non-zero integer vectors $x$ with entries bounded by
absolute value at most $n^{k}$ and checks if $HAx\equiv 0\bmod q$. If such an
$x$ is found, it outputs the rank is less than $k$ and otherwise says the rank
is at least $k$.

We first analyze the space. Note that the entries of $H$ can be generated on
the fly to compute the sketch $HA$ using the random oracle. Assuming the
entries of $A$ are bounded by $\operatorname*{poly}(n)$, the overall space
required is $\tilde{\mathcal{O}}\left(nk^{2}\right)$ since $q$ requires
$\tilde{\mathcal{O}}\left(k\right)$ bits to specify.

We now prove the correctness. If $A$ has rank less than $k$, then there exists
a $k\times k$ submatrix of $A$ which has rank less than $k$. Therefore, there
exists a non-zero $x$ such that $Ax=0$ and that the entries of $x$ can be
taken to be integers bounded by $\operatorname*{poly}(n)^{k}$ (we can see this
in a variety of ways. For example, any $k\times k$ matrix with entries bounded
by $\operatorname*{poly}(n)$ has determinant at most
$\operatorname*{poly}(n)^{k}$ or by considering the row echelon form of the
matrix). Since $q>\operatorname*{poly}(n)^{k}$, we know that $x$ is not
$0\bmod q$ and thus we will find a $x$ such that $HAx\equiv 0\bmod q$.

Otherwise, $A$ has rank at least $k$. In this case, if we find an $x$ with
$HAx\equiv 0\bmod q$, then the adversary has found a $y=Ax$ with entries
bounded by $\operatorname*{poly}(n)^{k}$ such that $Hy=0$ and $y$ is not
$0\bmod q$. This contradicts the assumption that the adversary is
computationally bounded. Note that $y$ can have entries up to
$\operatorname*{poly}(n)^{k}$ so we can set $k$ as large as $n^{c}$ for a
sufficiently small $c$ to satisfy our computational hardness requirements.
Altogether, we output the correct answer in both cases. ∎

######  Remark 2.23.

Our algorithm also works in the _turnstile_ setting where an adversary can
make positive or negative updates to the rows of $A$.

###  2.6 String Algorithms

In this section, we consider string algorithms in the white-box adversarial
streaming model. For oblivious streams, algorithms often utilize Karp-Rabin
fingerprints, which is a form of polynomial identity testing that determines
whether two strings $U$ and $V$ are equal. Given a string $U\in\\{0,1\\}^{n}$,
the Karp-Rabin fingerprint of $U$ is $\sum_{i=1}^{n}U[i]\cdot x^{i}\bmod{p}$
for some sufficiently random large prime $p$ and a generator $x$. The Karp-
Rabin fingerprint utilizes the Schwart-Zippel lemma to show that with high
probability, the fingerprints of $U$ and $V$ are identical if $U=V$ and the
fingerprints are different if $U\neq V$.

Unfortunately, the Karp-Rabin fingerprint is not robust to white-box
adversaries because Fermat’s little theorem shows that a string with $U[i]=1$
and $U[j]=0$ for all $j\neq i$ has the same Karp-Rabin fingerprint as a string
$V\in\\{0,1\\}^{n}$ with $V[i+p-1]=1$ and $V[j=0]$ for all $j\neq i+p-1$,
given the same choice of $p$ and $x$. In other words, an adversary can use the
information about the internal parameters of the Karp-Rabin fingerprint to
easily generate a collision.

For the white-box adversarial model, we can instead use collision-resistant
hash functions to hash strings $U$ and $V$ and compare their hashes for
equality. However, we require the property that the hash value of a string $U$
can be computed as the characters of $U$ arrive sequentially. Fortunately, the
hash function in Theorem 2.5 randomly selects a large prime $p$ with
$\mathcal{O}\left(\log\kappa\right)$ bits and then randomly chooses a
generator $g$ of $p$. Then the hash function maps $h(U)=g^{U}\bmod{p}$, which
can be computed as characters of $U$ arrive sequentially. Thus, we set $h(U)$
to be the fingerprint of $U$.

######  Lemma 2.24.

There exists a streaming algorithm that, with probability at least
$1-\frac{1}{\operatorname*{poly}(n)}$, determines whether (possibly adaptive)
input strings $U$ and $V$ of length $n$ are equal and is robust against
$T$-time white-box adversaries using $\mathcal{O}\left(\log\min(T,n)\right)$
bits of space.

Similar to the techniques in [PP09, CFP+16, CKP19], we can use Lemma 2.24 as a
subroutine in the pattern matching problem, where the goal is to find all
instances of a pattern $P$ in a text $U$. For simplicity, we consider the case
where the period $p$ of the pattern $P$ is also given as part of the input.
The period $p$ of a string $S$ of length $n$ is the smallest integer $\pi$
such that $S[1:n-\pi]=S[\pi+1:n]$, e.g., see [PP09, EJS10, EGSZ17, EGSZ20], as
well as the more common notion that every $p$ characters of the string are the
same. We use the following structural property about strings:

######  Lemma 2.25.

[PP09] If a pattern $P$ with period $p$ matches the text $U$ at a position
$i$, there cannot be a match between positions $i$ and $i+p$.

Thus we can use the crucial fact that for our collision-resistant hash
functions, the fingerprint of a string $U\circ V$ can be computed from the
hashes of $U$ and $V$ and the length of $V$, to perform pattern matching in a
stream.

Algorithm 6 Pattern matching in a stream

1:Pattern $P$ and its period $p$ of length $n$, text $U$ of length
$\operatorname*{poly}(n)$, runtime $T$ of white-box adversary

2:All positions of $P$ in $U$

3:Choose a collision-resistant hash function $h$ against adversaries with
runtime $\max(T,\operatorname*{poly}(n))$.

4:Compute the fingerprints $\psi\leftarrow h(P[1:p])$, $\phi\leftarrow h(P)$.

5:$m\leftarrow\emptyset$

6:for each index $i$ such that $h(T[i+1:i+p])=\psi$ do

7: if $m\not\equiv i\pmod{p}$ then

8: $m\leftarrow i$

9: if $h(T[m+1:m+n])=\phi$ then

10: Output $m$

11: $m\leftarrow m+p$

######  Lemma 2.26.

For an input string $P$ with given period $p$, followed by a string $T$, there
exists a streaming algorithm that, with probability at least
$1-\frac{1}{\operatorname*{poly}(n)}$, finds all instances of $P$ within $T$
that is robust against $T$-time white-box adversaries and uses
$\mathcal{O}\left(\log T\right)$ bits of space.

###### Proof.

Consider Algorithm 6. Lemma 2.25 implies that if $U[i+1:i+p]$ matches $P[1:p]$
for any index $i$, then either $U[i+1:i+2p]$ matches $P[1:2p]$ or there is at
most one index $j\in[i+p+1,i+2p]$ that matches $P[1:p]$. In other words, any
sequence of matches for the first $p$ characters of $P$ must either be exactly
$p$ characters apart or be more than $p$ characters apart thus eliminating the
possibility of previous positions that have not already been verified as
periods. Hence for any index $i$ of $U$ at which an instance of $P$ begins,
either $i\equiv m\pmod{p}$ or $i$ will be a certificate that all positions
$j=m+kp$ with integer $k\geq 0$ and $j<i$ do not match the pattern $P$. In the
former case, $i-p$ must also be an instance of the pattern, so $m$ will be
increased by $p$ to $i$ after verifying the position $i-p$. In the latter
case, all future matches of $P[1,p]$ within the next $n$ characters of $i$
must occur at multiples of $p$ away from $i$ by Lemma 2.25. Thus in either
case, Algorithm 6 will report $i$. ∎

##  3 Lower Bound Techniques

In this section, we present techniques to showing lower bounds in the white-
box adversarial streaming model. Surprisingly, our reductions can utilize
deterministic communication complexity protocols, even to show lower bounds
for randomized algorithms. We apply our techniques to show lower bounds for
$F_{p}$ estimation for all $p\geq 0$, including estimating the number of
distinct elements for $p=0$, as well as matrix rank estimation.

###  3.1 Lower Bounds for $F_{p}$ Estimation

We illustrate Theorem 1.8 with a lower bound for $F_{p}$ moment estimation
through a reduction from the following formulation of the Gap Equality
problem:

######  Definition 3.1 (Gap Equality).

In the deterministic Gap Equality problem ${\textsc{DetGapEQ}}_{n}$, Alice
receives a string $x\in\\{0,1\\}^{n}$ with $|x|=\frac{n}{2}$ and Bob receives
a string $y\in\\{0,1\\}^{n}$ with $|y|=\frac{n}{2}$. Their goal is to use a
deterministic protocol to determine whether $x=y$, given the promise that
either $x=y$ or the Hamming distance ${\mathsf{HAM}}(x,y)$ satisfies
${\mathsf{HAM}}(x,y)\geq\frac{n}{10}$.

######  Theorem 3.2.

([BCW98]) The deterministic communication complexity of
${\textsc{DetGapEQ}}_{n}$ is $\Omega(n)$.

We use the Gap Equality problem to show lower bounds for $F_{p}$ moment
estimation in the white-box adversarial streaming model; Theorem 1.10 follows
from a similar reduction.

######  Theorem 3.3.

For any $p\geq 0$ with $p\neq 1$, there exists a constant $C_{p}>1$ such that
any white-box adversarially robust algorithm that outputs an
$C_{p}$-approximation to $F_{p}$ with probability at least $9/10$ requires
$\Omega(n)$ space.

We remark that a stronger version of Theorem 3.3 can be proved, in which the
streaming algorithm can hide bits from the adversary.

###### Proof.

First note that given vectors $u,v\in\\{0,1\\}^{n}$ with $|u|=|v|=\frac{n}{2}$
and ${\mathsf{HAM}}(u,v)\geq\frac{n}{10}$, there exists a constant $C_{p}$
such that $C_{p}\|2u\|_{p}\leq\|u+v\|_{p}$ for $p\in[0,1)$ and
$C_{p}\|u+v\|_{p}\leq\|2u\|_{p}$ for $p>1$. Assume for the sake of
contradiction that there exists an algorithm ${\mathcal{A}}$ that uses
$o\left(\frac{n}{2^{k}}\right)$ space and $k$ hidden private bits and outputs
a $C_{p}$-approximation to $F_{p}$ with probability at least $9/10$ in the
white-box adversarial model. Given an instance of ${\textsc{DetGapEQ}}_{n}$,
Alice receives a string $x\in\\{0,1\\}^{n}$ with $|x|=\frac{n}{2}$ and Bob
receives a string $y\in\\{0,1\\}^{n}$ with $|y|=\frac{n}{2}$. Alice creates a
stream $S$ that induces the frequency vector $x$.

Because Alice and Bob must solve ${\textsc{DetGapEQ}}_{n}$ deterministically,
$k$ random bits cannot be selected. Instead, Alice runs a separate instance of
${\mathcal{A}}$ on $S$ for each of the $2^{k}$ possible realizations of the
$k$ random bits. For the $i$-th realization of the sequence of the hidden
random bits under some fixed ordering, Alice deterministically chooses a
sequence $R_{i}$ of public random bits such that ${\mathcal{A}}$ is correct
for at least $9/10$ fraction of the possible values of $y$. Otherwise, if such
a sequence does not exist, Alice sets the sequence $R_{i}$ to be the all zeros
sequence. For each $i\in[2^{k}]$, Alice then runs the algorithm
${\mathcal{A}}$ on the $i$-th realization of the sequence of the hidden random
bits under some fixed ordering, the deterministic fixing of the sequence
$R_{i}$ to use as ${\mathcal{A}}$’s public “random bits”, and the input $x$ to
create a state $\sigma_{i}(x)$. Alice then sends the set of states
$\sigma_{1}(x),\ldots,\sigma_{2^{k}}(x)$ to Bob.

Bob creates a stream that induces the frequency vector $y$. For each
$i\in[2^{k}]$, Bob takes $\sigma_{i}(x)$, continues running ${\mathcal{A}}$ on
the created stream, so that the underlying frequency vector is $x+y$, and
queries the algorithm. Since a $C_{p}$-approximation to the norm of $x+y$
distinguishes whether $x=y$ or ${\mathsf{HAM}}(x,y)\geq\frac{n}{10}$ by the
above argument, then for each $i\in[2^{k}]$, Bob can determine whether the
$i$-th instance of ${\mathcal{A}}$ outputs whether $x=y$ or
${\mathsf{HAM}}(x,y)\geq\frac{n}{10}$ by enumerating over all possible
“random” strings and taking the majority output by the algorithm. By the
correctness of ${\mathcal{A}}$ in the white-box adversarial model, for at
least $9/10$ of the possible realizations of the sequence of the hidden random
bits under some fixed ordering will also be correct for _all possible values_
of $y$, across at least $9/10$ of the possible public random bits used by the
algorithm. Thus at least $9/10$ fraction of the states $\sigma_{i}(x)$ sent by
Alice, where $i\in[2^{k}]$, will succeed for all possible values of $y$.
Hence, at least $9/10$ fraction of the $2^{k}$ outputs by Bob will be correct,
allowing Bob to distinguish whether $x=y$ or
${\mathsf{HAM}}(x,y)\geq\frac{n}{10}$.

From our assumption, each instance of ${\mathcal{A}}$ uses
$o\left(\frac{n}{2^{k}}\right)$ space. Thus the states $\sigma_{i}(x)$ sent by
Alice, where $i\in[2^{k}]$, use at most $o(n)$ communication, which
contradicts Theorem 3.2. It follows that ${\mathcal{A}}$ uses
$\Omega\left(\frac{n}{2^{k}}\right)$ space. ∎

###  3.2 Lower Bound for Deterministic Approximate Counting

A natural question is whether the techniques of Theorem 1.8 extend to
multiplayer communication games. Unfortunately, Theorem 1.11 shows that the
technique provably cannot generalize.

See 1.11

Theorem 1.11 is proven by showing that all read-once branching programs
require at least $\operatorname*{poly}(n)$ states to approximately count the
number of ones in a length $n$ stream. Hence in a communication protocol
across $n$ players where each player is given a single bit and the goal is to
approximately count the number of ones held across all players, the maximum
communication by a single player must be at least $\Omega(\log n)$ bits. This
implies that our techniques which reduce hardness for white-box adversarially
robust algorithms to two-player deterministic communication lower bounds
_cannot_ be generalized to multiplayer deterministic communication lower
bounds, since such a generalization would imply a space lower bound of
$\Omega(\log n)$ for approximate counting, whereas Morris counters use
$\mathcal{O}\left(\log\log
n+\log\frac{1}{\varepsilon}+\log\frac{1}{\delta}\right)$ bits of space.

We now prove Theorem 1.11. Assume that there is an algorithm which, using $s$
bits of memory, counts the number of 1’s in a stream, consisting of 0’s and
1’s, approximately. A key result of this section is that to count up to $n$
1’s up to a factor of $1+\varepsilon$, where $\varepsilon>0$ is constant, we
must have $s=\Omega(\log n)$; this asymptotically matches the bound required
to count it exactly. Moreover the bound that holds even if the streaming
algorithm has access to a clock that keeps track of the index of the input
being read (the algorithm is not charged for the memory required to store the
index). Such an algorithm can be modeled as an oblivious leveled read-once
branching program (also known as Ordered Binary Decision Diagram, abbreviated
as OBDD) of width $2^{s}$ over the input alphabet $\\{0,1\\}$. (Without loss
of generality, we let the stream be infinite and therefore the length of the
OBDD is also infinite.)

More generally, we show that the lower bound applies to a larger class of
counting functions called _monotonic counters_.

######  Definition 3.4 (Monotonic Counters).

Let $\Sigma$ be the input alphabet. A monotonic counter is a function
$\chi:\Sigma^{*}\to\mathbb{N}\backslash\\{0\\}$ satisfying $\chi(\epsilon)=1$
for the empty string111This does not entail a loss of generality for monotonic
counters that can also output 0; such exceptional sequences can be handled
separately. and $\\{\chi(\sigma a)-\chi(\sigma):a\in\Sigma\\}=\\{0,1\\}$, for
every $\sigma\in\Sigma^{*}$.

In words, the counter is initialized to 1 at time 1. The counter can increase
by at most 1 in each time step, and stays the same for at least one input
symbol and strictly increases by 1 for at least one input symbol, thereby
ensuring that the counter can assume all possible values in
$\\{1,2,\dots,t\\}$ at time $t$.

Fix a monotonic counter $\chi$ over an input alphabet $\Sigma$. Let $P$ be an
OBDD also over $\Sigma$ and let $P(\sigma)$ denote the node reached in $P$ on
input $\sigma\in\Sigma^{*}$. Fix any node $u$ in $P$ and let
$C_{u}=\\{\chi(\sigma):P(\sigma)=u\text{ for some }\sigma\\}$ be the nonempty
set of values of the monotonic counter for input sequences that reach node
$u$.

To characterize the error in $P$’s computation, we abstractly let
$\varepsilon:\mathbb{N}\to\mathbb{R}_{\geq 0}$ be a function that represents
the error in approximation. For example:

  1. (1)

$\varepsilon(k)=\delta k$ where $\delta>0$ is a fixed constant
$\quad\Longrightarrow\quad(1+\delta)$-multiplicative approximation.

  2. (2)

$\varepsilon(k)=(n^{\delta}-1)k$ where $0<\delta<1$ is a fixed constant
$\quad\Longrightarrow\quad n^{\delta}$-multiplicative approximation.

  3. (3)

$\varepsilon(k)=n^{\delta}$ where $0\leq\delta<1$ is a fixed constant
$\quad\Longrightarrow\quad n^{\delta}$-additive approximation.

We say that a set $C$ of values is _$\varepsilon$ -bound_ if the deviation of
its maximum value from $k$ is at most $\varepsilon(k)$ for every $k\in C$. We
say that $P$ has error $\varepsilon$ at time $t$ if $C_{u}$ is
$\varepsilon$-bound for every node $u$ at time $t$.

For a node $u$, let $J_{u}=[\min(C_{u}),\max(C_{u})]$ be the interval that
minimally covers $C_{u}$, and let $I_{0}(t)$ be the set of intervals $J_{u}$
over all nodes $u$ at level $t$. Define $I(t)$ to be the set of all maximal
intervals (under set inclusion) in $I_{0}(t)$. Note that $|I(t)|$ is a lower
bound on the number of nodes in $P$ at time $t$. For this section, it suffices
to consider the error in approximation induced by the intervals in $I(t)$.
Namely, if $P$ has error $\varepsilon$ at time $t$, then it implies every
interval of $I(t)$ is $\varepsilon$-bound.

######  Lemma 3.5.

$I(1)=\\{[1,1]\\}$.

###### Proof.

This holds because the initial value of the monotonic counter is 1. ∎

######  Lemma 3.6.

Let $t^{\prime}\geq t\geq 1$. For every interval $[k,\ell]\in I(t)$, there
exists an interval in $I(t^{\prime})$ containing $[k,\ell]$.

###### Proof.

The statement is trivially true for $t^{\prime}=t$ and we show that it holds
for $t^{\prime}=t+1$; it follows by induction that also holds for all
$t^{\prime}\geq t$. Let $u$ be the node in level $t$ such that
$J=J_{u}=[k,\ell]$ is the interval associated with node $u$. Let $\sigma$ be
an input sequence such that $P(\sigma)=u$ and $\chi(\sigma)=k$. Similarly, let
$\rho$ be another input sequence such that $P(\rho)=u$ and $\chi(\rho)=\ell$.

Let $a\in\Sigma$ be such that $\chi(\sigma a)=\chi(\sigma)=k$. Let $v=P(\sigma
a)$ be the node reached in level $t+1$. Then $v=P(\rho a)$ as well and
$\chi(\rho a)\geq\chi(\rho)=\ell$. Thus $J_{v}\supseteq[k,\ell]$ implying that
there is an interval in $I(t+1)$ that contains $[k,\ell]$. ∎

######  Lemma 3.7.

Let $t\geq 1$. For every interval $[k,\ell]\in I(t)$, there exists an interval
in $I(t+1)$ containing $[k+1,\ell+1]$.

###### Proof.

Let $u$, $\sigma$ and $\rho$ be as in the proof of Lemma 3.6. Let $a\in\Sigma$
be such that $\chi(\rho a)=\chi(\rho)+1=\ell+1$. Let $v=P(\rho a)$ be the node
reached in level $t+1$. Then $v=P(\sigma a)$ as well and $\chi(\sigma
a)\leq\chi(\sigma)+1=k+1$. Thus $J_{v}\supseteq[k+1,\ell+1]$ implying that
there is an interval in $I(t+1)$ that contains $[k+1,\ell+1]$.∎

Now fix any family $\\{I(t)\\}_{t\geq 1}$, where $I(t)$ for each “time” $t$ is
a set of maximal intervals. The proof below depends only on the assumption the
family satisfies Lemma 3.5, Lemma 3.6, and Lemma 3.7 above. Our goal is to
give a lower bound on $|I(t)|$ for some appropriate time $t$. We say that $k$
is _present_ at time $t$ if there exists an interval in $I(t)$ whose left
endpoint is $k$.

######  Lemma 3.8.

1 is present at all times.

###### Proof.

By Lemma 3.5, $[1,1]\in I(1)$, and by Lemma 3.6, $I(t)$ contains an interval
$[k,\ell]\supseteq[1,1]$ for each $t\geq 1$. Because $k\geq 1$ we have $k=1$.
∎

We say that $k$ is _exceptional_ at time $t$ if $k$ is present at time $t$ but
$k+1$ is absent at time $t+1$. We show first that if exceptional counts occur
very few times then we get a lower bound $|I(t)|$ for some time $t$. Fix a
time horizon $n$ and the corresponding subfamily $\\{I(t)\\}_{t=1}^{n+1}$. For
each $h\geq 1$, let $\phi_{h}$ be the number of times $t\in\\{1,2,\dots,n\\}$
that some count $1\leq k\leq h$ is exceptional at time $t$.

######  Lemma 3.9.

If $(\phi_{h}+1)h\leq n$, then there exists $t_{0}\in\\{1,2,\dots,n+1\\}$ such
that $|I(t_{0})|\geq h+1$.

###### Proof.

In the interval $[1,n]$, mark the times $t$ when some count $1\leq k\leq h$ is
exceptional at time $t$. The unmarked times can be represented as a disjoint
union of $\phi_{h}+1$ intervals. By the pigeonhole principle, there exists one
interval with size at least $h$. Let $\\{t,t+1,\dots,t+h-1\\}$ be such that no
count $1\leq k\leq h$ is exceptional in that interval. We show by induction
that every count in $\\{1,2,\dots,k\\}$ is present at time $t+k-1$ for $1\leq
k\leq h+1$. That would imply for $k=h+1$ that $|I(t+h)|\geq h+1$. Since
$t+h-1\leq n$, the lemma holds with $t_{0}=t+h$.

The base case $k=1$ follows by Lemma 3.8. Assume the statement holds for some
$1\leq k\leq h$. Then, since each count in $\\{1,2,\dots,k\\}$ is non-
exceptional at time $t+k-1$, it follows by definition that each count in
$\\{2,\dots,k+1\\}$ is present at time $t+k$. Together with Lemma 3.8, it
follows that each count in $\\{1,2,\dots,k+1\\}$ is present at time $t+k$ as
well. ∎

We will now bound $\phi_{h}$ so that the above lemma can be applied for $h$ as
large as possible. The idea below is to show that if a single count is
exceptional too many times, then it belongs to some interval of large length,
violating the approximability guarantee.

######  Lemma 3.10.

Suppose $k$ is exceptional at each time $t\in E$ for some nonempty set $E$.
Then for all $t>\max(E)$, there exists an interval in $I(t)$ containing $k$
whose right endpoint is at least $k+|E|$.

###### Proof.

For every $s\in E$, since $k$ is exceptional at time $s$, it is also present
at time $s$ by definition. Let $t_{0}$ be the minimum value in $E$ and let
$[k,\ell_{0}]\in I(t_{0})$ for some $\ell_{0}$ certify $k$’s presence at time
$t_{0}$. We show the following statement, denoted $P(E,t_{0},\ell_{0})$, by
induction on $|E|$: for each $t>\max(E)$ there exists an interval in $I(t)$
containing $k$ such that its right endpoint is at least $\ell_{0}+|E|$. Since
$\ell_{0}\geq k$, this proves the lemma.

For $|E|=1$, because $[k,\ell_{0}]\in I(t_{0})$, by Lemma 3.7, there exists an
interval $[k^{\prime},\ell^{\prime}]\supseteq[k+1,\ell_{0}+1]$ in
$I(t_{0}+1)$. Because $k+1$ is absent at time $t_{0}+1$, we have
$k^{\prime}\leq k$. By Lemma 3.6, there exists $J\in I(t)$ with
$J\supseteq[k^{\prime},\ell^{\prime}]\supseteq[k,\ell_{0}+1]$. Thus, $k\in J$
and the right endpoint of $J$ is at least $\ell_{0}+1=\ell_{0}+|E|$.

For $|E|>1$, let $t_{1}\neq t_{0}$ denote $\max(E)$. Let $[k,\ell_{1}]\in
I(t_{1})$ for some $\ell_{1}$ certify $k$’s presence at time $t_{1}$. Let
$F=E\backslash\\{t_{1}\\}$ and observe that $t_{0}=\min(F)$ as well. Apply the
induction hypothesis $P(F,t_{0},\ell_{0})$: since $t_{1}>\max(F)$, there
exists an interval in $I(t_{1})$ containing $k$ such that its right endpoint
is at least $\ell_{0}+|F|$. On the other hand, $[k,\ell_{1}]$ is maximal in
$I(t)$, therefore $\ell_{1}\geq\ell_{0}+|F|$.

Apply the induction hypothesis $P(\\{t_{1}\\},t_{1},\ell_{1})$: for every
$t>t_{1}=\max(E)$, there exists an interval in $I(t)$ containing $k$ such that
its right endpoint is at least $\ell_{1}+1\geq\ell_{0}+|F|+1=\ell_{0}+|E|$. ∎

Finally, we consider the situation where every element of $I(n+1)$ is
$\varepsilon$-bound. By Lemma 3.10, each $k$ can be exceptional at most
$\varepsilon(k)$ times in $\\{1,2,\dots,n\\}$. This gives an immediate bound
on $\phi_{h}$ namely $\phi_{h}\leq\sum_{k=1}^{h}\varepsilon(k)$. To apply
Lemma 3.9, we find the largest $h$ such that
$\left(1+\sum_{k=1}^{h}\varepsilon(k)\right)h\leq n$.

For example, when $\varepsilon(k)=\delta k$, where $\delta>0$ is constant, we
have $\sum_{k=1}^{h}\varepsilon(k)\leq\delta h(h+1)/2$. Therefore there exists
a good choice of $h$ with $h=\Theta(n^{1/3})$ that yields a polynomial bound
for $|I(t_{0})|$. For a multiplicative approximation $n^{1-\delta}$, where
$\delta>0$ is constant, we can choose $h=\Theta(n^{\delta^{\prime}/3})$ for
some $0<\delta^{\prime}<\delta$ and still obtain a polynomial bound for
$|I(t_{0})|$. Finally, for an additive approximation $n^{1-\delta}$, we can
choose $h=\Theta(n^{\delta^{\prime}/2})$ for some $0<\delta^{\prime}<\delta$.

The proof of Theorem 1.11 follows by noting that since
$|I(t_{0})|=\Omega(\operatorname*{poly}(n))$, the number of states in any
deterministic approximate counting algorithm must also be
$\Omega(\operatorname*{poly}(n))$. Therefore, the algorithm requires at least
$\Omega(\log n)$ bits of space.

###  3.3 A Communication Complexity Model for White-Box Adversaries

We can formulate the communication game in Theorem 1.8 in terms of a
communication matrix. The communication matrix differs from existing two-
player communication games because the protocol may not necessarily succeed
against all possible inputs to the players; there can be specific inputs to
the protocol that cause failure, provided that these inputs cannot be found by
a $T$-time randomized algorithm. The communication model is particularly
interesting due to the equality problem and its previously discussed
complexity in this model, which depends on the runtime $T$. On the other hand,
problems like set disjointness and index do not seem to exhibit such a
dependence. Thus we believe that this communication complexity model may be of
independent interest.

Assume that there exists a streaming algorithm $\mathcal{A}$ robust against
$T$-time white-box adversaries that can be used to compute a function $f(x,y)$
using $s$ bits of communication with probability $p$. In the communication
protocol, Alice creates a stream $S_{x}$ that induces the input $x$. Alice
runs $\mathcal{A}$ on $S_{x}$ and communicates the $s$-bit state of
$\mathcal{A}$ to Bob. Bob then continues running $\mathcal{A}$ on a stream
$S_{y}$ that induces the input $y$, starting from the $s$-bit state that Bob
receives from Alice. The output $f(x,y)$ is the output of $\mathcal{A}$ when
run on the stream $S_{x}\circ S_{y}$, where $\circ$ denotes concatenation.

We now define a communication matrix for the randomized one-way communication
protocol induced by $\mathcal{A}$. Consider a matrix $M$ whose rows are
indexed by tuples $(x,r_{x})$, where $x$ is Alice’s input and $r_{x}$ is
Alice’s randomness, and whose columns are indexed by tuples $(y,r_{y})$, where
$y$ is Bob’s input and $r_{y}$ is Bob’s randomness. The entry
$M_{(x,r_{x}),(y,r_{y})}$ of $M$ denotes the output of the two-player
communication game when Alice holds $(x,r_{x})$ and Bob holds $(y,r_{y})$.
Since $\mathcal{A}$ uses $s$ space, there exists a partition of the rows of
$M$ into $2^{s}$ parts such that if $(x,r_{x})$ and
$(x^{\prime},r_{x^{\prime}})$ are in the same part, then
$M_{(x,r_{x}),(y,r_{y})}=M_{(x^{\prime},r_{x^{\prime}}),(y,r_{y})}$. This
corresponds to the fact that Alice sends Bob the same $s$-bit state
$\text{state}(x,r_{x})$ whether Alice held $(x,r_{x})$ or
$(x^{\prime},r_{x^{\prime}})$. For each $(x,r_{x})$, define

$p_{\text{state}(x,r_{x})}=\min_{y}\Pr_{r_{y}}[M_{(x,r_{x}),(y,r_{y})}=f(x,y)]$
(1)

which is the minimum probability that $\mathcal{A}$ outputs $f(x,y)$ over all
possible inputs $y$ chosen by a white-box adversary. Note that (1) is well-
defined because
$M_{(x,r_{x}),(y,r_{y})}=M_{(x^{\prime},r_{x^{\prime}}),(y,r_{y})}$ whenever
$\text{state}(x,r_{x})=\text{state}(x^{\prime},r_{x^{\prime}})$. By the
robustness of $\mathcal{A}$ against a white-box adversary, we have the
guarantee that for all inputs $x$,
$\mathbb{E}_{r_{x}}[p_{\text{state}(x,r_{x})}]\geq p$.

We now consider the situation in which the white-box adversary $A$ is
computationally bounded. In this setting, the adversary may not be able to
enumerate over all inputs $y$ and output the $y$ that minimizes
$\Pr_{r_{y}}[M_{(x,r_{x}),(y,r_{y})}=f(x,y)]$. Hence a communication protocol
$\mathcal{A}$ robust against computationally bounded white-box adversaries $A$
satisfies the weaker guarantee that

$\mathbb{E}_{y=A(\text{state}(x,r_{x}))}\Pr_{r_{y}}[M_{(x,r_{x}),(y,r_{y})}=f(x,y)]\geq
p$

for all computationally bounded adversaries $A$ and inputs $x$.

## Acknowledgements

Alec Sun was supported by the NSF Graduate Research Fellowship under Grant
Nos. 1745016, and 2140739. David P. Woodruff and Samson Zhou were supported by
a Simons Investigator Award and by the National Science Foundation under Grant
No. CCF-1815840. This work was performed under the auspices of the U.S.
Department of Energy by Lawrence Livermore National Laboratory under Contract
DE-AC52-07NA27344. LLNL-CONF-833470. Sandeep Silwal is supported by an NSF
Graduate Research Fellowship under Grant No. 1745302, NSF TRIPODS program
(award DMS-2022448), and Simons Investigator Award.

## References

  * [ABD+21] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev.  Adversarial laws of large numbers and optimal regret in online classification.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 447–455, 2021.
  * [ACSS21] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer.  A framework for adversarial streaming via differential privacy and difference estimators.  CoRR, abs/2107.14527, 2021.
  * [AEIK18] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok.  Synthesizing robust adversarial examples.  In Proceedings of the 35th International Conference on Machine Learning, ICML, pages 284–293, 2018.
  * [AGPR99] Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, and Sridhar Ramaswamy.  The aqua approximate query answering system.  In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, pages 574–576, 1999.
  * [AJKS02] Miklós Ajtai, T. S. Jayram, Ravi Kumar, and D. Sivakumar.  Approximate counting of inversions in a data stream.  In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 370–379, 2002.
  * [Ajt96] Miklós Ajtai.  Generating hard instances of lattice problems (extended abstract).  In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 99–108, 1996.
  * [AMS99] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.
  * [AMYZ19] Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou.  Adversarially robust submodular maximization under knapsack constraints.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 148–156, 2019\.
  * [BCM+13] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli.  Evasion attacks against machine learning at test time.  In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD, Proceedings, Part III, pages 387–402, 2013\.
  * [BCW98] Harry Buhrman, Richard Cleve, and Avi Wigderson.  Quantum vs. classical communication and computation.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 63–68, 1998.
  * [BDW19] Arnab Bhattacharyya, Palash Dey, and David P. Woodruff.  An optimal algorithm for $l_{1}$-heavy hitters in insertion streams and related problems.  ACM Trans. Algorithms, 15(1):2:1–2:27, 2019.
  * [BEF+17] Ran Ben-Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard.  Constant time updates in hierarchical heavy hitters.  In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, SIGCOMM, pages 127–140, 2017.
  * [BEF+18] Ran Ben-Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard.  Volumetric hierarchical heavy hitters.  In 26th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, MASCOTS, pages 381–392, 2018.
  * [BEO22] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak.  Adversarially robust streaming via dense-sparse trade-offs.  In 5th Symposium on Simplicity in Algorithms, SOSA, 2022.  (to appear).
  * [BHM+05] Paul Brown, Peter J. Haas, Jussi Myllymaki, Hamid Pirahesh, Berthold Reinwald, and Yannis Sismanis.  Toward automated large-scale information integration and discovery.  In Data Management in a Connected World, Essays Dedicated to Hartmut Wedekind on the Occasion of His 70th Birthday, pages 161–180, 2005.
  * [BHM+21] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou.  Adversarial robustness of streaming algorithms through importance sampling.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, 2021.  (to appear).
  * [BJWY21] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev.  A framework for adversarially robust streaming algorithms.  SIGMOD Rec., 50(1):6–13, 2021.
  * [BMSC17] Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher.  Robust submodular maximization: A non-uniform partitioning approach.  In Proceedings of the 34th International Conference on Machine Learning, ICML, pages 508–516, 2017.
  * [BR93] Mihir Bellare and Phillip Rogaway.  Random oracles are practical: A paradigm for designing efficient protocols.  In CCS ’93, Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62–73, 1993.
  * [BR96] Mihir Bellare and Phillip Rogaway.  The exact security of digital signatures - how to sign with RSA and rabin.  In Advances in Cryptology - EUROCRYPT ’96, International Conference on the Theory and Application of Cryptographic Techniques, Proceeding, pages 399–416, 1996.
  * [BY20] Omri Ben-Eliezer and Eylon Yogev.  The adversarial robustness of sampling.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 49–62, 2020.
  * [CDIM03] Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan.  Comparing data streams using hamming norms (how to zero in).  IEEE Trans. Knowl. Data Eng., 15(3):529–540, 2003.
  * [CFP+16] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya.  The _k_ -mismatch problem revisited.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2039–2052, 2016.
  * [CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi.  The random oracle methodology, revisited.  Journal of the ACM (JACM), 51(4):557–594, 2004.
  * [CGS22] Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl.  Adversarially robust coloring for graph streams.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, 2022.  (to appear).
  * [CH21] Timothy M. Chan and Qizheng He.  More dynamic data structures for geometric set cover with sublinear update time.  In 37th International Symposium on Computational Geometry, SoCG, pages 25:1–25:14, 2021.
  * [Cha10] Timothy M. Chan.  A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries.  J. ACM, 57(3):16:1–16:15, 2010.
  * [CKMS03] Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava.  Finding hierarchical heavy hitters in data streams.  In Proceedings of 29th International Conference on Very Large Data Bases VLDB, pages 464–475. Morgan Kaufmann, 2003.
  * [CKMS04] Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava.  Diamond in the rough: Finding hierarchical heavy hitters in multi-dimensional data.  In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 155–166, 2004.
  * [CKMS08] Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava.  Finding hierarchical heavy hitters in streaming data.  ACM Trans. Knowl. Discov. Data, 1(4):2:1–2:48, 2008.
  * [CKP19] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat.  The streaming k-mismatch problem.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1106–1125, 2019.
  * [CN20] Yeshwanth Cherapanamjeri and Jelani Nelson.  On adaptive distance estimation.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS, 2020.
  * [CZM+18] Ekin Dogus Cubuk, Barret Zoph, Dandelion Mané, Vijay Vasudevan, and Quoc V. Le.  Autoaugment: Learning augmentation policies from data.  CoRR, abs/1805.09501, 2018.
  * [DJMS02] Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, and Vladislav Shkapenyuk.  Mining database structure; or, how to build a data quality browser.  In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pages 240–251, 2002.
  * [DNP+10] Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, and Sergey Yekhanin.  Pan-private streaming algorithms.  In Andrew Chi-Chih Yao, editor, Innovations in Computer Science - ICS,Proceedings, pages 66–80, 2010.
  * [DNSS92] David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, and S. Seshadri.  Practical skew handling in parallel joins.  In 18th International Conference on Very Large Data Bases, Proceedings, pages 27–40. Morgan Kaufmann, 1992.
  * [DSST89] James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan.  Making data structures persistent.  J. Comput. Syst. Sci., 38(1):86–124, 1989.
  * [EGSZ17] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou.  Streaming periodicity with mismatches.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 42:1–42:21, 2017.
  * [EGSZ20] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou.  Periodicity in data streams with wildcards.  Theory Comput. Syst., 64(1):177–197, 2020.
  * [EJS10] Funda Ergün, Hossein Jowhari, and Mert Saglam.  Periodicity in streams.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM Proceedings, pages 545–559, 2010.
  * [ESV03] Cristian Estan, Stefan Savage, and George Varghese.  Automatically inferring patterns of resource consumption in network traffic.  In Proceedings of the ACM SIGCOMM 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pages 137–148, 2003.
  * [FK03] Amos Fiat and Haim Kaplan.  Making data structures confluently persistent.  J. Algorithms, 48(1):16–58, 2003.
  * [GHS+12] Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, and Mary Wootters.  Reusable low-error compressive sampling schemes through privacy.  In IEEE Statistical Signal Processing Workshop, SSP, pages 536–539, 2012.
  * [Goo89] I. J. Good.  C332. surprise indexes and p-values.  Journal of Statistical Computation and Simulation, 32:90–92, 1989\.
  * [GS09] André Gronemeier and Martin Sauerhoff.  Applying approximate counting for computing the frequency moments of long data streams.  Theory Comput. Syst., 44(3):332–348, 2009.
  * [GSS14] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  CoRR, abs/1412.6572, 2014.
  * [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, NeurIPS, 2020.
  * [HPG+17] Sandy H. Huang, Nicolas Papernot, Ian J. Goodfellow, Yan Duan, and Pieter Abbeel.  Adversarial attacks on neural network policies.  In 5th International Conference on Learning Representations, ICLR, 2017.
  * [HW13] Moritz Hardt and David P. Woodruff.  How robust are linear sketches to adaptive inputs?  In Symposium on Theory of Computing Conference, STOC, pages 121–130, 2013.
  * [IEM18] Andrew Ilyas, Logan Engstrom, and Aleksander Madry.  Prior convictions: Black-box adversarial attacks with bandits and priors.  CoRR, abs/1807.07978, 2018.
  * [JW18] Rajesh Jayaram and David P. Woodruff.  Data streams with bounded deletions.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 341–354, 2018.
  * [JW19] Rajesh Jayaram and David P. Woodruff.  Towards optimal moment estimation in streaming and distributed models.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 29:1–29:21, 2019.
  * [Kap04] Haim Kaplan.  Persistent data structures.  In Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004.
  * [KGB16] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial examples in the physical world.  CoRR, abs/1607.02533, 2016.
  * [KGB17] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In 5th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2017.
  * [KL14] Jonathan Katz and Yehuda Lindell.  Introduction to Modern Cryptography, Second Edition.  CRC Press, 2014.
  * [KM15] Neal Koblitz and Alfred J Menezes.  The random oracle model: a twenty-year retrospective.  Designs, Codes and Cryptography, 77(2):587–610, 2015.
  * [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, Proceedings, Part III, pages 94–121, 2021.
  * [KW09] Eyal Kushilevitz and Enav Weinreb.  The communication complexity of set-disjointness with small sets and 0-1 intersection.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 63–72. IEEE Computer Society, 2009.
  * [LCLS17] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song.  Delving into transferable adversarial examples and black-box attacks.  In 5th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2017.
  * [Lig18] Sam Lightstone.  Physical database design for relational databases.  In Encyclopedia of Database Systems, Second Edition. Springer, 2018\.
  * [LL07] Yuan Lin and Hongyan Liu.  Separator: Sifting hierarchical heavy hitters accurately from data streams.  In Advanced Data Mining and Applications, Third International Conference, ADMA, Proceedings, pages 170–182, 2007.
  * [MG82] Jayadev Misra and David Gries.  Finding repeated elements.  Sci. Comput. Program., 2(2):143–152, 1982.
  * [MMNW11] Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright.  Pan-private algorithms via statistics on sketches.  In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 37–48, 2011.
  * [MMS+18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In 6th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2018.
  * [MN21] Boaz Menuhin and Moni Naor.  Keep that card in mind: Card guessing with limited memory.  CoRR, abs/2107.03885, 2021.
  * [MNS11] Ilya Mironov, Moni Naor, and Gil Segev.  Sketching in adversarial environments.  SIAM J. Comput., 40(6):1845–1870, 2011.
  * [Mor78] Robert H. Morris Sr.  Counting large numbers of events in small registers.  Commun. ACM, 21(10):840–842, 1978.
  * [MP13] Daniele Micciancio and Chris Peikert.  Hardness of SIS and LWE with small parameters.  In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference. Proceedings, Part I, pages 21–39, 2013.
  * [MR20] Jalil Moraney and Danny Raz.  On the practical detection of hierarchical heavy hitters.  In 2020 IFIP Networking Conference, Networking, pages 37–45, 2020\.
  * [MWY15] Marco Molinaro, David P. Woodruff, and Grigory Yaroslavtsev.  Amplification of one-way information complexity via codes and noise sensitivity.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP, Proceedings, Part I, pages 960–972, 2015.
  * [NNW12] Jelani Nelson, Huy L. Nguyên, and David P. Woodruff.  On deterministic sketching and streaming for sparse recovery and norm estimation.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM. Proceedings, pages 627–638, 2012.
  * [NY19] Moni Naor and Eylon Yogev.  Bloom filters in adversarial environments.  ACM Trans. Algorithms, 15(3):35:1–35:30, 2019.
  * [PBM+03] Sriram Padmanabhan, Bishwaranjan Bhattacharjee, Timothy Malkemus, Leslie Cranston, and Matthew Huras.  Multi-dimensional clustering: A new data layout scheme in DB2.  In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pages 637–641, 2003.
  * [PP09] Benny Porat and Ely Porat.  Exact and approximate pattern matching in the streaming model.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 315–323, 2009.
  * [RSW22] Mohammad Roghani, Amin Saberi, and David Wajc.  Beating the folklore algorithm for dynamic matching.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, 2022.  (to appear).
  * [SAC+79] Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price.  Access path selection in a relational database management system.  In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pages 23–34. ACM, 1979.
  * [SBBR16] Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K. Reiter.  Accessorize to a crime: Real and stealthy attacks on state-of-the-art face recognition.  In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pages 1528–1540, 2016.
  * [SDNR96] Amit Shukla, Prasad Deshpande, Jeffrey F. Naughton, and Karthikeyan Ramasamy.  Storage estimation for multidimensional aggregates in the presence of hierarchies.  In VLDB’96, Proceedings of 22th International Conference on Very Large Data Bases, pages 522–531, 1996.
  * [SDS+06] Vyas Sekar, Nick G. Duffield, Oliver Spatscheck, Jacobus E. van der Merwe, and Hui Zhang.  LADS: large-scale automated ddos detection system.  In Proceedings of the 2006 USENIX Annual Technical Conference, pages 171–184. USENIX, 2006.
  * [SST+18] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.  Adversarially robust generalization requires more data.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS., pages 5019–5031, 2018.
  * [SZS+14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  International Conference on Learning Representations, 2014.
  * [TG09] Patrick Truong and Fabrice Guillemin.  Identification of heavyweight address prefix pairs in IP traffic.  In 21st International Teletraffic Congress, ITC, pages 1–8, 2009\.
  * [TKP+18] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel.  Ensemble adversarial training: Attacks and defenses.  In 6th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2018.
  * [TMS12] Justin Thaler, Michael Mitzenmacher, and Thomas Steinke.  Hierarchical heavy hitters with the space saving algorithm.  In Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, ALENEX 2012, pages 160–174, 2012.
  * [Vai15] Vinod Vaikuntanathan.  Lecture notes for advanced topics in cryptography: Lattices, 2015.
  * [Waj20] David Wajc.  Rounding dynamic matchings against an adaptive adversary.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 194–207, 2020.
  * [WZ21] David P. Woodruff and Samson Zhou.  Tight bounds for adversarially robust streams and sliding windows via difference estimators.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1183–1196, 2021.
  * [ZSS+04] Yin Zhang, Sumeet Singh, Subhabrata Sen, Nick G. Duffield, and Carsten Lund.  Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications.  In Proceedings of the 4th ACM SIGCOMM Internet Measurement Conference, IMC, pages 101–114, 2004.