# Streaming complexity of CSPs with randomly ordered constraints

Raghuvansh R. Saxena Microsoft Research. Email<EMAIL_ADDRESS>Noah Singer Department of Computer Science, Carnegie Mellon University,
Pittsburgh, PA, USA and Harvard College, Harvard University, Cambridge, MA,
USA. Supported by an NSF Graduate Research Fellowship (Award DGE2140739).
Email<EMAIL_ADDRESS>Madhu Sudan School of Engineering and Applied
Sciences, Harvard University, Cambridge, Massachusetts, USA. Supported in part
by a Simons Investigator Award and NSF Awards CCF 1715187 and CCF 2152413.
Email<EMAIL_ADDRESS>Santhoshini Velusamy School of Engineering and
Applied Sciences, Harvard University, Cambridge, Massachusetts, USA. Supported
in part by a Google Ph.D. Fellowship, a Simons Investigator Award to Madhu
Sudan, and NSF Awards CCF 1715187 and CCF 2152413. Email:
<EMAIL_ADDRESS>
###### Abstract

We initiate a study of the streaming complexity of constraint satisfaction
problems (CSPs) when the constraints arrive in a random order. We show that
there exists a CSP, namely Max-DICUT, for which random ordering makes a
provable difference. Whereas a $4/9\approx 0.445$ approximation of DICUT
requires $\Omega(\sqrt{n})$ space with adversarial ordering, we show that with
random ordering of constraints there exists a $0.48$-approximation algorithm
that only needs $O(\log n)$ space. We also give new algorithms for Max-DICUT
in variants of the adversarial ordering setting. Specifically, we give a two-
pass $O(\log n)$ space $0.48$-approximation algorithm for general graphs and a
single-pass $\widetilde{O}(\sqrt{n})$ space $0.48$-approximation algorithm for
bounded degree graphs.

On the negative side, we prove that CSPs where the satisfying assignments of
the constraints support a one-wise independent distribution require
$\Omega(\sqrt{n})$-space for any non-trivial approximation, even when the
constraints are randomly ordered. This was previously known only for
adversarially ordered constraints. Extending the results to randomly ordered
constraints requires switching the hard instances from a union of random
matchings to simple Erdös-Renyi random (hyper)graphs and extending tools that
can perform Fourier analysis on such instances.

The only CSP to have been considered previously with random ordering is Max-
CUT where the ordering is not known to change the approximability.
Specifically it is known to be as hard to approximate with random ordering as
with adversarial ordering, for $o(\sqrt{n})$ space algorithms. Our results
show a richer variety of possibilities and motivate further study of CSPs with
randomly ordered constraints.

###### Contents

  1. 1 Introduction
    1. 1.1 Previous work
    2. 1.2 Main results
      1. 1.2.1 Positive results
      2. 1.2.2 Positive results in other streaming models
      3. 1.2.3 Negative results
    3. 1.3 Technical contributions
      1. 1.3.1 Positive results
      2. 1.3.2 Negative results
  2. 2 Preliminaries
    1. 2.1 Definitions
      1. 2.1.1 The Random-Order Streaming Model
    2. 2.2 The $\textsf{Max-CSP}(\cdot)$ Problem
    3. 2.3 One Way Communication Protocols
    4. 2.4 Analytical tools
      1. 2.4.1 Random variables
      2. 2.4.2 Fourier analysis over $\mathbb{Z}_{q}$
      3. 2.4.3 Hypergraphs
    5. 2.5 Reservoir sampling in the streaming setting
    6. 2.6 $k$-wise independent hash family
  3. 3 Algorithms for Max-DICUT
    1. 3.1 $O(\log n)$-space random-ordering (single-pass) algorithm
    2. 3.2 Two-pass $O(\log n)$-space adversarial-ordering algorithm
    3. 3.3 $O(D^{3/2}\sqrt{n}\log^{2}n)$-space adversarial-ordering algorithm for degree-$D$ bounded graphs
  4. 4 Lower bounds for Max-CSP in the random-ordering setting
    1. 4.1 The Generalized Uniform Randomized Mask Detection (RMD) Problem
    2. 4.2 Proof of Theorem 1.4
    3. 4.3 Proof of Theorem 4.4
  5. 5 Proof of Theorem 4.3
    1. 5.1 Indististinguishability via Fourier Analysis
    2. 5.2 Properties of random hypergraphs
    3. 5.3 Putting the ingredients together
  6. 6 Hypergraph analyses
    1. 6.1 Proving Lemma 5.4: Upper-bounding the probability of cycles
    2. 6.2 Proving Lemma 5.3: Upper-bounding $h_{k,\alpha}(\ell,n)$

##  1 Introduction

In this paper we consider the streaming complexity of solving constraint
satisfaction problems (CSPs) approximately with randomly ordered constraints.
We introduce these terms below before turning to the context and our work.
Readers familiar with these topics may safely skip to Section 1.1.

##### Constraint satisfaction problems:

A _constraint satisfaction problem (CSP)_ is described by a family of
predicates $\mathcal{F}\subseteq\\{f:\mathbb{Z}_{q}^{k}\to\\{0,1\\}\\}$ where
$k,q\in\mathbb{N}$ and $\mathbb{Z}_{q}=\\{0,\ldots,q-1\\}$. Given such a
family $\mathcal{F}$, an instance $\Psi$ of the problem $\textsf{Max-
CSP}(\mathcal{F})$ on $n$ variables is described by $m$ constraints
$C_{1},\ldots,C_{m}$ where for $i\in[m]$,
$C_{i}=(f_{i},\mathbf{j}(i)=(j_{1}(i),\ldots,j_{k}(i)))$ with
$f_{i}\in\mathcal{F}$ and $\mathbf{j}(i)$ is a sequence of $k$ distinct
elements of $[n]$. An assignment to the $n$ variables is given by
$\mathbf{a}\in\mathbb{Z}_{q}^{n}$. The assignment satisfies $C_{i}$ if
$C_{i}(\mathbf{a}):=f_{i}(a_{j_{1}(i)},\ldots,a_{j_{k}(i)})=1$ and the value
of the assignment on the instance $\Psi$ is given by
$\mathsf{val}_{\Psi}(\mathbf{a})=\frac{1}{m}\sum_{i\in[m]}C_{i}(\mathbf{a})$.
The goal of $\textsf{Max-CSP}(\mathcal{F})$ is to compute
$\mathsf{val}_{\Psi}:=\max_{\mathbf{a}\in\mathbb{Z}_{q}^{n}}\\{\mathsf{val}_{\Psi}(\mathbf{a})\\}$.
We will also be interested in approximation algorithms $\mathbf{ALG}$: Given
$\alpha\in[0,1]$, an $\alpha$-approximation algorithm to $\textsf{Max-
CSP}(\mathcal{F})$ is one whose output satisfies
$\alpha\cdot\mathsf{val}_{\Psi}\leq\mathbf{ALG}(\Psi)\leq\mathsf{val}_{\Psi}$
for every instance $\Psi$.

Many natural problems can be expressed as CSPs. One example of particular
interest to this paper is the Max-DICUT problem which is $\textsf{Max-
CSP}(\\{\textsf{DICUT}\\})$ where
$\textsf{DICUT}:\mathbb{Z}_{2}^{2}\to\\{0,1\\}$ is the predicate
$\textsf{DICUT}(x,y)=(1-x)y$ (with the arithmetic being over
$\mathbb{Z}_{2}$). Max-DICUT can equivalently be viewed as a _graph_ problem
in which variables correspond to vertices and constraints correspond to edges.
The goal is then to estimate the size of the highest-value “directed
partition” (i.e., $\\{0,1\\}$-assignment) of the vertices, where the value of
a partition is the number of edges from $0$-vertices to $1$-vertices.

##### Streaming Algorithms:

The class of algorithms we consider (and rule out) are randomized streaming
algorithms. Inputs to these algorithms arrive as a stream of elements, in our
case a stream of constraints. We consider algorithms that use some bounded
amount of space, denoted $s(n)$, to process the stream and produce their
output. They may toss their own coins to process the stream. In this work we
focus mainly on algorithms whose inputs are randomly ordered, i.e., given an
instance $m$ on variables with constraint $C_{1},\ldots,C_{m}$ a permutation
$\pi:[m]\to[m]$ is chosen uniformly at random and the constraints arrive in
the order $C_{\pi(1)},\ldots,C_{\pi(m)}$. We say that an algorithm is correct
if it outputs a correct answer111Recall that approximation algorithms are not
required to output any one fixed answer. An answer is correct on input $\Psi$
if it lies in the interval
$[\alpha\cdot\mathsf{val}_{\Psi},\mathsf{val}_{\Psi}]$. with probability
$2/3$, where the probability is both over internal coin tosses and over the
random arrival order of the input.

###  1.1 Previous work

The recent years have seen a significant amount of research on the streaming
complexity of approximating CSPs with adversarial order of arrival. We refer
the reader to Chou, Golovnev, Sudan and Velusamy [CGSV21b] for some of the
history. (See also [Sin22] and [Sud22] for some broader surveys.) The summary
of this line of research is a dichotomy result for “sketching algorithms” to
approximate all CSPs, while getting dichotomies in the more general streaming
context for many subclasses. A sketching algorithm is a streaming algorithm
that works by compressing substreams into small summaries called sketches with
the feature that the sketch of a concatenation of two streams can be obtained
from sketches of the two component streams. All known algorithms for CSPs
(with proven guarantees on approximation) are sketching algorithms motivating
the current work. In this work we consider a weakening of the input space, to
random ordering of constraints, to explore the possibility of other
algorithms, or to rule them out.

Turning to random order in graph streaming problems, [KKS14] gave a
$\mathrm{polylog}(n)$-space random-order streaming algorithm for
$\mathrm{polylog}(n)$-approximating the maximum matching problem; [KMNT20]
improved the exponent in the approximation factor. Another line of works
[MMPS17, PS18] explores “generic” ways in which sublinear-time algorithms for
graph problems can be transformed into random-ordering streaming algorithms;
the latter work establishes provable separations for random-ordering streaming
from adversarial-order streaming for problems including estimating the number
of connected components and the minimum spanning tree weight. Most relevantly,
Kapralov, Khanna, and Sudan [KKS15] showed that the CSP $\textsf{Max-
CUT}=\textsf{Max-CSP}(\\{\textsf{CUT}\\})$ where
$\textsf{CUT}:\mathbb{Z}_{2}^{2}\to\\{0,1\\}$ is defined by
$\textsf{CUT}(a,b)=a+b$ cannot be nontrivially approximated by
$o(\sqrt{n})$-space streaming algorithms even in the random-order setting.
Thus, other than [KKS15], the previous works on random-order streaming have
not studied CSPs; and in particular, none of the previous works suggest that
random order of arrival could lead to any algorithmic improvement.

###  1.2 Main results

In this paper, we present both positive (algorithmic) and negative (hardness)
on the usefulness of randomly-ordered streams for approximating CSPs, in
comparison to adversarially-ordered streams.

####  1.2.1 Positive results

Our main positive result asserts that there exists a constraint satisfaction
problem where random arrival of constraints provably leads to better
approximation with $o(\sqrt{n})$ space.

######  Theorem 1.1.

There exists a $O(\log n)$-space streaming algorithm that outputs a
$.483$-approximation to the Max-DICUT value of directed graphs on $n$ vertices
whose edges arrive in a random order.

This theorem is restated as Theorem 3.1 and proved in Section 3.1.

The result above should be contrasted with the result of Chou, Golovnev and
Velusamy [CGV20] who show that for every $\epsilon>0$, a streaming algorithm
that achieves a $(4/9+\epsilon)$-approximation of Max-DICUT requires
$\Omega(\sqrt{n})$ space when the constraints are ordered _adversarially_.
(Note $4/9=0.444\ldots$.) Their lower bound holds in the general setting of
streaming algorithms, with a matching upper bound using a sketching algorithm.
Our algorithm is not a sketching algorithm. This is the only result to our
knowledge for a streaming CSP (even with assumptions on arrival order) where a
non-sketching algorithm outperforms known sketching algorithms.

Indeed the ideas from this algorithm help in contexts other than just the
random arrival order and we describe some of these consequences next.

####  1.2.2 Positive results in other streaming models

The algorithm used to prove Theorem 1.1 can also be modified to the setting of
$2$-pass algorithms with adversarial order as asserted below.

######  Theorem 1.2.

There exists a $O(\log n)$-space 2-pass streaming algorithm that outputs a
$.483$-approximation to the Max-DICUT value of directed graphs on $n$ vertices
under adversarial ordering of edges.

This theorem is restated as Theorem 3.2 and proved in Section 3.2. The 2-pass
algorithm answers an open question in [CGSV21b], perhaps with an unexpected
answer.

Finally, we also show how the algorithm can be further modified to get the
same approximation to Max-DICUT using $\widetilde{O}(\sqrt{n})$ space with a
single-pass streaming algorithm in bounded degree graphs with adversarial
ordering of edges.

######  Theorem 1.3.

There exists a $\widetilde{O}(\sqrt{n})$-space streaming algorithm that
outputs a $.483$-approximation to the Max-DICUT value of bounded-degree
directed graphs on $n$ vertices under adversarial ordering of edges.

Theorem 3.3 states a more detailed relationship between the space needed and
the maximum degree of the graph. It implies the theorem above and is proved in
Section 3.3. We remark that [CGV20] show that $o(\sqrt{n})$ space algorithms
cannot get better than a $4/9$-approximation and their proof actually holds
even when the input graphs are of bounded degree. Thus Theorem 1.3 establishes
the significance of the $\sqrt{n}$-space threshold — again a result that may
be somewhat surprising.

####  1.2.3 Negative results

Returning to our main quest of understanding streaming CSPs in the random-
ordering setting and motivated by the algorithmic potential demonstrated by
Theorem 1.1 above, we re-explore negative results on streaming to see when
they apply also to random arrival ordering. We show that for a broad class of
constraint satisfaction problems, the known hardness results on streaming
algorithms with adversarial ordering, also extend (with non-trivial analysis)
to the case of randomly ordered constraints. We define the class of problems
considered and the approximation lower bound achieved below, starting with the
latter.

We say that an algorithm is _trivial_ if its output is a constant (independent
of the input). For a class of constraints $\mathcal{F}$, define
$\rho_{\min}(\mathcal{F})$ to be the minimum (strictly, infimum) value
$\mathsf{val}_{\Psi}$ over all instance $\Psi$ of $\textsf{Max-
CSP}(\mathcal{F})$. (A priori, $\rho_{\min}(\mathcal{F})$ might not be
computable given $\mathcal{F}$, but [CGSV21b] show it is computable.) Clearly
an algorithm that outputs $\rho=\rho_{\min}(\mathcal{F})$ on every instance is
a valid, but trivial, $\rho$-approximation algorithm for $\textsf{Max-
CSP}(\mathcal{F})$. Motivated by this [CGSV21b] define a problem to be
approximation-resistant to a class of algorithms if for every $\epsilon>0$ it
does not have a $(\rho+\epsilon)$-approximation within the class. Our next
theorem proves a broad class of CSPs to be approximation-resistant to
$o(\sqrt{n})$-space single pass streaming algorithms, even with a random
ordering of constraints.

We now turn to the class of problems covered by our theorem. We say a
predicate $f:\mathbb{Z}_{q}^{k}\to\\{0,1\\}$ _supports one-wise independence_
if there exists a distribution $\mathcal{D}$ supported on $f^{-1}(1)$ whose
marginals are uniform (i.e., if
$\mathbf{a}=(a_{1},\ldots,a_{k})\sim\mathcal{D}$ then for every $i$, $a_{i}$
is distributed uniformly over $\mathbb{Z}_{q}$). We say a family $\mathcal{F}$
_supports one-wise independence_ if every $f\in\mathcal{F}$ supports one-wise
independence. We say a family $\mathcal{F}$ _weakly supports one-wise
independence_ if there exists $\mathcal{F}^{\prime}\subseteq\mathcal{F}$
supporting one-wise independence with
$\rho_{\min}(\mathcal{F}^{\prime})=\rho_{\min}(\mathcal{F})$. Our theorem
below asserts the approximation resistance of $\textsf{Max-CSP}(\mathcal{F})$
on randomly ordered instances when $\mathcal{F}$ weakly supports one-wise
independence.

######  Theorem 1.4.

For every $k,q\in\mathbb{N}$ and $\mathcal{F}$ s.t.
$\mathcal{F}\subseteq\\{f:\mathbb{Z}_{q}^{k}\to\\{0,1\\}\\}$ that weakly
supports one-wise independence, $\textsf{Max-CSP}(\mathcal{F})$ is
approximation resistant to $o(\sqrt{n})$-space streaming algorithms in the
random order model. That is, for every $\epsilon>0$, there exists $\tau>0$
such that every streaming algorithm which
$(\rho_{\min}(\mathcal{F})+\epsilon)$-approximates $\textsf{Max-
CSP}(\mathcal{F})$ in the random-order model uses at least $\tau\sqrt{n}$
space on instances with $n$ variables.

We assert that all known families that are known to be approximation-resistant
to $o(\sqrt{n})$-space single pass streaming algorithms, even under
adversarial ordering, weakly support one-wise independence [CGSV21b]. Such
problems include Max-CUT (and thus our result subsumes that of [KKS15]),
$\textsf{Max-}q\textsf{UniqueGames}$, $\textsf{Max-}q\textsf{Coloring}$, and
$\textsf{Max-}k\textsf{OR}$. The question of proving random-ordering
approximation-resistance for $\textsf{Max-}q\textsf{UniqueGames}$ was posed by
Guruswami and Tao [GT19, §5]. Our result thus strengthens our understanding of
approximation resistance for the broadest class of problems where it was
previously understood.

###  1.3 Technical contributions

####  1.3.1 Positive results

All streaming algorithms for CSPs in previous works [GVV17, CGV20, CGSV21a,
CGSV21b, BHP+22] have been based on measuring generalizations of the “total
bias” of CSP instances defined originally in [GVV17]; this quantity, even in
its richest form from [CGSV21b], is a sum over the variables of some form of
“bias”, and can be computed using norm-sketching algorithms [Ind06, KNW10,
AKO11]. Bias, in turn, roughly measures whether, considering each constraint
in which a variable appears independently, the variable prefers to take one
value more often than others. In the specific case of Max-DICUT, the bias
$\textsf{bias}(i)$ of vertex $i$ is simply $\frac{\textsf{out-
deg}(i)-\textsf{in-deg}(i)}{\textsf{out-deg}(i)+\textsf{in-deg}(i)}$, where
$\textsf{out-deg}(i)$ and $\textsf{in-deg}(i)$ denote the out- and in-degrees
of $i$, respectively. Thus, if $\textsf{bias}(i)\approx 1$, $i$ has mostly
out-edges, so we should assign it to $0$, while if
$\textsf{bias}(i)\approx-1$, it has mostly in-edges, so we should assign $i$
to $1$.

Thus, for the random-ordering algorithmic result, a key contribution of our
work is the first new _algorithmic_ paradigm for streaming CSPs since [GVV17].
This should be contrasted with the fact that many works [GT19, KK19, CGV20,
CGSV21a, CGSV21b, SSV21, CGS+22] have made significant progress on the
hardness front. Instead of estimating the _total_ bias of the input graph, we
build a snapshot of the graph: Specifically we merge vertices with (roughly)
the same bias and estimate the fraction of edges that go from vertices of
different bias. To get this snapshot information, we look at a representative
sample of edges and consider the biases of their endpoints. Here is where we
use the random arrival order of edges: We can sample typical edges at the
beginning of the stream, and then we measure the bias of their endpoints over
the rest of the stream. (So really our algorithm just needs the first few
edges to be random, and the rest of the stream could even be ordered
adversarially!)

Using this bias information to produce a cut is not trivial, but fortunately
for us a previous work of Feige and Jozeph [FJ15] analyzed exactly this
question. They studied “oblivious algorithms” for Max-DICUT, which are
algorithms which randomly assign each vertex independently based solely on its
bias, and showed the existence of an $\alpha_{\mathrm{FJ}}$-approximation
algorithm for some $\alpha_{\mathrm{FJ}}\in(0.483,0.4899)$. Our theorem
follows by appealing to their result. We remark that based on the trivial
reduction from Max-CUT, Max-DICUT’s approximability for $o(\sqrt{n})$-space
algorithms with randomly ordered constraints is at most $1/2$. And while
[FJ15] showed that oblivious algorithms cannot do better than
$0.4899$-approximations, it is quite possible that other quantities that can
be easily estimated with random arrival orders (such as the number of copies
of $O(1)$-vertex subgraphs, such as paths) could lead to $1/2$-approximation
algorithms.

The idea of computing a snapshot of the graph and then using that (via the
Feige-Jozeph analysis) to approximate the Dicut value of a graph turns out to
work in other streaming settings as well. For instance in the two-pass setting
with adversarial ordering of the edges, we can pick a random sample of edges
in the first pass and then use the second pass to compute the bias of the
endpoints of the edges. This leads to a polylog space streaming 2-pass
algorithm achieving the same approximation for Max-DICUT even in the
adversarial arrival setting. In the case of bounded degree graphs also we are
able to compute snapshots with $\widetilde{O}(\sqrt{n})$-space when the edge
arrival order is adversarial. While this requires some additional care, to
deal with very sparse graphs (with most vertices being isolated), the general
plan can be implemented leading to a single-pass
$\widetilde{O}(\sqrt{n})$-space algorithm achieving the same approximation for
Dicut.

####  1.3.2 Negative results

Turning to the negative results that form the technical meat of this paper, we
comment briefly on where previous works used the adversarial ordering and what
we need to do to overcome it. Starting with [KKS15], all hardness results for
streaming $\textsf{Max-CSP}(\mathcal{F})$ problems have been based on
constructing so-called “YES” and “NO” distributions over instances which have
high and low values, respectively (with high probability), and showing that
these are indistinguishable by reducing from a one-way communication problem.
Designing these distributions is typically a trade-off between desired
properties for the streaming lower bound (e.g., optimizing the value gap
between YES and NO instances) and technical considerations in terms of how to
prove the appropriate communication lower bounds (and whether they even hold
at all!). The distributions themselves result from a two-fold process: First,
sample a random hypergraph, and then treat each hyperedge as a CSP constraint
by labeling it with an appropriate predicate $f\in\mathcal{F}$. Indeed, this
“labeling” is the only difference between the YES and NO distributions;
typically, in the NO distribution the labels are completely random, while in
the YES distribution they are selected to be consistent with some global
assignment.

Now, consider the communication problem in which we split up hypergraph edges
and labels among $T=O(1)$ of “players”, and the players must distinguish
between the YES and NO cases. At a high level, the technical complexity of
such problems is closely connected to the structure of the hypergraphs that
the players receive. In particular, it becomes necessary to analyze a counting
problem involving $\mathbb{Z}_{q}$-labelings of edge-vertex incidences with
sum constraints at vertices and density constraints on edges (see Eq. 5.1
below for a technical statement). In previous works aside from [KKS15], each
player’s input hypergraph was a random (partial) _hypermatching_. Crucially,
hypermatchings (of any particular size) are unique up to renaming of vertices.
While this significantly simplifies the combinatorial analysis, it is not
appropriate for proving random-ordering streaming lower bounds. This is
because, in the communication-to-streaming reduction, the resultant stream of
constraints is the concatenation of constraints contributed by each player;
these streams will have the property that in each successive “chunk” of
$\approx 1/T$ constraints, no variables are repeated, which is unlikely in a
randomly-ordered stream. Thus, it is necessary to draw the players’ input
hypergraphs from a different distribution. In the case of Max-CUT, with
alphabet size $q=2$ and arity $k=2$, Kapralov _et al._ [KKS15] instead worked
with general random graphs. Such graphs are no longer unique up to renaming of
vertices; there are many different equivalence classes, and each behaves
differently in the proof of the lower bound. However, [KKS15] manages this
difficulty by showing that (1) cycles are unlikely, and (2) conditioned on
cycle-freeness, each equivalence class corresponds to a union of paths with a
certain length profile. It turns out that both the $k=2$ and $q=2$ assumptions
are significantly helpful the analysis of [KKS15]. If $k>2$, we lose the
decomposition into unions of paths, while if $q>2$, we need to worry about
different $\mathbb{Z}_{q}$-labelings even of the same path, and thus the
length of paths comes into play.

Nevertheless, in our work, we manage to generalize to arbitrary
$k,q\in\mathbb{N}$ by conducting a careful combinatorial analysis of connected
component sizes in random hypergraphs (see Section 6). This allows us to
develop streaming hardness results for all CSPs weakly supporting one-wise
independence (Theorem 1.4). Indeed, we show that perfectly satisfiable
instances (i.e., those with value $1$) are indistinguishable from random
instances with independent, uniformly random constraints!

##  2 Preliminaries

For $n>0$, we use $0^{n}$ to denote the all zeros vector of length $n$ and
$\mathcal{S}(n)$ to denote the set of all permutations mapping the set $[n]$
to itself. Let $\Sigma$ be a set, $n\in\mathbb{N}$, and $\pi\in\mathcal{S}(n)$
be a permutation. For $\sigma\in\Sigma^{n}$ and $i\in[n]$, we use $\sigma_{i}$
to denote coordinate $i$ of $\sigma$ and $\pi(\sigma)$ to denote the vector
$\sigma_{\pi(1)},\sigma_{\pi(2)},\ldots,\sigma_{\pi(n)}$. For
$\sigma\in\Sigma^{*}$, we use $\left\lvert\sigma\right\rvert$ to denote the
number of coordinates in $\sigma$.

For a set $S$, we use $\Delta(S)$ to denote the set of all distributions whose
support is $S$. For $k>0$ and sets $S_{1},S_{2},\ldots,S_{k}$, we use
${\Delta_{\mathsf{unif}}}(S_{1},S_{2},\ldots,S_{k})$ to denote the set of all
distributions on the product set $S=S_{1}\times S_{2}\times\ldots\times S_{k}$
for which the marginal distribution on the set $S_{i}$, for all $i\in[k]$ is
uniform. We simply write ${\Delta_{\mathsf{unif}}}(S)$ if the decomposition
into the sets $S_{i}$ is clear from context.

###  2.1 Definitions

####  2.1.1 The Random-Order Streaming Model

Let $\Sigma$ be an alphabet set. A deterministic streaming algorithm
$\mathbf{ALG}$ for $\Sigma$-streams is defined by the tuple:

$\mathbf{ALG}=\left\lparen S,\mathsf{mdfy},\mathsf{out}\right\rparen,$

where:  (1) $S=\left\lVert\mathbf{ALG}\right\rVert$is the space/memory
required by the algorithm $\mathbf{ALG}$.  (2)
$\mathsf{mdfy}=\Sigma\times\left\\{0,1\right\\}^{S}\to\left\\{0,1\right\\}^{S}$is
the function the algorithm uses to update its state upon reading a symbol from
the stream.  (3)
$\mathsf{out}=\left\\{0,1\right\\}^{S}\to\left\\{0,1\right\\}^{S}$is the
function the algorithm uses to compute its output from its state at the end of
the stream.  We shall suppress arguments on the right hand side when they are
clear from context. We define a randomized streaming algorithm on
$\Sigma$-streams to be a distribution over deterministic streaming algorithms.
Additionally, the space required by a randomized streaming algorithm is the
maximum space required by a deterministic algorithm in its support.

##### Execution of a streaming algorithm.

Let $\Sigma$ be an alphabet set and $\mathbf{ALG}$ be a (deterministic)
algorithm for $\Sigma$-streams. For an element $\sigma\in\Sigma^{*}$ with
$m=\left\lvert\sigma\right\rvert$, the algorithm $\mathbf{ALG}$ acts on
$\sigma$ in $m$ steps as follows. At the beginning (before step $1$), the
algorithm is the state $s_{0}=0^{S}$. Then, for $i\in[m]$, the algorithm reads
the symbol $\sigma_{i}$ and uses it to update its state by defining
$s_{i}=\mathsf{mdfy}\left\lparen\sigma_{i},s_{i-1}\right\rparen$. Finally,
after $m$ steps, the algorithm outputs the value $\mathsf{out}(s_{m})$.

Note that all the states of the algorithm and its final output are determined
by its input $\sigma$. For $i\in[m]$, we write
$\mathbf{ALG}(\sigma,i)\in\left\\{0,1\right\\}^{S}$ to denote the state after
step $i$ of the algorithm on input $\sigma$. We define
$\mathbf{ALG}(\sigma,0)=0^{S}$ for convenience. Finally, we write
$\mathbf{ALG}(\sigma)\in\left\\{0,1\right\\}$ to denote the output of the
algorithm on input $\sigma$.

##### Computation using streaming algorithms.

Let $\Sigma$ be an alphabet set and $f:\Sigma^{*}\to\left\\{0,1\right\\}$ be a
(possibly partial) function. For $p>0$, we say that a randomized streaming
algorithm $\mathcal{A}$ computes the function $f$ in the random-order
streaming model with probability $p$ if for all $\sigma\in\Sigma^{*}$, we
have:

$\Pr_{\mathbf{ALG}\sim\mathcal{A},\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen}\left\lparen\mathbf{ALG}\left\lparen\pi\left\lparen\sigma\right\rparen\right\rparen=f(\sigma)\right\rparen\geq
p.$

##### Distinguishing using streaming algorithms.

Let $\Sigma$ be an alphabet set and
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$ be a pair of distributions
over $\Sigma^{*}$. For $\delta\geq 0$, we say that a deterministic streaming
algorithm $\mathbf{ALG}$ distinguishes between $\mathcal{Y}$ and $\mathcal{N}$
with advantage $\delta$ in the random-order streaming model if:

$\left\lvert\Pr_{\sigma\sim\mathcal{Y},\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen}\left\lparen\mathbf{ALG}\left\lparen\pi\left\lparen\sigma\right\rparen\right\rparen=1\right\rparen-\Pr_{\sigma\sim\mathcal{N},\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen}\left\lparen\mathbf{ALG}\left\lparen\pi\left\lparen\sigma\right\rparen\right\rparen=1\right\rparen\right\rvert\geq\delta.$

We say that $\mathbf{ALG}$ distinguishes between $\mathcal{Y}$ and
$\mathcal{N}$ with advantage $\delta$ in the worst case streaming model if:

$\left\lvert\Pr_{\sigma\sim\mathcal{Y}}\left\lparen\mathbf{ALG}\left\lparen\sigma\right\rparen=1\right\rparen-\Pr_{\sigma\sim\mathcal{N}}\left\lparen\mathbf{ALG}\left\lparen\sigma\right\rparen=1\right\rparen\right\rvert\geq\delta.$

We may sometimes refer to a pair
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$ of distributions as a
streaming problem and say that “$\mathbf{ALG}$ solves the
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$-problem” instead of saying
that “$\mathbf{ALG}$ distinguishes between $\mathcal{Y}$ and $\mathcal{N}$”.
We also note that the two notions of distinguishability are equivalent if the
distributions $\mathcal{Y}$ and $\mathcal{N}$ are sufficiently symmetric.

######  Lemma 2.1.

Let $\Sigma$ be an alphabet set and $\mathcal{D}$ be a distribution over
$\Sigma^{*}$ such that for all $\sigma\in\Sigma^{*}$ and
$\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen$, we
have
$\mathcal{D}\left\lparen\sigma\right\rparen=\mathcal{D}\left\lparen\pi\left\lparen\sigma\right\rparen\right\rparen$.
Then, for all $\tau\in\Sigma^{*}$, we have:

$\Pr_{\sigma\sim\mathcal{D}}\left\lparen\sigma=\tau\right\rparen=\Pr_{\sigma\sim\mathcal{D},\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen}\left\lparen\pi\left\lparen\sigma\right\rparen=\tau\right\rparen.$

###### Proof.

Let $\mathcal{D}^{\prime}$ be the distribution on $\mathbb{N}$ obtained by
sampling $\sigma$ from $\mathcal{D}$ and outputting
$\left\lvert\sigma\right\rvert$. We can view the process of sampling $\sigma$
from $\mathcal{D}$ and then sampling $\pi$ from
$\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen$ as the
process of first sampling an integer $m\geq 0$ from $\mathcal{D}^{\prime}$,
then sampling a permutation $\pi$ from $\mathcal{S}(m)$ and finally, a string
$\sigma$ from $\mathcal{D}$ conditioned on the fact that
$\left\lvert\sigma\right\rvert=m$. Moreover, as
$\pi\left\lparen\sigma\right\rparen=\tau$ can happen only if
$m=\left\lvert\tau\right\rvert$, we get (using
$m=\left\lvert\tau\right\rvert$):

$\displaystyle\Pr_{\sigma\sim\mathcal{D},\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen}\left\lparen\pi\left\lparen\sigma\right\rparen=\tau\right\rparen$
$\displaystyle=\mathcal{D}^{\prime}(m)\cdot\Pr_{\pi\sim\mathcal{S}(m),\sigma\sim\mathcal{D}|_{\left\lvert\sigma\right\rvert=m}}\left\lparen\pi\left\lparen\sigma\right\rparen=\tau\right\rparen$
$\displaystyle=\mathcal{D}^{\prime}(m)\cdot\frac{1}{m!}\cdot\sum_{\pi\in\mathcal{S}(m)}\Pr_{\sigma\sim\mathcal{D}|_{\left\lvert\sigma\right\rvert=m}}\left\lparen\pi\left\lparen\sigma\right\rparen=\tau\right\rparen$
$\displaystyle=\mathcal{D}^{\prime}(m)\cdot\frac{1}{m!}\cdot\sum_{\pi\in\mathcal{S}(m)}\Pr_{\sigma\sim\mathcal{D}|_{\left\lvert\sigma\right\rvert=m}}\left\lparen\sigma=\pi^{-1}\left\lparen\tau\right\rparen\right\rparen$
$\displaystyle=\mathcal{D}^{\prime}(m)\cdot\frac{1}{m!}\cdot\sum_{\pi\in\mathcal{S}(m)}\Pr_{\sigma\sim\mathcal{D}|_{\left\lvert\sigma\right\rvert=m}}\left\lparen\sigma=\tau\right\rparen$
$\displaystyle=\mathcal{D}^{\prime}(m)\cdot\Pr_{\sigma\sim\mathcal{D}|_{\left\lvert\sigma\right\rvert=m}}\left\lparen\sigma=\tau\right\rparen$
$\displaystyle=\Pr_{\sigma\sim\mathcal{D}}\left\lparen\sigma=\tau\right\rparen.$

∎

######  Corollary 2.2 (Random order to worst-case).

Let $\Sigma$ be an alphabet set and
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$ be a pair of distributions
over $\Sigma^{*}$ such that for all $\sigma\in\Sigma^{*}$ and
$\pi\sim\mathcal{S}\left\lparen\left\lvert\sigma\right\rvert\right\rparen$, we
have
$\mathcal{Y}\left\lparen\sigma\right\rparen=\mathcal{Y}\left\lparen\pi\left\lparen\sigma\right\rparen\right\rparen$
and
$\mathcal{N}\left\lparen\sigma\right\rparen=\mathcal{N}\left\lparen\pi\left\lparen\sigma\right\rparen\right\rparen$.
Then, for all $\delta\geq 0$ and any deterministic streaming algorithm
$\mathbf{ALG}$ from $\Sigma$-streams, we have that $\mathbf{ALG}$
distinguishes between $\mathcal{Y}$ and $\mathcal{N}$ with advantage $\delta$
in the random-order streaming model if and only if $\mathbf{ALG}$
distinguishes between $\mathcal{Y}$ and $\mathcal{N}$ with advantage $\delta$
in the worst case streaming model.

We shall also need the following connection between computation and
distinguishing using streaming algorithms.

######  Fact 2.3.

Let $\Sigma$ be an alphabet set, $f:\Sigma^{*}\to\left\\{0,1\right\\}$ be a
partial function, and $p>0$. If there exists a randomized streaming algorithm
$\mathcal{A}$ that computes the function $f$ in the random-order streaming
model with probability $p$, then for all distributions $\mathcal{Y}$ and
$\mathcal{N}$ supported on $f^{-1}(1)$ and $f^{-1}(0)$ respectively, we have a
deterministic streaming algorithm $\mathbf{ALG}$,
$\left\lVert\mathbf{ALG}\right\rVert\leq\left\lVert\mathcal{A}\right\rVert$
such that $\mathbf{ALG}$ distinguishes between $\mathcal{Y}$ and $\mathcal{N}$
with advantage $2\cdot\left\lparen p-\frac{1}{2}\right\rparen$ in the random-
order streaming model.

###  2.2 The $\textsf{Max-CSP}(\cdot)$ Problem

Throughout this subsection, we let $q,k\in\mathbb{N}$ and $\mathcal{F}$ be a
non-empty set of functions mapping
$\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$. Let $n\geq k\in\mathbb{N}$. An
instance $\Psi$ of $\textsf{Max-CSP}_{n}(\mathcal{F})$ is given by a sequence:

$\Psi=\left\lparen
f_{i},M_{i}\right\rparen_{i>0}\in\left\lparen\mathcal{F}\times\left\\{0,1\right\\}^{k\times
n}\right\rparen^{*},$

where, for all $i\in\left[\left\lvert\Psi\right\rvert\right]$, the matrix
$M_{i}$ is partial permutation matrix, i.e., a matrix with $0,1$ entries and
exactly one $1$ in each row and at most one $1$ in every column. Let
$m=\left\lvert\Psi\right\rvert$. Intuitively, $\Psi$ can be seen as a sequence
of $m$ constraints, with constraint $i\in[m]$ requiring that the function
$f_{i}$ when applied to the $k$ variables indicated by $M_{i}$ evaluates to
$1$. Here, for $j\in[k]$ the $j^{\text{th}}$ variable indicated by $M_{i}$ is
the unique column that has the $1$ in row $j$ of $M_{i}$.

##### Value of $\Psi$.

For an assignment $\mathbf{x}\in\mathbb{Z}_{q}^{n}$ of the $n$ variables, the
fraction of satisfied constraints is given by:

$\mathsf{val}_{\Psi}(\mathbf{x})=\frac{1}{L}\cdot\sum_{i\in[L]}f_{i}\left\lparen
M_{i}\mathbf{x}\right\rparen.$ (2.4)

We define the value of $\Psi$ to be the largest fraction of the constraints
that can be satisfied by an assignment. Thus,

$\mathsf{val}_{\Psi}=\max_{\mathbf{x}\in\mathbb{Z}_{q}^{n}}\mathsf{val}_{\Psi}(\mathbf{x}).$
(2.5)

##### The function $\rho_{\min}(\cdot)$.

The minimum value of an instance of $\textsf{Max-CSP}(\mathcal{F})$ is given
by:

$\rho_{\min}(\mathcal{F})=\inf_{\begin{subarray}{c}n\in\mathbb{N}\\\
\Psi\text{~{}instance of~{}}\textsf{Max-
CSP}_{n}(\mathcal{F})\end{subarray}}\mathsf{val}_{\Psi}.$ (2.6)

The following lemma, taken from [CGSV21b], gives an equivalent formulation of
the function $\rho(\cdot)$ above that is slightly more amenable to analysis.

######  Lemma 2.7 ([CGSV21b], Proposition 2.12).

Let $q,k\in\mathbb{N}$ be given and $\mathcal{F}$ be a non-empty set of
functions mapping $\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$. It holds that:

$\rho_{\min}(\mathcal{F})=\min_{D\in\Delta(\mathcal{F})}\max_{D^{\prime}\in\Delta\left\lparen\mathbb{Z}_{q}\right\rparen}\mathop{\mathbb{E}}_{\begin{subarray}{c}f\sim
D\\\ \mathbf{a}\sim D^{\prime k}\end{subarray}}\left[f(\mathbf{a})\right].$

##### Approximation resistance.

Let $n\geq k\in\mathbb{N}$ and $\epsilon>0$. Define the partial function
$\mathsf{aprx}_{\mathcal{F},n,\epsilon}$ on instances $\Psi$ of $\textsf{Max-
CSP}_{n}(\mathcal{F})$ to be $1$ if $\mathsf{val}_{\Psi}=1$ and $0$ if
$\mathsf{val}_{\Psi}\leq\rho_{\min}(\mathcal{F})+\epsilon$. We are now ready
to define the notion of approximation resistance.

######  Definition 2.8 (Approximation resistance).

Let $q,k\in\mathbb{N}$ be given and $\mathcal{F}$ be a non-empty set of
functions mapping $\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$. Let
$s:\mathbb{N}\to\mathbb{R}$ be a monotone function. We say that $\textsf{Max-
CSP}(\mathcal{F})$ is approximation resistant to $o(s)$ space in the random
order streaming model if for all $\epsilon>0$ and $p>\frac{1}{2}$, there
exists $\tau>0$ such that for all $n\in\mathbb{N}$ and all randomized
streaming algorithms $\mathcal{A}$ that compute
$\mathsf{aprx}_{\mathcal{F},n,\epsilon}$ in the random-order streaming model
with probability $p$, we have $\left\lVert\mathcal{A}\right\rVert\geq\tau\cdot
s(n)$.

##### One-wise independence.

We say that a function $f:\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$ _supports
one-wise independence_ if there exists a distribution
$D\in{\Delta_{\mathsf{unif}}}\left\lparen\mathbb{Z}_{q}^{k}\right\rparen$ that
is supported on $f^{-1}(1)$. Similarly, we say that a family $\mathcal{F}$ of
functions _(strongly) supports one-wise independence_ if all functions in the
family support one-wise independence. Finally, we say that a family
$\mathcal{F}$ _weakly supports one-wise independence_ if there exists a non-
empty sub-family $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ that strongly
supports one-wise independence and satisfies
$\rho_{\min}(\mathcal{F})=\rho_{\min}(\mathcal{F}^{\prime})$.

###  2.3 One Way Communication Protocols

Let $\mathcal{X}^{A}$ and $\mathcal{X}^{B}$ be two sets. We will treat these
sets as the inputs sets for Alice and Bob respectively. We now define one-way
communication protocols between Alice and Bob, where the inputs of the parties
come from the sets $\mathcal{X}^{A}$ and $\mathcal{X}^{B}$ respectively, and
Alice sends a single message to Bob. We start by defining deterministic
protocols. Such a protocol is defined by a tuple:

$\Pi=\left\lparen L,\mathsf{msg},\mathsf{out}\right\rparen,$

where:  (1) $L=\left\lVert\Pi\right\rVert$is the length of the protocol $\Pi$.
(2) $\mathsf{msg}:\mathcal{X}^{A}\to\left\\{0,1\right\\}^{L}$is the function
Alice uses to compute her message.  (3)
$\mathsf{out}:\mathcal{X}^{B}\times\left\\{0,1\right\\}^{L}\to\left\\{0,1\right\\}$is
the function Bob uses to compute his output.  We shall suppress the arguments
on the right hand side when they are clear from context. We define a
randomized protocol to be a distribution over deterministic protocols with the
same input sets. The length of a randomized protocol is defined to be the
maximum length of the deterministic protocols in its support.

##### Execution of a protocol.

Let $\mathcal{X}^{A}$ and $\mathcal{X}^{B}$ be sets and $\Pi$ be a
deterministic protocol with inputs sets $\mathcal{X}^{A}$ and
$\mathcal{X}^{B}$. For $x^{A}\in\mathcal{X}^{A}$ and
$x^{B}\in\mathcal{X}^{B}$, we define the output
$\Pi(x^{A},x^{B})\in\left\\{0,1\right\\}$ of the protocol $\Pi$ on inputs
$x^{A}$ and $x^{B}$ as:

$\Pi(x^{A},x^{B})=\mathsf{out}\left\lparen x^{B},\mathsf{msg}\left\lparen
x^{A}\right\rparen\right\rparen.$

This is because, when the inputs are $x^{A}$ and $x^{B}$, the string
$\mathsf{msg}\left\lparen x^{A}\right\rparen$ is the message sent by Alice to
Bob, and therefore, $\mathsf{out}\left\lparen x^{B},\mathsf{msg}\left\lparen
x^{A}\right\rparen\right\rparen$ is the output computed by Bob upon receiving
this message.

##### One-way communication problems.

We define a communication problem to be a pair of distributions222Note that
this matches our notation for distributional streaming problems. Nonetheless,
the difference will be clear from context.
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$ on the same product set
$\mathcal{X}^{A}\times\mathcal{X}^{B}$. A protocol for the
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$-problem is a one way
communication protocol where Alice’s input comes from the set
$\mathcal{X}^{A}$ and Bob’s input comes from the set $\mathcal{X}^{B}$. Let
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$ be a communication problem
and $\mathsf{\Pi}$ be a randomized communication protocol for the
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$-problem. For $\delta\geq
0$, we say that $\mathsf{\Pi}$ solves the
$\left\lparen\mathcal{Y},\mathcal{N}\right\rparen$-problem with advantage
$\delta$ if we have:

$\left\lvert\Pr_{\begin{subarray}{c}(x^{A},x^{B})\sim\mathcal{Y}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\Pi(x^{A},x^{B})=1\right\rparen-\Pr_{\begin{subarray}{c}(x^{A},x^{B})\sim\mathcal{N}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\Pi(x^{A},x^{B})=1\right\rparen\right\rvert\geq\delta.$

###  2.4 Analytical tools

####  2.4.1 Random variables

######  Lemma 2.9 (Triangle inequality).

Let $\mathcal{Y},\mathcal{N},\mathcal{Z}\in\Delta(\Omega)$. Then

$\|\mathcal{Y}-\mathcal{N}\|_{\mathrm{tv}}\geq\|\mathcal{Y}-\mathcal{Z}\|_{\mathrm{tv}}-\|\mathcal{Z}-\mathcal{N}\|_{\mathrm{tv}}.$

######  Lemma 2.10 (Data processing inequality).

Let $Y,N$ be random variables with sample space $\Omega$, and let $Z$ be a
random variable with sample space $\Omega^{\prime}$ which is independent of
$Y$ and $N$. If $g:\Omega\times\Omega^{\prime}\to\Omega^{\prime\prime}$ is any
function, then

$\|Y-N\|_{\mathrm{tv}}\geq\|g(Y,Z)-g(N,Z)\|_{\mathrm{tv}}.$

We will use the following concentration inequality from [KK19].

######  Lemma 2.11 ([KK19, Lemma 2.5]).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}$ are Bernoulli $\\{0,1\\}$-valued
random variables satisfying, for every $k\in[n]$, $\mathbb{E}[X_{k}\mid
X_{1},\dots,X_{k-1}]\leq p$ for some $p\in(0,1)$. Let $\mu=np$. Then for all
$\Delta>0$,

$\Pr[X\geq\mu+\Delta]\leq\exp\left(-\frac{\Delta^{2}}{2(\mu+\Delta)}\right)\,.$

We also need the following concentration inequality that we prove using Lemma
2.11.

######  Lemma 2.12.

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}$ are Bernoulli $\\{0,1\\}$-valued
random variables satisfying, for every $k\in[n]$, $\mathbb{E}[X_{k}\mid
X_{1},\dots,X_{k-1}]\geq p$ for some $p\in(0,1)$. Let $\mu=np$. Then for all
$\Delta>0$,

$\Pr[X\leq\mu-\Delta]\leq\exp\left(-\frac{\Delta^{2}}{2(n-(\mu-\Delta))}\right)\,.$

###### Proof.

Follows immediately from Lemma 2.11 on the random variables $Y_{i}=1-X_{i}$,
$q=1-p$, and $\nu=nq$ (since $X\leq\mu-\Delta$ is equivalent to
$Y\geq\nu+\Delta$). ∎

####  2.4.2 Fourier analysis over $\mathbb{Z}_{q}$

Let $q\geq 2\in\mathbb{N}$, and let
$\omega\stackrel{{\scriptstyle\mathrm{\small def}}}{{=}}e^{2\pi i/q}$ denote a
(fixed primitive) $q$-th root of unity. Here, we summarize relevant aspects of
Fourier analysis over $\mathbb{Z}_{q}^{n}$; see e.g. [O’D14, §8] for
details.333[O’D14] uses a different normalization for norms and inner
products, essentially because it considers expectations instead of sums over
inputs. Given a function $f:\mathbb{Z}_{q}^{n}\to\mathbb{C}$ and
$\mathbf{s}\in\mathbb{Z}_{q}^{n}$, we define the _Fourier coefficient_

$\widehat{f}(\mathbf{s})\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{n}}\omega^{-\mathbf{s}\cdot\mathbf{x}}f(\mathbf{x})$

where $\cdot$ denotes the inner product over $\mathbb{Z}_{q}$. For
$p\in(0,\infty)$, we define $f$’s _$p$ -norm_

$\|f\|_{p}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\left(\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{n}}|f(\mathbf{x})|^{p}\right)^{1/p}.$

We also define $f$’s $0$-norm

$\|f\|_{0}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{n}}\mathbbm{1}_{f(\mathbf{x})\neq
0}$

(a.k.a. the size of its support and the Hamming weight of its “truth table”).
Also, for $\ell\in\\{0\\}\cup[n]$, we define the _level- $\ell$ Fourier
($2$-)weight_ as

$\mathsf{W}^{\ell}[f]\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}:\|\mathbf{s}\|_{0}=\ell}|\widehat{f}(\mathbf{s})|^{2}.$

These weights are closely connected to $f$’s $2$-norm:

######  Proposition 2.13 (Parseval’s identity).

For every $q,n\in\mathbb{N}$ and $f:\mathbb{Z}_{q}^{n}\to\mathbb{C}$, we have

$\|f\|_{2}^{2}=q^{n}\sum_{\ell=0}^{n}\mathsf{W}^{\ell}[f].$

Moreover, let $\mathbb{D}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\\{w\in\mathbb{C}:|w|\leq 1\\}$ denote the (closed) unit disk in
the complex plane. The following lemma bounding the low-level Fourier weights
for functions mapping into $\mathbb{D}$ is derived from hypercontractivity
theorems in [CGS+22]:

######  Lemma 2.14 ([CGS+22, Lemma 2.11]).

There exists $\zeta>0$ such that the following holds. Let $q\geq
2,n\in\mathbb{N}$ and consider any function
$f:\mathbb{Z}_{q}^{n}\to\mathbb{D}$. If for $c\in\mathbb{N}$, $\|f\|_{0}\geq
q^{n-c}$, then for every $\ell\in\\{1,\ldots,4c\\}$, we have

$\frac{q^{2n}}{\|f\|_{0}^{2}}\mathsf{W}^{\ell}[f]\leq\left(\frac{\zeta
c}{\ell}\right)^{\ell}.$

######  Lemma 2.15.

Let $\mathcal{U}=\mathcal{U}(\mathbb{Z}_{q}^{m})$. Then for all
$\mathcal{Z}\in\Delta(\mathbb{Z}_{q}^{m})$,

$\|\mathcal{Z}-\mathcal{U}\|_{\mathrm{tv}}^{2}\leq
q^{2m}\sum_{\ell=1}^{m}\mathsf{W}^{\ell}[\mathcal{Z}].$

###### Proof.

We have

$\|\mathcal{Z}-\mathcal{U}\|_{\mathrm{tv}}=\frac{q^{m}}{2}\|\mathcal{Z}-\mathcal{U}\|_{1}.$

Thus by Cauchy-Schwartz,

$\|\mathcal{Z}-\mathcal{U}\|_{\mathrm{tv}}^{2}\leq
q^{2m}\|\mathcal{Z}-\mathcal{U}\|_{2}^{2}.$

Finally, we apply Parseval and observe that
$\widehat{\mathcal{Z}}(\mathbf{0})=\widehat{\mathcal{U}}(\mathbf{0})=1$ while
for all $\mathbf{s}\neq\mathbf{0}$, $\widehat{\mathcal{U}}(\mathbf{s})=0$ by
symmetry. ∎

####  2.4.3 Hypergraphs

Let $2\leq k,n\in\mathbb{N}$. A _$k$ -hyperedge_ on $[n]$ is a $k$-tuple
$\mathbf{e}=(e_{1},\ldots,e_{k})\in[n]^{k}$ of distinct indices, and a _$k$
-hypergraph_ (a.k.a. “$k$-uniform hypergraph”) $G$ on $[n]$ is a sequence
$(\mathbf{e}(1),\ldots,\mathbf{e}(m))$ of (not necessarily distinct)
$k$-hyperedges. For $\alpha\in(0,1),n\in\mathbb{N}$, let
$\mathcal{G}_{k,\alpha}(n)$ denote the uniform distribution over
$k$-hypergraphs on $[n]$ with $\alpha n$ hyperedges.

Given a graph $G$ with $m$ edges $\mathbf{e}(1),\ldots,\mathbf{e}(m)$, we
associate each hyperedge $\mathbf{e}(i)$ with a partial permutation matrix
$M_{i}\in\\{0,1\\}^{k\times n}$, such that for each $j\in[k]$, row $j$ has a
$1$ only in position $e(j)_{i}$. We associate to $G$ an _adjacency matrix_
$M\in\\{0,1\\}^{km\times n}$ by stacking together $M_{1},\ldots,M_{m}$. Since
they encode the same information, we will often treat adjacency matrices and
$k$-hypergraphs as interchangeable (and speak of drawing a matrix $M$ from
$\mathcal{G}_{k,\alpha}(n)$.

For a $k$-hypergraph $G$ on vertex-set $[n]$ with hyperedges
$(\mathbf{e}(1),\ldots,\mathbf{e}(m))$, we define the _vertex-hyperedge
incidence graph_ $B_{G}$, which is a bipartite graph (i.e., 2-hypergraph)
defined as follows: The left vertex-set is $[n]$, the right vertex-set is
$[m]$, and there is an edge between $i\in[n]$ and $j\in[m]$ iff
$i\in\mathbf{e}(j)$.

###  2.5 Reservoir sampling in the streaming setting

Reservoir sampling is a term used to refer to a family of randomized streaming
algorithms that are used to sample uniform $k$ random elements from the stream
without prior knowledge on the length of the stream. The simplest algorithm,
known as _Algorithm R_ , was created by Alan Waterman in 1975. The algorithm
runs in $O(k)$ space and works as follows: it maintains a “reservoir” of size
$k$. Initially, the first $k$ elements in the stream are stored in the
reservoir. For $i>k$, when the $i$-th element of the stream, denoted by
$a_{i}$, arrives, the algorithm generates a random number $j$ between $1$ and
$i$, and if $j\leq k$, it replaces the $j$-th element in the reservoir with
$a_{i}$. It is not hard to show that if $m$ elements have arrived in the
stream so far, then the probability of any one of them being in the reservoir
is exactly $k/m$ (see [Vit85] for more details).

###  2.6 $k$-wise independent hash family

A $k$-wise independent hash family is a family of hash functions
$\mathsf{H}(n,m)=\\{h:[n]\rightarrow[m]\\}$ that satisfies the following
properties: For a hash function $h$ drawn uniformly at random from
$\mathsf{H}$,

  * •

for every $x\in[n]$ and $a\in[m]$, $\Pr[h(x)=a]=\frac{1}{m}$, and

  * •

for every distinct $x_{1},\dots,x_{k}\in[n]$, $h(x_{1}),\dots,h(x_{k})$ are
independent random variables.

We give a construction of $\mathsf{H}(n,m)$ for $m=2^{\ell}$ for some
$\ell\in\mathbb{N}$. Let $r\in\mathbb{N}$ be the smallest integer such that
$2^{r}\geq\max\\{n,m\\}$. Let $\mathbb{F}$ be a field of size $2^{r}$.
Consider the hash family
$\mathsf{H}=\\{h_{a_{1},\dots,a_{k}}:a_{i}\in\mathbb{F}\\}$, where
$h_{a_{1},\dots,a_{k}}$ is the hash function defined as follows. Let
$h^{\prime}_{a_{1},\dots,a_{k}}:\mathbb{F}\rightarrow\mathbb{F}$ be the
function defined as $h^{\prime}(x)=\sum_{i=1}^{k}a_{i}x^{i-1}$. Let
$f:[n]\rightarrow\mathbb{F}$ be any injective function and
$g:\mathbb{F}\rightarrow[m]$ be a function such that for every $a\in[m]$,
$|g^{-1}(a)|=2^{r-\ell}$. We define $h_{a_{1},\dots,a_{k}}=g\circ
h^{\prime}_{a_{1},\dots,a_{k}}\circ f$.

To show that $\mathsf{H}$ is a $k$-wise independent family, observe that it
suffices to show that
$\mathsf{H}^{\prime}=\\{h^{\prime}_{a_{1},\dots,a_{k}}:a_{i}\in\mathbb{F}\\}$
is a $k$-wise independent hash family. Indeed, for $x\in[n]$ and $a\in[m]$,

$\Pr_{a_{1},\dots,a_{k}\in\mathbb{F}}[h_{a_{1},\dots,a_{k}}(x)=a]=\Pr_{a_{1},\dots,a_{k}\in\mathbb{F}}[h^{\prime}_{a_{1},\dots,a_{k}}(x)\in
g^{-1}(a)]=2^{r-\ell}\cdot 2^{-r}=2^{-\ell}\,.$

The independence of $h(x_{1}),\dots,h(x_{k})$ follows from the independence of
$h^{\prime}(x_{1}),\dots,h^{\prime}(x_{k})$. It is a standard exercise to show
that $\mathsf{H}^{\prime}$ is a $k$-wise independent family (see [Vad12] for
instance).

##  3 Algorithms for Max-DICUT

We review the definition of Max-DICUT as an optimization problem on unweighted
directed graphs. Let $\mathcal{G}=(V,E)$ be an unweighted directed
(multi)graph. $\mathcal{G}$’s Max-DICUT value, denoted
$\mathsf{val}_{\mathcal{G}}$, is defined as the size of the largest directed
cut in the graph. Formally,

$\mathsf{val}_{\mathcal{G}}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\max_{L,R:V=L\sqcup R}|E_{L\rightarrow R}|\,,$

where $E_{L\rightarrow R}=\\{(i,j)\in E:i\in L\text{ and }j\in R\\}$. In this
section, we prove the following three theorems for a constant
$\alpha_{\mathrm{FJ}}\geq 0.483$:

######  Theorem 3.1 (Random-ordering algorithm).

Let $\epsilon>0$ and $c>0$ be constants. There exists an $O(\log n)$-space
single-pass streaming algorithm $\mathbf{ALG}$ such that for every directed
graph $\mathcal{G}=(V,E)$ with $|V|=n$ and $|E|\leq n^{c}$, the following
holds: On input the edges of $\mathcal{G}$ in a uniformly random order,
$\mathbf{ALG}$ outputs an $(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to
$\mathsf{val}_{\mathcal{G}}$ with probability at least $2/3$.

######  Theorem 3.2 (Two-pass algorithm).

Let $\epsilon>0$ and $c>0$ be constants. There exists an $O(\log n)$-space
_two-pass_ streaming algorithm $\mathbf{ALG}$ such that for every directed
graph $\mathcal{G}=(V,E)$ with $|V|=n$ and $|E|\leq n^{c}$, the following
holds: On input the edges of $\mathcal{G}$ in adversarial order,
$\mathbf{ALG}$ outputs an $(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to
$\mathsf{val}_{\mathcal{G}}$ with probability at least $2/3$.

######  Theorem 3.3 (Bounded-degree algorithm).

Let $\epsilon>0$, $c>0$ be constants. There exists an
$O(D^{3/2}\sqrt{n}\log^{2}n)$-space single-pass streaming algorithm
$\mathbf{ALG}$ such that for every directed graph $\mathcal{G}=(V,E)$ with
$|V|=n$, $|E|\leq n^{c}$, and max-degree at most $D$, the following holds: On
input the edges of $\mathcal{G}$ in adversarial order, $\mathbf{ALG}$ outputs
an $(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to
$\mathsf{val}_{\mathcal{G}}$ with probability at least $2/3$.

But first, we build some notation. The _bias_ of a vertex $i\in V$ with
respect to a directed graph $\mathcal{G}=(V,E)$, denoted
$\textsf{bias}_{\mathcal{G}}(i)$, is defined as
$\textsf{bias}_{\mathcal{G}}(i)=\frac{\textsf{out-
deg}_{\mathcal{G}}(i)-\textsf{in-deg}_{\mathcal{G}}(i)}{\textsf{out-
deg}_{\mathcal{G}}(i)+\textsf{in-deg}_{\mathcal{G}}(i)}$, where $\textsf{out-
deg}_{\mathcal{G}}(i),\textsf{in-deg}_{\mathcal{G}}(i)$ respectively denote
the out-degree and in-degree of $i$ in $\mathcal{G}$. We now define a quantity
called the “density matrix” of a graph with respect to a partition of its
vertices into bias intervals. Given any vector
$\mathbf{t}=(t_{1},\ldots,t_{\ell})\in[-1,1]^{\ell}$ satisfying
$-1=t_{1}<\cdots<t_{\ell}=1$, we let $\mathcal{P}_{\mathcal{G},\mathbf{t}}$
denote the “canonical” partition partition of $V$ into blocks of vertices
$V=V_{1}\sqcup\cdots\sqcup V_{\ell}$ where for every $r\in[\ell-1]$,
$V_{r}=\\{i:\textsf{bias}_{\mathcal{G}}(i)\in[t_{r},t_{r+1})\\}$, and
$V_{\ell}=\\{i:\textsf{bias}_{\mathcal{G}}(i)=1\\}$. Now the density matrix of
$\mathcal{G}$ with respect to $\mathbf{t}$, denoted by
$M_{\mathcal{G},\mathbf{t}}$, is an $\ell\times\ell$ matrix of natural numbers
defined as $M_{\mathcal{G},\mathbf{t}}(i,j)=|E_{V_{i}\rightarrow V_{j}}|$, for
every $i,j\in[\ell]$, i.e., the $(i,j)$-th entry of
$M_{\mathcal{G},\mathbf{t}}$ counts the number of edges in $\mathcal{G}$
between vertices with biases in the intervals $[t_{i},t_{i+1})$ (or $\\{1\\}$
if $i=\ell$) and $[t_{j},t_{j+1})$ (or $\\{1\\}$ if $j=\ell$).

The following lemma was proved in [FJ15] and it shows that there exists a
vector $\mathbf{t}$ such that for every directed graph $\mathcal{G}$, the
density matrix of $\mathcal{G}$ with the respect to the canonical partition
$\mathcal{P}_{\mathcal{G},\mathbf{t}}$ can be used to get a good approximation
to the Max-DICUT value of $\mathcal{G}$.

######  Lemma 3.4 ([FJ15]).

There exists a constant $\alpha_{\mathrm{FJ}}\in(0.483,0.4899)$,
$\ell_{\mathrm{FJ}}\in\mathbb{N}$, a vector of bias thresholds
$\mathbf{t}_{\mathrm{FJ}}=(t_{1},\ldots,t_{\ell})\in[-1,1]^{\ell_{\mathrm{FJ}}}$,
and a vector of probabilities
$\mathbf{p}_{\mathrm{FJ}}=(p_{1},\ldots,p_{\ell})\in[0,1]^{\ell}$ such that
for every directed graph $\mathcal{G}$,

$\alpha_{\mathrm{FJ}}\cdot\mathsf{val}_{\mathcal{G}}\leq\sum_{i,j=1}^{\ell_{\mathrm{FJ}}}p_{i}(1-p_{j})M_{\mathcal{G},\mathbf{t}}(i,j)\leq\mathsf{val}_{\mathcal{G}}.$

We observe that algorithmically, the estimate for $\mathsf{val}_{\mathcal{G}}$
in this lemma corresponds to assigning each vertex in block $V_{i}$ to $L$
w.p. $p_{i}$ and $R$ w.p. $1-p_{i}$, independently of all other vertices.

As a corollary of Lemma 3.4, we show that in order to get an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation for the Max-DICUT value of
$\mathcal{G}$, it suffices to obtain an additive $\pm\epsilon^{\prime}m$
approximation for every element of $M_{\mathcal{G},\mathbf{t}}$, for
$\epsilon^{\prime}=O(\epsilon)$.

######  Corollary 3.5.

Let
$\alpha_{\mathrm{FJ}},\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}},\mathbf{p}_{\mathrm{FJ}}$
be as in Lemma 3.4. Let $\mathcal{G}$ be a directed graph and let $m$ denote
the number of edges in $\mathcal{G}$. Let
$\epsilon\in(0,\alpha_{\mathrm{FJ}})$ and
$\epsilon^{\prime}=\frac{\epsilon}{8(\ell_{\mathrm{FJ}})^{2}}$. If there
exists $N\in\mathbb{R}^{\ell_{\mathrm{FJ}}\times\ell_{\mathrm{FJ}}}$ such that
for every $i,j\in[\ell_{\mathrm{FJ}}]$,

$M_{\mathcal{G},\mathbf{t}}(i,j)-\epsilon^{\prime}m\leq N(i,j)\leq
M_{\mathcal{G},\mathbf{t}}(i,j)+\epsilon^{\prime}m\,,$

then

$(\alpha_{\mathrm{FJ}}-\epsilon)\mathsf{val}_{\mathcal{G}}\leq\sum_{i,j\in[\ell_{\mathrm{FJ}}]}p_{i}(1-p_{j})N(i,j)-\frac{\epsilon}{8}m\leq\mathsf{val}_{\mathcal{G}}.$

###### Proof.

For the upper bound, we have

$\displaystyle\sum_{i,j\in[\ell_{\mathrm{FJ}}]}p_{i}(1-p_{j})N(i,j)-\frac{\epsilon}{8}m$
$\displaystyle\leq\sum_{i,j\in[\ell_{\mathrm{FJ}}]}p_{i}(1-p_{j})(M_{\mathcal{G},\mathbf{t}}(i,j)+\epsilon^{\prime}m)-\frac{\epsilon}{8}m$
(assumption on $N(i,j)$)
$\displaystyle\leq\mathsf{val}_{\mathcal{G}}+(\ell_{\mathrm{FJ}})^{2}\epsilon^{\prime}m-\frac{\epsilon}{8}m$
(Lemma 3.4) $\displaystyle\leq\mathsf{val}_{\mathcal{G}}.$ (choice of
$\epsilon^{\prime}$)

For the lower bound, we have

$\displaystyle\sum_{i,j\in[\ell_{\mathrm{FJ}}]}p_{i}(1-p_{j})N(i,j)-\frac{\epsilon}{8}m$
$\displaystyle\geq\sum_{i,j\in[\ell_{\mathrm{FJ}}]}p_{i}(1-p_{j})(M_{\mathcal{G},\mathbf{t}}(i,j)-\epsilon^{\prime}m)-\frac{\epsilon}{8}m$
(assumption on $N(i,j)$)
$\displaystyle\geq\alpha_{\mathrm{FJ}}\mathsf{val}_{\mathcal{G}}-(\ell_{\mathrm{FJ}})^{2}\epsilon^{\prime}m-\frac{\epsilon}{8}m$
(Lemma 3.4)
$\displaystyle\geq\alpha_{\mathrm{FJ}}\mathsf{val}_{\mathcal{G}}-\frac{\epsilon}{4}m$
(choice of $\epsilon^{\prime}$)
$\displaystyle\geq(\alpha_{\mathrm{FJ}}-\epsilon)\mathsf{val}_{\mathcal{G}}.$
($\mathsf{val}_{\mathcal{G}}\geq\frac{m}{4}$)

∎

In the following subsections, we describe how to estimate
$M_{\mathcal{G},\mathbf{t}}$ in a number of different settings: $O(\log
n)$-space single-pass streaming algorithm under random ordering of edges
(Section 3.1), $O(\log n)$-space two-pass streaming algorithm under
adversarial ordering (Section 3.2), and $O(D^{3/2}\sqrt{n}\log^{2}n)$-space
single-pass streaming algorithm for degree-$D$ bounded graphs under
adversarial ordering (Section 3.3). These algorithms share the same central
principle: First, let $\mathcal{H}=(V,E^{\prime})$ be a subgraph of
$\mathcal{G}=(V,E)$ (i.e., $E^{\prime}\subseteq E$). Given bias thresholds
$-1=t_{1}<\cdots<t_{\ell}=1$, let
$M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}\in\mathbb{N}^{\ell\times\ell}$
denote the matrix with entries
$M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}(i,j)=|E^{\prime}_{V_{i}\to
V_{j}}|$ where $\mathcal{P}_{\mathcal{G},\mathbf{t}}=V_{1}\sqcup\cdots\sqcup
V_{\ell}$ is the canonical partition of $V$ with respect to bias in
$\mathcal{G}$. (Note that this is distinct from the matrices
$M_{\mathcal{G},\mathbf{t}}$ and $M_{\mathcal{H},\mathbf{t}}$ because it
counts _edges_ in $\mathcal{H}$ but measures _bias_ with respect to
$\mathcal{G}$.) Now the strategy of all three algorithms is to somehow sample
a “representative” subgraph $\mathcal{H}$ of $\mathcal{G}$, and then estimate
$M_{\mathcal{G},\mathbf{t}}$ from
$M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}$ simply by multiplying every
entry by a scale factor $\frac{m(\mathcal{G})}{m(\mathcal{H})}$ (where
$m(\mathcal{G})=|E|$ and $m(\mathcal{H})=|E^{\prime}|$). There are two
questions associated with this approach, which we answer differently in each
setting:

  1. 1.

_How do we sample a “representative” subgraph $\mathcal{H}$, which doesn’t
oversample edges from $E_{V_{i}\to V_{j}}$ for any $i,j\in[\ell]$?_ In
Sections 3.1 and 3.2, $\mathcal{H}$ consists of random edges from
$\mathcal{G}$, while in Section 3.3, $\mathcal{H}$ is the subgraph induced on
random vertices from $\mathcal{G}$. In both cases, we show that (for a
sufficiently large sample size), $\mathcal{H}$ is “sufficiently
representative” with high probability using concentration bounds.

  2. 2.

_How do we remember the “global bias” (i.e., the bias in $\mathcal{G}$) of
vertices we sample in $\mathcal{H}$?_ In the single-pass setting, we measure
biases “online”: Each time we see a new vertex appear as an endpoint in an
edge, we decide whether to track its bias over the rest of the stream or not,
and if we decide not to, it cannot have positive degree in $\mathcal{H}$. The
two-pass setting obviates this limitation, since we can decide which vertices
to track in the first pass and then actually track them in the second pass.

###  3.1 $O(\log n)$-space random-ordering (single-pass) algorithm

In this subsection, we prove Theorem 3.1 by showing that Algorithm 1 is an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation streaming algorithm for
computing Max-DICUT value when the edges of the input graph $\mathcal{G}$ are
randomly ordered and uses space at most $O(\log n)$. Algorithm 1 uses
Algorithm 2 as a subroutine to estimate $M_{\mathcal{G},\mathbf{t}}$ within a
small additive error and then uses this estimate to compute an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to the Max-DICUT value of
$\mathcal{G}$. We now describe and analyse Algorithm 1 and Algorithm 2.

Algorithm 1 $\textsf{Random-Order-Dicut}_{\epsilon}(n,\bm{\sigma})$:

1:$n\in\mathbb{N}$ and a stream
$\bm{\sigma}=(\mathbf{e}(1),\ldots,\mathbf{e}(m))$ representing randomly
ordered edges of $\mathcal{G}$ on $n$ vertices.

2:Let $\ell_{\mathrm{FJ}}$, $\mathbf{t}_{\mathrm{FJ}}$,
$\mathbf{p}_{\mathrm{FJ}}$ be from Lemma 3.4. Let $k$ and $m_{0}$ be fixed
according to Lemma 3.6 corresponding to
$\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}}$, and
$\epsilon^{\prime}=\frac{\epsilon}{8(\ell_{\mathrm{FJ}}^{2})}$.

3:Store the first $m_{0}$ edges that arrive in the stream.

4:Let $N\leftarrow\textsf{Random-Order-
Estimate-}M_{\mathcal{G},\mathbf{t}}(n,\bm{\sigma},\mathbf{t}_{\mathrm{FJ}},k)$.

5:if $m<m_{0}$ then

6: Compute $M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$ directly from the stored
edges and $N\leftarrow M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$.

7:Output
$\sum_{i,j=1}^{\ell_{\mathrm{FJ}}}p_{i}(1-p_{j})N(i,j)-\frac{\epsilon}{8}m$.

We are now ready to describe our first algorithm for estimating
$M_{\mathcal{G},\mathbf{t}}$.

Algorithm 2 $\textsf{Random-Order-
Estimate-}M_{\mathcal{G},\mathbf{t}}(n,\bm{\sigma},\mathbf{t},k)$

1:the number $n$ of vertices of a directed graph $\mathcal{G}$, a stream
$\bm{\sigma}=(\mathbf{e}(1),\ldots,\mathbf{e}(m))$ representing randomly
ordered edges of $\mathcal{G}$, bias thresholds $-1=t_{1}<\cdots<t_{\ell}=1$,
and a parameter $k\in\mathbb{N}$.

2:Store the first $k$ edges ($\mathbf{e}(1),\ldots,\mathbf{e}(k)$) of the
stream. Let $\mathcal{H}$ denote the corresponding subgraph.

3:Over the remainder of the stream, track the following:

  * •

for every vertex $i$ with positive degree in $\mathcal{H}$, the degrees
$\textsf{out-deg}_{\mathcal{G}}(i)$ and $\textsf{in-deg}_{\mathcal{G}}(i)$,

  * •

and the total number $m$ of edges in the stream.

4:After the stream ends, compute the following:

  * •

for every $i$ with positive degree in $\mathcal{H}$,
$\textsf{bias}_{\mathcal{G}}(i)$,

  * •

and the matrix $M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}$.

5:$N\in\mathbb{R}^{\ell\times\ell}$, where for every $i,j\in[\ell]$,
$N(i,j)=\frac{m}{k}M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}(i,j)$.

Now the following lemma asserts the correctness of the estimate in Algorithm 2
for a sufficiently large choice of $k$:

######  Lemma 3.6.

For every $\ell\in\mathbb{N}$ and threshold vector
$\mathbf{t}\in[-1,1]^{\ell}$ and $\epsilon^{\prime}>0$, there exists
$k,m_{0}\in\mathbb{N}$ such that for every directed graph $\mathcal{G}=(V,E)$
with $m=|E|\geq m_{0}$ edges, with probability $\frac{2}{3}$, the matrix $N$
output by Algorithm 2 on input $\mathcal{G}$ satisfies, for every
$i,j\in[\ell]$, the inequalities

$M_{\mathcal{G},\mathbf{t}}(i,j)-\epsilon^{\prime}m\leq N(i,j)\leq
M_{\mathcal{G},\mathbf{t}}(i,j)+\epsilon^{\prime}m.$

###### Proof.

Consider the canonical partition
$\mathcal{P}_{\mathcal{G},\mathbf{t}}:V_{1}\sqcup\cdots\sqcup V_{\ell}=V$ of
$\mathcal{G}$ with respect to $\mathbf{t}$. Fix some $i,j\in[\ell]$ (over
which we’ll take a union bound) and let $T=M_{\mathcal{G},\mathbf{t}}(i,j)$
denote the total number of edges in $E_{V_{i}\rightarrow V_{j}}$.

Now consider random variables $X_{1},\ldots,X_{k}$, where $X_{s}$ is the
indicator for the event that $\mathbf{e}(s)$ belongs to $E_{V_{i}\rightarrow
V_{j}}$. Let $X=X_{1}+\cdots+X_{k}$ denote the number of observed edges (i.e.,
edges in $\\{\mathbf{e}(1),\dots,\mathbf{e}(k)\\}$) that belong to
$E_{V_{i}\rightarrow V_{j}}$; thus,
$X=M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}(i,j)$. Note that
$\mathop{\mathbb{E}}[X_{s}]=T/m$ and so $\mathop{\mathbb{E}}[X]=Tk/m$ and
$\mathop{\mathbb{E}}[N(i,j)]=T$. Our goal is to prove that w.h.p.,
$|N(i,j)-T|\leq\epsilon^{\prime}m$; rescaling by $k/m$, we seek to prove that
$|X-Tk/m|\leq\epsilon^{\prime}k$ w.h.p.

For this, we apply the concentration inequalities in Lemmas 2.11 and 2.12 to
show that the inequalities $X-Tk/m\leq\epsilon^{\prime}k$,
$X-Tk/m\geq-\epsilon^{\prime}k$ are violated with probability at most
$\exp(-O_{\epsilon^{\prime}}(k))$. This is sufficient to take a union bound
over $i,j\in[\ell]$ if we pick $k$ sufficiently large in terms of
$\epsilon^{\prime},\ell$ and then $m_{0}$ sufficiently large in terms of $k$.

##### Upper bound.

Since $\mathbf{e}(1),\ldots,\mathbf{e}(s)$ are sampled from $E(\mathcal{G})$
without replacement, for each $s\in[k]$, we have

$\mathop{\mathbb{E}}[X_{s}\mid
X_{1},\ldots,X_{s-1}]=\frac{T-(X_{1}+\cdots+X_{s-1})}{m-(s-1)}\leq\frac{T}{m-k}.$

Setting $p=T/(m-k)$, $\mu=kp$, and $\Delta=\epsilon^{\prime}k/2$, for
sufficiently large $m$, we claim that $\mu-\frac{T}{m}k\leq\Delta$, and thus
that $\mu+\Delta\leq\frac{T}{m}k+\epsilon^{\prime}k$. The claim follows
because, canceling $k$’s and cross-multiplying by $m$ and $m-k$, we get the
inequality $kT\leq\epsilon^{\prime}m(m-k)/2$, which since $T\leq m$ holds
whenever $k\leq\epsilon^{\prime}/(2+\epsilon^{\prime})m$ (which holds for
$m_{0}\geq(2+\epsilon^{\prime})k/\epsilon^{\prime}$).

Now Lemma 2.11 implies that $X\geq\mu+\Delta$ with probability at most

$\exp\left(-\frac{\Delta^{2}}{2(\mu+\Delta)}\right)\leq\exp\left(-\frac{(\epsilon^{\prime})^{2}k^{2}}{8k(m/(m-k)+\epsilon^{\prime}/2)}\right)\leq\exp\left(-\frac{(\epsilon^{\prime})^{2}}{8(1+\epsilon^{\prime}/2)}k\right)$

(using $T\leq m$ and setting $m_{0}\geq 2k$).

##### Lower bound.

As in the upper bound, we get $\mathop{\mathbb{E}}[X_{s}\mid
X_{1},\ldots,X_{s-1}]\geq\frac{T-k}{m-k}$; setting this time $p=(T-k)/(m-k)$,
and again $\mu=pk$ and $\Delta=\epsilon^{\prime}k/2$, we now claim that
$\mu-\Delta\geq\frac{T}{m}k-\epsilon^{\prime}k$; this holds because it’s
implied by the inequality $k(m-T)\leq\epsilon^{\prime}m(m-k)/2$, which again
holds whenever $k\leq\epsilon^{\prime}/(2+\epsilon^{\prime})m$ (now since
$T\geq 0$). Now Lemma 2.12 implies that $X\leq\mu-\Delta$, again with
probability at most

$\exp\left(-\frac{\Delta^{2}}{2(k-(\mu-\Delta))}\right)\leq\exp\left(-\frac{(\epsilon^{\prime})^{2}k}{8(1-(T-k)/(m-k)+\epsilon^{\prime}/2)}\right)\leq\exp\left(-\frac{(\epsilon^{\prime})^{2}}{8(1+\epsilon^{\prime}/2)}k\right)$

(using $T\geq 0$ and again $m_{0}\geq 2k$). ∎

Finally, we prove Theorem 3.1.

###### Proof of Theorem 3.1.

Consider Algorithm 1. We fix
$\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}},\mathbf{p}_{\mathrm{FJ}},\alpha_{\mathrm{FJ}}$
according to Lemma 3.4. For the choice of $k\in\mathbb{N}$ in Lemma 3.6 that
corresponds to $\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}}$, and
$\epsilon^{\prime}=\frac{\epsilon}{8(\ell_{\mathrm{FJ}})^{2}}$, we run
Algorithm 2 with the parameters $\mathbf{t}_{\mathrm{FJ}},k$ on the input
graph $\mathcal{G}$. For $m\geq m_{0}$, Lemma 3.6 implies that with
probability $\frac{2}{3}$, the output $N$ of Algorithm 2 entrywise
approximates $M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$ up to an additive
$\pm\epsilon^{\prime}m$. For $m<m_{0}$, Algorithm 1 computes
$M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$ exactly. Now Corollary 3.5 implies
that the output of Algorithm 1 is an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to the Max-DICUT value of
$\mathcal{G}$ as desired.

Finally, we show that Algorithm 1 can be implemented in $O(\log n)$ space.
Since $m_{0}$ is a constant, it takes only $O(\log n)$ space to store the
first $m_{0}$ edges. Algorithm 2 can be implemented in $O(\log n)$ space since
it takes $O(\log n)$ space to store $k$ edges and we use a simple counter in
step $2$ that uses $O(\log n)$ space for $m$ that is bounded by
$\mathrm{poly}(n)$. ∎

###  3.2 Two-pass $O(\log n)$-space adversarial-ordering algorithm

In this subsection, we show how the random-ordering algorithm presented in
Section 3.1 can be modified to work with adversarial input ordering given
_two_ passes over the input stream to prove Theorem 3.2.

###### Proof of Theorem 3.2.

Let $\mathbf{ALG}$ denote the $(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation
algorithm for Max-DICUT in the random ordering setting (Algorithm 1). Consider
the following algorithm $\mathbf{ALG}^{\prime}$: In the first pass
$\mathbf{ALG}^{\prime}$ uses reservoir sampling (see Section 2.5) to randomly
sample $k$ edges from the stream; this requires $O(k)$ space.444Note that if
the length of the stream is known _a priori_ , there is a simpler sampling
procedure. In the first pass, $\mathbf{ALG}^{\prime}$ can sample every edge in
the stream with probability $\frac{2k}{m}$. Let $S$ denote the number of edges
that were sampled. With high probability, $|S|\geq k$. Now,
$\mathbf{ALG}^{\prime}$ can choose a random subset of $k$ edges from $S$. In
the second pass, it runs the remainder of Algorithm 2 with parameters
$\mathbf{t}_{\mathrm{FJ}},k$ to obtain $N$ and outputs
$\sum_{i,j=1}^{\ell_{\mathrm{FJ}}}p_{i}(1-p_{j})N(i,j)-\frac{\epsilon}{8}m$.
The same proof of correctness, as well as the space analysis for Algorithm 1
works here as well. We conclude that with probability at least $2/3$,
$\mathbf{ALG}^{\prime}$ outputs an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to the Max-DICUT value of
$\mathcal{G}$. ∎

###  3.3 $O(D^{3/2}\sqrt{n}\log^{2}n)$-space adversarial-ordering algorithm
for degree-$D$ bounded graphs

In this subsection, we prove Theorem 3.3 by showing that Algorithm 3 is an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation streaming algorithm for
computing Max-DICUT value of degree-$D$ bounded graphs and uses space at most
$O(D^{3/2}\sqrt{n}\log^{2}n)$. The basic idea is to sample a subset of the
vertices of the input graph $\mathcal{G}$ and estimate
$M_{\mathcal{G},\mathbf{t}}$ using the density matrix for the induced subgraph
$M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}$. However, there are a few
issues that ensue. Firstly, we need to deal with the case where most of
$\mathcal{G}$’s vertices are isolated (i.e., they have degree zero); we manage
this by only sampling vertices which have positive degree, by using a hash
function on these vertices. This, in turn, requires estimating the number $m$
of edges in the stream, which is not known _a priori_. For an estimate
$\widehat{m}$ that satisfies $\widehat{m}\leq m<2\widehat{m}$, with high
probability, Algorithm 4 estimates $M_{\mathcal{G},\mathbf{t}}$ correctly
within a small additive error. Algorithm 3 runs Algorithm 4 for various
estimates of $m$ and using the correct output from Algorithm 4, it computes an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to the Max-DICUT value of
$\mathcal{G}$. We now describe and analyse Algorithm 3 and Algorithm 4.

Algorithm 3 $\textsf{Bounded-Degree-Dicut}_{D}(n,\bm{\sigma})$:

1:$n\in\mathbb{N}$ and a stream
$\bm{\sigma}=(\mathbf{e}(1),\ldots,\mathbf{e}(m))$ representing randomly
ordered edges of $\mathcal{G}$ on $n$ vertices.

2:Let $\ell_{\mathrm{FJ}}$, $\mathbf{t}_{\mathrm{FJ}}$,
$\mathbf{p}_{\mathrm{FJ}}$ be from Lemma 3.4. Let $C_{1}$ and $k$ be fixed
according to Lemma 3.7 corresponding to
$\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}}$, and
$\epsilon^{\prime}=\frac{\epsilon}{8(\ell_{\mathrm{FJ}}^{2})}$.

3:Store the first $2C_{1}^{2}D$ edges that arrive in the stream.

4:for every integer $b$ from $0$ to $\lfloor\log(nD/2)\rfloor$ do

5: $\widehat{N}_{b}\leftarrow\textsf{Bounded-Degree-
Estimate-}M_{\mathcal{G},\mathbf{t}}(n,\bm{\sigma},\mathbf{t}_{\mathrm{FJ}},k,2^{b})$

6: if $\widehat{N}_{b}$ is not Fail then

7: $N\leftarrow\widehat{N}_{b}$.

8:if $m<2C_{1}^{2}D$ then

9: Compute $M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$ directly from the stored
edges and $N\leftarrow M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$.

10:Output
$\sum_{i,j=1}^{\ell_{\mathrm{FJ}}}p_{i}(1-p_{j})N(i,j)-\frac{\epsilon}{8}m$.

Algorithm 4 $\textsf{Bounded-Degree-
Estimate-}M_{\mathcal{G},\mathbf{t}}(n,\bm{\sigma},\mathbf{t},k,\widehat{m})$

1:the number $n$ of vertices of a directed graph $\mathcal{G}$, a stream
$\bm{\sigma}=(\mathbf{e}(1),\ldots,\mathbf{e}(m))$ representing adversarially
ordered edges, a vector $\mathbf{t}=(t_{1},\ldots,t_{\ell})\in[-1,1]^{\ell}$,
and parameters $k,\widehat{m}\in\mathbb{N}$, where $\widehat{m}$ is a power of
$2$.

2:Sample a random hash function $\pi:[n]\to[\widehat{m}]$ from a $4$-wise
independent hash family $\mathsf{H}(n,\widehat{m})$ (see Section 2.6).

3:For the remainder of the stream, track the number of edges $m$ that arrive.

4:Define $s\leftarrow k\sqrt{\widehat{m}}$.

5:Initialize $\widehat{n}\leftarrow 0$.

6:Initialize $\mathcal{H}\leftarrow(V,\emptyset)$, where $V$ is the vertex set
of $\mathcal{G}$.

7:for each edge $\mathbf{e}(t)=(u,v)$ in the stream do

8: if $\pi(u)\leq s$ then

9: Track the bias of $u$. Increase $\widehat{n}$ by $1$ if this is the first
edge incident on $u$.

10: if $\pi(v)\leq s$ then

11: Track the bias of $v$. Increase $\widehat{n}$ by $1$ if this is the first
edge incident on $v$.

12: if $\pi(u)\leq s$ and $\pi(v)\leq s$ then

13: Add $\mathbf{e}$ to $\mathcal{H}$.

14: if $\widehat{n}>(5s\cdot\min\\{n,4\widehat{m}\\})/\widehat{m}$ then

15: Halt and output Fail.

16:if $m<\widehat{m}$ or $m\geq 2\widehat{m}$ then

17: Halt and output Fail.

18:$N\in\mathbb{R}^{\ell\times\ell}$, where for every $i,j\in[\ell]$,
$N(i,j)=\frac{m}{\mu}M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}(i,j)$
where $\mu=ms^{2}/\widehat{m}^{2}$.

The correctness of Algorithm 4 conditioned on the estimate $\widehat{m}$ being
approximately accurate is asserted in the following lemma:

######  Lemma 3.7.

For every $\ell$, threshold vector $\mathbf{t}\in[-1,1]^{\ell}$, and
$\epsilon^{\prime}>0$, there exists $C_{1}=C_{1}(\epsilon^{\prime})>0$ such
that the following holds. Let $\mathcal{G}$ be a graph with $n$ vertices, $m$
edges, and max-degree $\leq D$ such that $m\geq 2C_{1}^{2}D$, and let
$\widehat{m}\in\mathbb{N}$ be such that $\widehat{m}\leq m<2\widehat{m}$. Then
with probability $\frac{2}{3}$ (over the choice of the permutation $\pi$), the
matrix $N$ output by Algorithm 4 on input $\mathcal{G}$ (with parameters
$k=C_{1}\sqrt{D},\widehat{m}$) satisfies, for every $i,j\in[\ell]$, the
inequalities

$M_{\mathcal{G},\mathbf{t}}(i,j)-\epsilon^{\prime}m\leq N(i,j)\leq
M_{\mathcal{G},\mathbf{t}}(i,j)+\epsilon^{\prime}m.$

###### Proof.

Let $p=s/\widehat{m}=k/\sqrt{m}$555Note that $p\leq 1$ since
$\frac{s}{\widehat{m}}=C_{1}\sqrt{\frac{D}{\widehat{m}}}\leq
C_{1}\sqrt{\frac{2D}{m}}\leq 1$, by assumption. and $\mu=p^{2}m$. Conditioned
on $\widehat{m}\leq m<2\widehat{m}$, we first bound the probability that
Algorithm 4 halts and outputs Fail. Observe that $\widehat{n}$ is the number
of non-isolated vertices with hash value at most $s$. Let $S$ denote the set
of non-isolated vertices in $\mathcal{G}$. We have
$|S|\leq\min\\{n,2m\\}\leq\min\\{n,4\widehat{m}\\}$. For vertex $i\in S$, let
$Y_{i}$ be the event that $\pi(i)\leq s$. Let $Y=\sum_{i\in
S}Y_{i}=\widehat{n}$. Let $p=s/\widehat{m}$.We have
$\mathop{\mathbb{E}}[Y_{i}]=p$ for every $i\in[n]$ and hence
$\mathop{\mathbb{E}}[Y]=p|S|$.666Note that $p|S|\geq 1$ since $|S|\geq m/D$
and $p|S|\geq C_{1}\sqrt{\frac{m}{D}}\geq 1$. Since $Y_{i},Y_{j}$ are
independent for $i\neq j$, the variance of $Y$ is given by

$\mathsf{Var}[Y]=p|S|+p^{2}(|S|^{2}-|S|)-p^{2}|S|^{2}\leq p|S|\,.$

So by Chebyshev’s inequality,

$\Pr\left[\big{|}Y-p|S|\big{|}\geq a\sqrt{p|S|}\right]\leq\frac{1}{a^{2}}\,.$

By setting $a$ to be $\sqrt{10}$, we conclude that $\widehat{n}=Y\leq
5p|S|\leq(5s\cdot\min\\{n,4\widehat{m}\\})/\widehat{m}$ with probability at
least $\frac{9}{10}$.

Therefore with probability at least $9/10$, conditioned on $\widehat{m}\leq
m<2\widehat{m}$, Algorithm 4 does not halt and output Fail. Now conditioned on
this event, we show that with high probability, the matrix $N$ output by
Algorithm 4 on input $\mathcal{G}$ (with parameters
$k=C_{1}\sqrt{D},\widehat{m}$) satisfies, for every $i,j\in[\ell]$, the
inequalities

$M_{\mathcal{G},\mathbf{t}}(i,j)-\epsilon^{\prime}m\leq N(i,j)\leq
M_{\mathcal{G},\mathbf{t}}(i,j)+\epsilon^{\prime}m.$

Fix $i,j\in[\ell]$, and let $T=|E_{V_{i}\to
V_{j}}|=M_{\mathcal{G},\mathbf{t}}(i,j)$. Enumerate the edges of $E_{V_{i}\to
V_{j}}$ as $\mathbf{e}(e_{1}),\ldots,\mathbf{e}(e_{T})$ with
$\mathbf{e}(e_{t})=(u_{t},v_{t})$. For $t\in[T]$, let $X_{t}$ be the indicator
variable for the event that $\pi(u_{t})\leq s$ and $\pi(v_{t})\leq s$. The
events $\pi(u_{t})\leq s$ and $\pi(v_{t})\leq s$ each occur with probability
$s/\widehat{m}=p$, and they are independent (since $\mathsf{H}$ is $4$\- and
thus $2$-wise independent). Hence $\mathop{\mathbb{E}}[X_{t}]=p^{2}$ and,
defining
$X=X_{1}+\cdots+X_{T}=M_{\mathcal{H}\subseteq\mathcal{G},\mathbf{t}}(i,j)$, we
have $\mathop{\mathbb{E}}[X]=p^{2}T$ and so
$\mathop{\mathbb{E}}[N(i,j)]=m\mathop{\mathbb{E}}[X]/\mu=m(p^{2}T)/(p^{2}m)=T$.
Now observe that the desired inequality can be restated as
$|N(i,j)-T|\leq\epsilon^{\prime}m$ which, rescaling by $\mu/m=p^{2}$, is
equivalent to the inequality $|X-Tp^{2}|\leq\epsilon^{\prime}\mu$. We prove
that this holds with high probability using Chebyshev’s inequality.

First, we calculate that

$\mathsf{Var}[X]=\sum_{t,t^{\prime}=1}^{T}\mathop{\mathbb{E}}[X_{t}X_{t^{\prime}}]-(Tp^{2})^{2}.$

Also, when $\mathbf{e}(e_{t})$ and $\mathbf{e}(e_{t^{\prime}})$ do not share a
vertex, the events $\pi(u_{t})\leq s,\pi(v_{t})\leq s,\pi(u_{t^{\prime}})\leq
s$, and $\pi(v_{t^{\prime}})\leq s$ are all independent by $4$-wise
independence of $\pi$, and so
$\mathop{\mathbb{E}}[X_{t}X_{t^{\prime}}]=\mathop{\mathbb{E}}[X_{t}]\mathop{\mathbb{E}}[X_{t^{\prime}}]=p^{4}$.
On the other hand, when they are dependent, we can upper-bound
$\mathop{\mathbb{E}}[X_{t}X_{t^{\prime}}]\leq\mathop{\mathbb{E}}[X_{t}]=p^{2}$.
Since $p\leq 1$ and each $X_{t}$ is dependent on at most $D^{\prime}=2D-1$
variables $X_{t^{\prime}}$ (by the max-degree assumption), we have

$\mathsf{Var}[X]\leq(T^{2}-D^{\prime}T)p^{4}+D^{\prime}Tp^{2}-T^{2}p^{4}\leq
D^{\prime}Tp^{2}.$

So by Chebyshev’s inequality,

$\Pr[|X-Tp^{2}|\geq ap\sqrt{D^{\prime}T}]\leq\frac{1}{a^{2}}.$

Setting $ap\sqrt{D^{\prime}T}=\epsilon^{\prime}p^{2}m$, squaring, and
simplifying, we get $a^{2}D^{\prime}T=(\epsilon^{\prime})^{2}p^{2}m^{2}$, so

$\frac{1}{a^{2}}=\frac{D^{\prime}T}{(\epsilon^{\prime})^{2}p^{2}m^{2}}=\frac{D^{\prime}T\widehat{m}}{(\epsilon^{\prime})^{2}k^{2}m^{2}}$

by the definition of $p$. Now $D^{\prime}<2D$, $T\leq m$, and $\widehat{m}\leq
m$ by assumption, and recalling $k=C_{1}\sqrt{D}$, we can upper-bound the
probability by $\frac{2}{(\epsilon^{\prime})^{2}C_{1}^{2}}$, which can be made
arbitrarily small (in particular, less than, say, $1/(100\ell^{2})$) for a
sufficiently large choice of $C_{1}$. ∎

Finally, we prove Theorem 3.3.

###### Proof of Theorem 3.3.

Consider Algorithm 3. We fix
$\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}},\mathbf{p}_{\mathrm{FJ}},\alpha_{\mathrm{FJ}}$
according to Lemma 3.4 and $k$ according to Lemma 3.7 corresponding to
$\ell_{\mathrm{FJ}},\mathbf{t}_{\mathrm{FJ}}$, and
$\epsilon^{\prime}=\frac{\epsilon}{8(\ell_{\mathrm{FJ}})^{2}}$. Since the max-
degree of $\mathcal{G}$ is at most $D$, the number of edges $m$ is at most
$nD/2$. Observe that for every $m$, there is a unique
$b\in[0,\lfloor\log(nD/2)\rfloor]$ such that $2^{b}\leq m<2^{b+1}$. Namely,
for $\widehat{b}=\lfloor\log m\rfloor$, we have $2^{\widehat{b}}\leq
m<2^{\widehat{b}+1}$. For $b=\widehat{b}$, the algorithm executes Algorithm 4
with $\widehat{m}=2^{\widehat{b}}$. For $m\geq 2C_{1}^{2}D$, Lemma 3.7 implies
that with probability $\frac{2}{3}$, the output $N$ of Algorithm 4 entrywise
approximates $M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$ up to an additive
$\pm\epsilon^{\prime}m$. For $m<2C_{1}^{2}D$, Algorithm 3 computes
$M_{\mathcal{G},\mathbf{t}_{\mathrm{FJ}}}$ exactly. Now Corollary 3.5 implies
that output of Algorithm 3 is an
$(\alpha_{\mathrm{FJ}}-\epsilon)$-approximation to the Max-DICUT value of
$\mathcal{G}$ as desired.

Finally, we show that Algorithm 3 can be implemented in
$O(D^{3/2}\sqrt{n}\log^{2}n)$ space. The first $2C_{1}^{2}D$ edges in the
stream can be stored in $O(D\log n)$ space. Since Algorithm 3 executes
Algorithm 4 $O(\log n)$ times, it suffices to prove that Algorithm 4 can be
implemented in $O(D^{3/2}\sqrt{n}\log n)$ space. Firstly, it takes $O(\log n)$
space to store $\pi$ (see Section 2.6 for an example construction). Moreover,
we can maintain the counter for the number of edges using $O(\log m)$ space.
We have $\widehat{n}\leq(5s\cdot\min\\{n,4\widehat{m}\\})/\widehat{m}$. Every
tracked vertex contributes only $O(D\log n)$ space to store its degree and
neighborhood. Therefore, Algorithm 4 requires at most $O\left(D^{3/2}\log
n\cdot\min\\{n,\widehat{m}\\}/\sqrt{\widehat{m}}\right)\leq O(D^{3/2}\log
n\cdot\sqrt{n})$ space. Hence, Algorithm 3 can be implemented in
$O(D^{3/2}\log^{2}n\sqrt{n})$ space. ∎

##  4 Lower bounds for Max-CSP in the random-ordering setting

###  4.1 The Generalized Uniform Randomized Mask Detection (RMD) Problem

We now define the $\mathsf{Generalized\text{-}Uniform\text{-}RMD}$ problem,
the main focus of our lower bound. We shall define both a communication
version and a streaming version. In either case, we need to define a pair of
distributions. As the two pairs are rather closely related, we define them
together.

######  Definition 4.1 ($\mathsf{Generalized\text{-}Uniform\text{-}RMD}$).

Let $q,k\in\mathbb{N}$ be given and $\mathcal{F}$ be a non-empty set of
functions mapping $\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$. Let $\alpha>0$
and $n\in\mathbb{N}$ be parameters and
$\mathcal{D}_{Y}\in\Delta\left\lparen\mathcal{F}\times{\Delta_{\mathsf{unif}}}\left\lparen\mathbb{Z}_{q}^{k}\right\rparen\right\rparen$
be a distribution with finite support777Observe that $\mathcal{D}_{Y}$ is a
finite support distribution over pairs, the second element of which is itself
a distribution.. For all integers $0\leq t\leq\alpha n$ and both versions, we
now define a distribution
$\mathcal{H}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n,t)$ as follows:

  1. 1.

For both versions:

    1. (a)

Sample a vector $\mathbf{x}^{*}$ uniformly at random from
$\mathbb{Z}_{q}^{n}$.

    2. (b)

For all $i\in[\alpha n]$, sample a matrix
$M_{i}\in\left\\{0,1\right\\}^{k\times n}$ uniformly and independently from
the set of all partial permutation matrices888Recall that a partial
permutation matrix is a matrix with $0,1$ entries and exactly one $1$ in each
row and at most one $1$ in every column..

    3. (c)

For all $i\in[\alpha n]$, sample a pair $\left\lparen
f_{i},D_{i}\right\rparen$ independently from $\mathcal{D}_{Y}$.

    4. (d)

For all $i\in[\alpha n]$, sample a vector $\mathbf{b}(i)\in\mathbb{Z}_{q}^{k}$
independently from $D_{i}$ if $i\leq t$ and uniformly and independently from
the set $\mathbb{Z}_{q}^{k}$ if $i>t$.

    5. (e)

For all $i\in[\alpha n]$, set
$\mathbf{z}(i)=M_{i}\mathbf{x}^{*}-\mathbf{b}(i)$.

  2. 2.

Output as follows:

    1. (a)

For the communication version, define $M$ (respectively, $\mathbf{z}$) to be
the matrix (resp., vector) obtained by stacking all the $M_{i}$ (resp.,
$\mathbf{z}(i)$) on top of each other. Also, define the vector $\mathbf{D}$ to
be the vector consisting of the pairs $\left\lparen
f_{i},D_{i}\right\rparen_{i\in[\alpha n]}$. Output the pair
$\left\lparen\mathbf{x}^{*},\left\lparen
M,\mathbf{z},\mathbf{D}\right\rparen\right\rparen$. (The first element of the
pair $\mathbf{x}^{*}$ forms the input for Alice and the second element
$\left\lparen M,\mathbf{z},\mathbf{D}\right\rparen$ forms the input for Bob.)

    2. (b)

For the streaming version, output the stream $\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen_{i\in[\alpha n]}$. (Note that the
length of the stream is $\alpha n$ and each symbol is a triple $\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen$.)

For both versions, the problem
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$
is defined to be the pair of distributions
$\left\lparen\mathcal{H}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n,\alpha
n),\mathcal{H}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n,0)\right\rparen$. We
shall often refer to
$\mathcal{H}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n,\alpha n)$ as the “yes”
distribution and denote it by $\mathcal{Y}$ and
$\mathcal{H}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n,0)$ as the “no”
distribution and denote it by $\mathcal{N}$. The remaining distributions will
only be needed for the streaming version and will be used as “hybrids”.

We note that in the communication version of Definition 4.1, the matrix $M$
given to Bob is the adjacency matrix of a graph sampled from the distribution
$\mathcal{G}_{k,\alpha}(n)$ (see Section 2.4.3).

We now define what it means to solve the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}$ communication problem arising
from the pair $(\mathcal{F},\mathcal{D}_{Y})$ with non-trivial advantage. The
main emphasis of the definition is the advantage one can get as $\alpha\to 0$.
It is natural to expect the advantage to shrink with $\alpha$, and the
definition below requires that the advantage only shrinks linearly with
$\alpha$.

######  Definition 4.2 (Solving
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}$ with non-trivial advantage).

Let $q,k\in\mathbb{N}$ be given and $\mathcal{F}$ be a non-empty set of
functions mapping $\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$. Let
$\mathcal{D}_{Y}\in\Delta\left\lparen\mathcal{F}\times{\Delta_{\mathsf{unif}}}\left\lparen\mathbb{Z}_{q}^{k}\right\rparen\right\rparen$
be a distribution with finite support and $s:\mathbb{N}\to\mathbb{R}$ be a
function. We say that the pair
$\left\lparen\mathcal{F},\mathcal{D}_{Y}\right\rparen$ can be solved with non-
trivial advantage using $o(s)$ communication if there exists $\delta>0$ such
that for all $\alpha,\tau>0$, there exist infinitely many $n\in\mathbb{N}$ for
which there exists a (randomized) protocol $\Pi$ that solves the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem
with advantage $\delta\cdot\alpha$ and satisfies
$\left\lVert\Pi\right\rVert\leq\tau\cdot s(n)$.

###  4.2 Proof of Theorem 1.4

In this section, we state two theorems that together imply Theorem 1.4. These
theorems are then proved in the following sections. First, we have the
following communication lower bound on the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}$ problem.

######  Theorem 4.3.

Let $q,k\in\mathbb{N}$ be given and $\mathcal{F}$ be a non-empty set of
functions mapping $\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$. Let
$\mathcal{D}_{Y}\in\Delta\left\lparen\mathcal{F}\times{\Delta_{\mathsf{unif}}}\left\lparen\mathbb{Z}_{q}^{k}\right\rparen\right\rparen$
be a distribution with finite support. Then,
$\left\lparen\mathcal{F},\mathcal{D}_{Y}\right\rparen$ cannot be solved with
non-trivial advantage using $o(\sqrt{n})$ communication.

We also show why the above communication lower bound implies that certain CSPs
are approximation resistant.

######  Theorem 4.4.

Let $q,k\in\mathbb{N}$ be given and $\mathcal{F}$ be a non-empty set of
functions mapping $\mathbb{Z}_{q}^{k}\to\left\\{0,1\right\\}$ and weakly
supporting one-wise independence. There exists a distribution
$\mathcal{D}_{Y}\in\Delta\left\lparen\mathcal{F}\times{\Delta_{\mathsf{unif}}}\left\lparen\mathbb{Z}_{q}^{k}\right\rparen\right\rparen$
with a finite support such that if
$\left\lparen\mathcal{F},\mathcal{D}_{Y}\right\rparen$ cannot be solved with
non-trivial advantage using $o(\sqrt{n})$ communication, then $\textsf{Max-
CSP}(\mathcal{F})$ is approximation resistant to $o(\sqrt{n})$ space in the
random order streaming model.

###  4.3 Proof of Theorem 4.4

We now prove Theorem 4.4. The proof of Theorem 4.3 is in the following
section. This proof closely follows arguments in [KKS15, CGSV21b].

###### Proof of Theorem 4.4.

As $\mathcal{F}$ weakly supports one wise independence, there exists a non-
empty sub-family $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ that such that
$\rho_{\min}(\mathcal{F})=\rho_{\min}(\mathcal{F}^{\prime})$ and for all
$f\in\mathcal{F}^{\prime}$, there exists a distribution
$D_{f}\in{\Delta_{\mathsf{unif}}}\left\lparen\mathbb{Z}_{q}^{k}\right\rparen$
that is supported on $f^{-1}(1)$. Fix such a family $\mathcal{F}^{\prime}$ and
note by Lemma 2.7 that there exists a distribution
$D\in\Delta(\mathcal{F}^{\prime})$ such that

$\rho_{\min}(\mathcal{F})=\rho_{\min}(\mathcal{F}^{\prime})=\max_{D^{\prime}\in\Delta\left\lparen\mathbb{Z}_{q}\right\rparen}\mathop{\mathbb{E}}_{\begin{subarray}{c}f\sim
D\\\ \mathbf{a}\sim D^{\prime k}\end{subarray}}\left[f(\mathbf{a})\right].$
(4.5)

Define the distribution $\mathcal{D}_{Y}$ to be the one that first samples
$f\sim D$ and then outputs the pair $\left\lparen f,D_{f}\right\rparen$.
Clearly, the support of $\mathcal{D}_{Y}$ is finite and all that remains to be
shown is that if $\left\lparen\mathcal{F},\mathcal{D}_{Y}\right\rparen$ cannot
be solved with non-trivial advantage using $o(\sqrt{n})$ communication, then
$\textsf{Max-CSP}(\mathcal{F})$ is approximation resistant to $o(\sqrt{n})$
space in the random order streaming model. We shall show this in the
contrapositive.

Suppose that $\textsf{Max-CSP}(\mathcal{F})$ is not approximation resistant to
$o(\sqrt{n})$ space in the random order streaming model, and let
$\epsilon>0,p>\frac{1}{2}$ be the parameters promised by Definition 2.8 in
this case. Thus, we have for all $\tau>0$ that there exists $n\in\mathbb{N}$
for which:

$\begin{split}&\text{~{}There exists a randomized streaming algorithms
$\mathcal{A}$, $\left\lVert\mathcal{A}\right\rVert<\tau\cdot\sqrt{n}$ that
~{}}\\\ &\text{~{}computes $\mathsf{aprx}_{\mathcal{F},n,\epsilon}$ in the
random-order streaming model with probability $p$.}\end{split}$

In fact, for any $\tau>0$, we must have infinitely many values of $n$ such
that ($\star$) holds. Indeed, if there is a $\tau$ for which there only
finitely many such $n$, as any non-trivial algorithm must have
$\left\lVert\mathbf{ALG}\right\rVert\geq 1$, we can construct a smaller $\tau$
for which there is no value of $n$ satisfying ($\star$), a contradiction.

To show that $\left\lparen\mathcal{F},\mathcal{D}_{Y}\right\rparen$ can be
solved with non-trivial advantage using $o(\sqrt{n})$ communication, we will
show Definition 4.2 with the parameter $\delta=\theta^{20}$, where we define
$\theta=\frac{\epsilon}{100}\cdot\frac{\left\lparen
p-1/2\right\rparen\cdot\rho_{\min}(\mathcal{F})}{q^{k}}$. Let $\alpha,\tau>0$
be arbitrary. Applying the reasoning in the foregoing paragraph with this
value of $\tau$, we get that there are infinitely many $n\in\mathbb{N}$ for
which ($\star$) holds. Fix any such $n$ that is also larger than
$\left\lparen\frac{k}{\theta}\right\rparen^{5}$ (this only excludes finitely
many values). We will show that there exists a protocol $\Pi$ that solves the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem
with advantage $\delta\cdot\alpha$ and satisfies
$\left\lVert\Pi\right\rVert\leq\tau\cdot\sqrt{n})$. We do this in two steps.

##### Streaming algorithm for
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}$.

As a first step we define $T=\frac{1}{\alpha\cdot\theta^{10}}$ and show that
there exists a deterministic streaming algorithm $\mathbf{ALG}$ that solves
the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha
T}(n)$ problem with advantage $\theta$ in the worst case streaming model. To
this end, for $0\leq t\leq T$, we let $\mathsf{Hyb}^{\mathsf{Str}}(t)$ be the
$\left\lparen\alpha nt\right\rparen^{\text{th}}$ hybrid distribution of
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha
T}(n)$, as defined in Definition 4.1. We also define the distributions
$\mathcal{Y}^{\mathsf{Str}}=\mathsf{Hyb}^{\mathsf{Str}}(T)$ and
$\mathcal{N}^{\mathsf{Str}}=\mathsf{Hyb}^{\mathsf{Str}}(0)$.

For an instance $\Psi=\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen_{i\in[\alpha Tn]}$, we define an
instance $\mathsf{Clean}(\Psi)$ of $\textsf{Max-CSP}_{n}(\mathcal{F})$ so that
for each $i\in[\alpha Tn]$ for which $\mathbf{z}(i)=0^{k}$, the instance
$\mathsf{Clean}(\Psi)$ has (in order) the tuple $\left\lparen
f_{i},M_{i}\right\rparen$. Also define the distribution
$\mathcal{Y}^{\mathsf{CSP}}$ (respectively, $\mathcal{N}^{\mathsf{CSP}}$) to
be the distribution that samples an instance $\Psi$ from
$\mathcal{Y}^{\mathsf{Str}}$ (resp. $\mathcal{N}^{\mathsf{Str}}$) and outputs
$\mathsf{Clean}(\Psi)$. We show that

######  Claim 4.5.

We have $\mathsf{val}_{\Psi^{\prime}}=1$ for all $\Psi^{\prime}$ in the
support of $\mathcal{Y}^{\mathsf{CSP}}$.

###### Proof.

It suffices to show that $\mathsf{val}_{\Psi^{\prime}}\geq 1$. If
$\Psi^{\prime}$ is in the support of $\mathcal{Y}^{\mathsf{CSP}}$, there
exists $\Psi$ in the support of $\mathcal{Y}^{\mathsf{Str}}$ such that
$\mathsf{Clean}(\Psi)=\Psi^{\prime}$. Let $L^{\prime}$ be the length of
$\Psi^{\prime}$ and $\left\lparen
f^{\prime}_{i^{\prime}},M^{\prime}_{i^{\prime}}\right\rparen_{i^{\prime}\in[L^{\prime}]}$
be the constraints in $\Psi^{\prime}$. By definition, we get that for all
$i^{\prime}\in[L^{\prime}]$, there exists an $i=i(i^{\prime})\in[\alpha Tn]$
such that $\left\lparen f_{i},M_{i},\mathbf{z}(i)\right\rparen=\left\lparen
f^{\prime}_{i^{\prime}},M^{\prime}_{i^{\prime}},0^{k}\right\rparen$. Let
$\mathbf{x}^{*}$ as in definition Definition 4.1 be the one that gave rise to
$\Psi$. We have:

$\displaystyle\mathsf{val}_{\Psi^{\prime}}$
$\displaystyle\geq\mathsf{val}_{\Psi^{\prime}}(\mathbf{x}^{*})$
$\displaystyle=\frac{1}{L^{\prime}}\cdot\sum_{i^{\prime}\in[L^{\prime}]}f^{\prime}_{i^{\prime}}\left\lparen
M^{\prime}_{i^{\prime}}\mathbf{x}^{*}\right\rparen$
$\displaystyle=\frac{1}{L^{\prime}}\cdot\sum_{i^{\prime}\in[L^{\prime}]}f_{i(i^{\prime})}\left\lparen
M_{i(i^{\prime})}\mathbf{x}^{*}\right\rparen$
$\displaystyle=\frac{1}{L^{\prime}}\cdot\sum_{i^{\prime}\in[L^{\prime}]}f_{i(i^{\prime})}\left\lparen\mathbf{b}(i(i^{\prime}))\right\rparen$
(As $\mathbf{z}(i(i^{\prime}))=0^{k}$) $\displaystyle=1,$

where the final step uses the fact that
$\mathcal{Y}^{\mathsf{Str}}=\mathsf{Hyb}^{\mathsf{Str}}(T)$ is the yes
distribution in
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha
T}(n)$, which implies that $\mathbf{b}(i(i^{\prime}))\in
f_{i(i^{\prime})}^{-1}(1)$ by our choice of $\mathcal{D}_{Y}$. ∎

######  Claim 4.6.

For all $i\in[\alpha Tn]$ and all $\mathbf{x}\in\mathbb{Z}_{q}^{n}$, we have

$\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen
f_{i}\left\lparen
M_{i}\mathbf{x}\right\rparen=1\right\rparen\leq\rho_{\min}(\mathcal{F})\cdot\left\lparen
1+\theta^{2}\right\rparen.$

###### Proof.

Let $D_{\mathsf{perm}}$ be the distribution that outputs a uniformly random
partial permutation matrix $M\in\left\\{0,1\right\\}^{k\times n}$ and
$D_{\mathsf{row}}$ be the distribution that outputs a uniformly random matrix
$M\in\left\\{0,1\right\\}^{k\times n}$ with exactly one $1$ in every row (but
a column may have more than one $1$). Clearly, $D_{\mathsf{perm}}$ is
$D_{\mathsf{row}}$ conditioned on the event that each row has its $1$ in a
different column. This means that

$\lVert D_{\mathsf{perm}}-D_{\mathsf{row}}\rVert_{\mathrm{tv}}\leq\Pr_{M\sim
D_{\mathsf{row}}}\left\lparen\text{~{}Exists two rows with $1$ in the same
column~{}}\right\rparen\leq\frac{k^{2}}{n}\leq\theta^{2}\cdot\rho_{\min}(\mathcal{F}),$

by our choice of $n,\theta$ We get:

$\displaystyle\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen
f_{i}\left\lparen M_{i}\mathbf{x}\right\rparen=1\right\rparen$
$\displaystyle=\Pr_{f\sim D,M\sim D_{\mathsf{perm}}}\left\lparen f\left\lparen
M\mathbf{x}\right\rparen=1\right\rparen$ (Items 1b and 1c)
$\displaystyle\leq\Pr_{f\sim D,M\sim D_{\mathsf{row}}}\left\lparen
f\left\lparen
M\mathbf{x}\right\rparen=1\right\rparen+\theta^{2}\cdot\rho_{\min}(\mathcal{F}).$
(As $\lVert
D_{\mathsf{perm}}-D_{\mathsf{row}}\rVert_{\mathrm{tv}}\leq\theta^{2}\cdot\rho_{\min}(\mathcal{F})$)

Now, let $D^{\prime}$ be the distribution over $\mathbb{Z}_{q}$ that samples a
uniformly random $i\in[n]$ and outputs $x_{i}$. Observe that distribution of
$M\mathbf{x}$ when $M\sim D_{\mathsf{row}}$ is the same as $D^{\prime k}$. We
get:

$\displaystyle\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen
f_{i}\left\lparen M_{i}\mathbf{x}\right\rparen=1\right\rparen$
$\displaystyle\leq\Pr_{\begin{subarray}{c}f\sim D\\\ \mathbf{a}\sim D^{\prime
k}\end{subarray}}\left\lparen
f(\mathbf{a})=1\right\rparen+\theta^{2}\cdot\rho_{\min}(\mathcal{F})$
$\displaystyle\leq\rho_{\min}(\mathcal{F})\cdot\left\lparen
1+\theta^{2}\right\rparen.$ (Eq. 4.5)

∎

######  Claim 4.7.

We have:

$\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen\mathsf{val}_{\Psi^{\prime}}>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen\leq\theta^{2}.$

###### Proof.

Note that:

$\displaystyle\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen\mathsf{val}_{\Psi^{\prime}}>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen$
$\displaystyle\leq\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen\exists\mathbf{x}\in\mathbb{Z}_{q}^{n}:\mathsf{val}_{\Psi^{\prime}}(\mathbf{x})>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen$
(Eq. 2.5) $\displaystyle\leq
q^{n}\cdot\max_{\mathbf{x}\in\mathbb{Z}_{q}^{n}}\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen\mathsf{val}_{\Psi^{\prime}}(\mathbf{x})>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen$
(Union bound) $\displaystyle\leq
q^{n}\cdot\max_{\mathbf{x}\in\mathbb{Z}_{q}^{n}}\Pr_{\Psi\sim\mathcal{N}^{\mathsf{Str}}}\left\lparen\mathsf{val}_{\mathsf{Clean}(\Psi)}(\mathbf{x})>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen.$

To finish the proof, we now fix an arbitrary $\mathbf{x}\in\mathbb{Z}_{q}^{n}$
and upper bound the probability term above. We shall omit writing
$\Psi\sim\mathcal{N}^{\mathsf{Str}}$ for brevity of notation. Note that
$\mathsf{val}_{\mathsf{Clean}(\Psi)}(\mathbf{x})>\rho_{\min}(\mathcal{F})+\epsilon$
implies by our choice of $\theta$ that either $\mathsf{Clean}(\Psi)$ has at
most $\left\lparen 1-\theta^{2}\right\rparen\cdot q^{-k}\cdot\alpha Tn$
constraints or it has at least $\left\lparen
1+\theta^{2}\right\rparen\cdot\left\lparen\rho_{\min}(\mathcal{F})+\epsilon/2\right\rparen\cdot
q^{-k}\cdot\alpha Tn$ that are satisfied by $\mathbf{x}$. For all $i\in[\alpha
Tn]$, define indicator random variables $\mathsf{X}_{i}$ and $\mathsf{Y}_{i}$
such that $\mathsf{X}_{i}$ is $1$ if and only if $\mathbf{z}(i)=0^{k}$ and
$\mathsf{Y}_{i}$ is $1$ if and only if $\mathsf{X}_{i}=1$ and
$f_{i}\left\lparen M_{i}\mathbf{x}\right\rparen=1$. We get using a union
bound:

$\Pr\left\lparen\mathsf{val}_{\mathsf{Clean}(\Psi)}(\mathbf{x})>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen\leq\Pr\left\lparen\sum_{i\in[\alpha
Tn]}\mathsf{X}_{i}\leq\left\lparen 1-\theta^{2}\right\rparen\cdot
q^{-k}\cdot\alpha Tn\right\rparen\\\ +\Pr\left\lparen\sum_{i\in[\alpha
Tn]}\mathsf{Y}_{i}\geq\left\lparen
1+\theta^{2}\right\rparen\cdot\left\lparen\rho_{\min}(\mathcal{F})+\epsilon/2\right\rparen\cdot
q^{-k}\cdot\alpha Tn\right\rparen.$

It is therefore sufficient to bound the probability terms on the right. We
will do this using Chernoff bounds. We first claim that the random variables
$\mathsf{X}_{i}$ are mutually independent and so are the random variables
$\mathsf{Y}_{i}$. For this, note that both these random variables are
determined by the triple $\left\lparen f_{i},M_{i},\mathbf{z}(i)\right\rparen$
and  (1) For each $i\in[\alpha Tn]$, the triple $\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen$ is independent of $\mathbf{x}^{*}$.
This is because, in the distribution $\mathcal{N}^{\mathsf{Str}}$, the vector
sampled in Item 1d is uniform over $\mathbb{Z}_{q}^{k}$.  (2) Conditioned on
$\mathbf{x}^{*}$, the triples $\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen$ are mutually independent. This can be
observed from Definition 4.1.

Next, we analyze $\Pr\left\lparen\mathsf{X}_{i}=1\right\rparen$ and
$\Pr\left\lparen\mathsf{Y}_{i}=1\right\rparen$ for $i\in[\alpha Tn]$. For the
former, we simply observe from Item 1d that
$\Pr\left\lparen\mathsf{X}_{i}=1\right\rparen=q^{-k}$. For the latter, we have
from the definition of $\mathsf{Y}_{i}$ that:

$\displaystyle\Pr\left\lparen\mathsf{Y}_{i}=1\right\rparen$
$\displaystyle=\Pr\left\lparen f_{i}\left\lparen
M_{i}\mathbf{x}\right\rparen=1\wedge\mathbf{z}(i)=0^{k}\right\rparen$
$\displaystyle=\Pr\left\lparen f_{i}\left\lparen
M_{i}\mathbf{x}\right\rparen=1\wedge\mathbf{b}(i)=M_{i}\mathbf{x}^{*}\right\rparen$
(Item 1e) $\displaystyle=q^{-k}\cdot\Pr\left\lparen f_{i}\left\lparen
M_{i}\mathbf{x}\right\rparen=1\right\rparen$ (Item 1d) $\displaystyle\leq
q^{-k}\cdot\rho_{\min}(\mathcal{F})\cdot\left\lparen
1+\theta^{2}\right\rparen$ (Claim 4.6) $\displaystyle\leq
q^{-k}\cdot\left\lparen\rho_{\min}(\mathcal{F})+\epsilon/2\right\rparen.$
(Claim 4.6)

We can now use Chernoff bounds to get:

$\Pr\left\lparen\mathsf{val}_{\mathsf{Clean}(\Psi)}(\mathbf{x})>\rho_{\min}(\mathcal{F})+\epsilon\right\rparen\leq
2^{-\theta^{5}\cdot q^{-k}\cdot\alpha
Tn}+2^{-\theta^{5}\cdot\left\lparen\rho_{\min}(\mathcal{F})+\epsilon/2\right\rparen\cdot
q^{-k}\cdot\alpha Tn}\leq\theta^{2}\cdot q^{-n},$

by our choice of $T$ and $\theta$.

∎

Define $\mathcal{N}^{\mathsf{CSP}}_{\mathsf{good}}$ to be the same as the
distribution $\mathcal{N}^{\mathsf{CSP}}$ conditioned on the event in Claim
4.7 not happening. It follows that
$\mathsf{val}_{\Psi^{\prime}}\leq\rho_{\min}(\mathcal{F})+\epsilon$ for all
$\Psi^{\prime}$ in the support of $\mathcal{N}^{\mathsf{CSP}}_{\mathsf{good}}$
and that
$\lVert\mathcal{N}^{\mathsf{CSP}}_{\mathsf{good}}-\mathcal{N}^{\mathsf{CSP}}\rVert_{\mathrm{tv}}\leq\theta^{2}$
. Using the former, Claim 4.5, ($\star$) and 2.3, we get that there is a
deterministic streaming algorithm $\mathbf{ALG}^{\prime}$ with
$\left\lVert\mathbf{ALG}^{\prime}\right\rVert\leq\tau\cdot\sqrt{n}$ that
distinguishes between $\mathcal{Y}^{\mathsf{CSP}}$ and
$\mathcal{N}^{\mathsf{CSP}}_{\mathsf{good}}$ with advantage
$2\cdot\left\lparen p-\frac{1}{2}\right\rparen$ in the random-order streaming
model. This means that

$\left\lvert\Pr_{\Psi^{\prime}\sim\mathcal{Y}^{\mathsf{CSP}},\pi\sim\mathcal{S}\left\lparen\left\lvert\Psi^{\prime}\right\rvert\right\rparen}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\pi\left\lparen\Psi^{\prime}\right\rparen\right\rparen=1\right\rparen-\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}_{\mathsf{good}},\pi\sim\mathcal{S}\left\lparen\left\lvert\Psi^{\prime}\right\rvert\right\rparen}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\pi\left\lparen\Psi^{\prime}\right\rparen\right\rparen=1\right\rparen\right\rvert\geq
2\theta.$

Using
$\lVert\mathcal{N}^{\mathsf{CSP}}_{\mathsf{good}}-\mathcal{N}^{\mathsf{CSP}}\rVert_{\mathrm{tv}}\leq\theta^{2}$,
we get:

$\left\lvert\Pr_{\Psi^{\prime}\sim\mathcal{Y}^{\mathsf{CSP}},\pi\sim\mathcal{S}\left\lparen\left\lvert\Psi^{\prime}\right\rvert\right\rparen}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\pi\left\lparen\Psi^{\prime}\right\rparen\right\rparen=1\right\rparen-\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}},\pi\sim\mathcal{S}\left\lparen\left\lvert\Psi^{\prime}\right\rvert\right\rparen}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\pi\left\lparen\Psi^{\prime}\right\rparen\right\rparen=1\right\rparen\right\rvert\geq\theta.$

Next, use Corollary 2.2 to get:

$\left\lvert\Pr_{\Psi^{\prime}\sim\mathcal{Y}^{\mathsf{CSP}}}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\Psi^{\prime}\right\rparen=1\right\rparen-\Pr_{\Psi^{\prime}\sim\mathcal{N}^{\mathsf{CSP}}}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\Psi^{\prime}\right\rparen=1\right\rparen\right\rvert\geq\theta.$

By definition of $\mathcal{Y}^{\mathsf{CSP}},\mathcal{N}^{\mathsf{CSP}}$, we
have:

$\left\lvert\Pr_{\Psi\sim\mathcal{Y}^{\mathsf{Str}}}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\mathsf{Clean}\left\lparen\Psi\right\rparen\right\rparen=1\right\rparen-\Pr_{\Psi\sim\mathcal{N}^{\mathsf{Str}}}\left\lparen\mathbf{ALG}^{\prime}\left\lparen\mathsf{Clean}\left\lparen\Psi\right\rparen\right\rparen=1\right\rparen\right\rvert\geq\theta.$

Now consider a streaming algorithm $\mathbf{ALG}$ for the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha
T}(n)$ problem that goes over all triples $\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen$ for $i\in[\alpha Tn]$, and applies
$\mathbf{ALG}^{\prime}$ on the triples for which $\mathbf{z}(i)=0^{k}$. By
definition of $\mathbf{ALG}$, we have

$\left\lvert\Pr_{\Psi\sim\mathcal{Y}^{\mathsf{Str}}}\left\lparen\mathbf{ALG}\left\lparen\Psi\right\rparen=1\right\rparen-\Pr_{\Psi\sim\mathcal{N}^{\mathsf{Str}}}\left\lparen\mathbf{ALG}\left\lparen\Psi\right\rparen=1\right\rparen\right\rvert\geq\theta.$
(4.8)

##### Protocol for $\mathsf{Generalized\text{-}Uniform\text{-}RMD}$.

We now use our algorithm $\mathbf{ALG}$ to define a (randomized) protocol
$\mathsf{\Pi}$ that solves the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem
with advantage $\delta\cdot\alpha$ and satisfies
$\left\lVert\mathsf{\Pi}\right\rVert\leq\tau\cdot\sqrt{n})$. To start, note
that Eq. 4.8 together with the fact that
$\mathsf{Hyb}^{\mathsf{Str}}(0)=\mathcal{Y}^{\mathsf{Str}}$ and
$\mathsf{Hyb}^{\mathsf{Str}}(T)=\mathcal{N}^{\mathsf{Str}}$ and the triangle
inequality, implies there exists a $t\in[T]$ such that

$\left\lvert\Pr_{\Psi\sim\mathsf{Hyb}^{\mathsf{Str}}(t)}\left\lparen\mathbf{ALG}\left\lparen\Psi\right\rparen=1\right\rparen-\Pr_{\Psi\sim\mathsf{Hyb}^{\mathsf{Str}}(t-1)}\left\lparen\mathbf{ALG}\left\lparen\Psi\right\rparen=1\right\rparen\right\rvert\geq\frac{\theta}{T}\geq\delta\cdot\alpha.$
(4.9)

Fix such a $t$ and using it to define a $\mathsf{\Pi}$ for the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem
as in Algorithm 5. Recall from Section 2.1.1 that notation
$\mathbf{ALG}(\sigma,t)$ to denote the state of the streaming algorithm
$\mathbf{ALG}$ on input $\sigma$ after it has processed $t$ symbols from the
stream.

Algorithm 5 The protocol $\mathsf{\Pi}$ for the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem.

1:Alice’s input is a vector $\mathbf{x}^{*}\in\mathbb{Z}_{q}^{n}$. Bob’s input
is a triple $\left\lparen M,\mathbf{z},\mathbf{D}\right\rparen$ as in
Definition 4.1.

2: Sampling phase:

3:Alice samples an instance $\Psi^{A}$ from the yes distribution of the
streaming version of
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha(t-1)}(n)$
conditioned on the value $\mathbf{x}^{*}$.

4:Bob uses his input to construct $\Psi^{B,1}=\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen_{i\in[\alpha n]}$. Next, he samples an
instance $\Psi^{B,2}$ from the no distribution of the streaming version of
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha(T-t)}(n)$.
He appends this to $\Psi^{B,1}$ to get an instance
$\Psi^{B}=\left\lparen\Psi^{B,1},\Psi^{B,2}\right\rparen$.

5: Communication phase:

6:Alice and Bob together run $\mathbf{ALG}$ on the instance
$\left\lparen\Psi^{A},\Psi^{B}\right\rparen$ as follows:

  1. (a)

Alice runs $\mathbf{ALG}$ on $\Psi^{A}$, and sends the final state
$\mathbf{ALG}\left\lparen\Psi^{A},\alpha(t-1)n\right\rparen$ to Bob.

  2. (b)

Bob receives a message $M$ from Alice, and runs $\mathbf{ALG}$ on $\Psi^{B}$
starting from the state $M$ and outputting what $\mathbf{ALG}$ outputs.

We now analyze the protocol $\mathsf{\Pi}$ and show that it solves the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem
with advantage $\delta\cdot\alpha$. For an input
$\Phi=\left\lparen\mathbf{x}^{*},\left\lparen
M,\mathbf{z},\mathbf{D}\right\rparen\right\rparen$ to the parties in the
protocol $\mathsf{\Pi}$, we define $\Psi^{A}(\Phi)$ to be the random variable
(over Alice’s randomness in $\mathsf{\Pi}$) that equals the instance sampled
by Alice in Line 3. Similarly, we define $\Psi^{B}(\Phi)$ to be the random
variable (over Bob’s randomness in $\mathsf{\Pi}$) that equals the instance
sampled by Bob in Line 4. Let $\mathcal{Y}^{\mathsf{CC}}$ and
$\mathcal{N}^{\mathsf{CC}}$ be the yes and no distributions in the
communication version of
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$.
We show that:

######  Lemma 4.10.

It holds for all instances $\Psi^{\prime}$ that:

$\displaystyle\Pr_{\Psi\sim\mathsf{Hyb}^{\mathsf{Str}}(t)}\left\lparen\Psi=\Psi^{\prime}\right\rparen$
$\displaystyle=\Pr_{\begin{subarray}{c}\Phi\sim\mathcal{Y}^{\mathsf{CC}}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\left\lparen\Psi^{A}(\Phi),\Psi^{B}(\Phi)\right\rparen=\Psi^{\prime}\right\rparen.$
$\displaystyle\Pr_{\Psi\sim\mathsf{Hyb}^{\mathsf{Str}}(t-1)}\left\lparen\Psi=\Psi^{\prime}\right\rparen$
$\displaystyle=\Pr_{\begin{subarray}{c}\Phi\sim\mathcal{N}^{\mathsf{CC}}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\left\lparen\Psi^{A}(\Phi),\Psi^{B}(\Phi)\right\rparen=\Psi^{\prime}\right\rparen.$

Before proving Lemma 4.10, we use it to finish the proof of Theorem 4.4 by
showing that $\mathsf{\Pi}$ solves the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{\mathcal{F},\mathcal{D}_{Y},\alpha}(n)$-problem
with advantage $\delta\cdot\alpha$. As Line 6 simply runs $\mathbf{ALG}$ on
the sampled instance $\left\lparen\Psi^{A}(\Phi),\Psi^{B}(\Phi)\right\rparen$,
we have:

$\displaystyle\delta\cdot\alpha$
$\displaystyle\leq\left\lvert\Pr_{\Psi\sim\mathsf{Hyb}^{\mathsf{Str}}(t)}\left\lparen\mathbf{ALG}\left\lparen\Psi\right\rparen=1\right\rparen-\Pr_{\Psi\sim\mathsf{Hyb}^{\mathsf{Str}}(t-1)}\left\lparen\mathbf{ALG}\left\lparen\Psi\right\rparen=1\right\rparen\right\rvert$
(Eq. 4.9)
$\displaystyle=\left\lvert\Pr_{\begin{subarray}{c}\Phi\sim\mathcal{Y}^{\mathsf{CC}}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\mathbf{ALG}\left\lparen\left\lparen\Psi^{A}(\Phi),\Psi^{B}(\Phi)\right\rparen\right\rparen=1\right\rparen-\Pr_{\begin{subarray}{c}\Phi\sim\mathcal{N}^{\mathsf{CC}}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\mathbf{ALG}\left\lparen\left\lparen\Psi^{A}(\Phi),\Psi^{B}(\Phi)\right\rparen\right\rparen=1\right\rparen\right\rvert$
(Lemma 4.10)
$\displaystyle=\left\lvert\Pr_{\begin{subarray}{c}\Phi\sim\mathcal{Y}^{\mathsf{CC}}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\Pi\left\lparen\Phi\right\rparen=1\right\rparen-\Pr_{\begin{subarray}{c}\Phi\sim\mathcal{N}^{\mathsf{CC}}\\\
\Pi\sim\mathsf{\Pi}\end{subarray}}\left\lparen\Pi\left\lparen\Phi\right\rparen=1\right\rparen\right\rvert,$

as desired. We now show Lemma 4.10.

###### Proof of Lemma 4.10.

We only show the first statement as the proof for the second one is analogous.
Let $\mathsf{Hyb}^{\mathsf{CC}}$ be the distribution obtained by first
sampling a $\Phi\sim\mathcal{Y}^{\mathsf{CC}}$ and then outputting
$\left\lparen\mathbf{x}^{*},\Psi^{A}(\Phi),\Psi^{B}(\Phi)\right\rparen$ as in
the protocol $\mathsf{\Pi}$. Viewing $\mathsf{Hyb}^{\mathsf{Str}}(t)$ as a
distribution over $\left\lparen\mathbf{x}^{*},\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen_{i\in[\alpha Tn]}\right\rparen$ as in
Definition 4.1, we shall show the stronger statement that the distributions
$\mathsf{Hyb}^{\mathsf{CC}}$ and $\mathsf{Hyb}^{\mathsf{Str}}(t)$ are the
same. We do this in steps.

##### The marginal distribution of $\mathbf{x}^{*}$ is the same.

We first show that the marginal distribution of $\mathbf{x}^{*}$ is the same
in both distributions. This is because by Definition 4.1,
$\mathbf{x}^{*}\in\mathbb{Z}_{q}^{n}$ is uniformly random in both cases.

##### Conditioned on $\mathbf{x}^{*}$, the marginals $\left\\{\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen\right\\}_{i\in[\alpha Tn]}$ are
mutually independent.

For the case of $\mathsf{Hyb}^{\mathsf{Str}}(t)$, this follows immediately
from Definition 4.1. Thus, we only analyze the case of
$\mathsf{Hyb}^{\mathsf{CC}}$. In this case, note first from Lines 3 and 4 that
conditioned on $\mathbf{x}^{*}$ the three marginals corresponding to:

$\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen_{0<i\leq\alpha(t-1)n}\hskip
35.56593pt\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen_{\alpha(t-1)n<i\leq\alpha tn}\hskip
35.56593pt\left\lparen f_{i},M_{i},\mathbf{z}(i)\right\rparen_{\alpha
tn<i\leq\alpha Tn},$

are mutually independent. This is because conditioned on $\mathbf{x}^{*}$, the
second vector above is Bob’s input in $\mathsf{\Pi}$ that Alice does not need
to see to sample the first vector in Line 3, and also because the third vector
is what Bob samples in Line 4, for which he does not need to see anything
(including his input). Thus, it is enough to show that the marginal
distribution of all the coordinates in each of the three vectors above are
mutually independent conditioned on $\mathbf{x}^{*}$.

For the first two vectors, this is because of Definition 4.1. For the third
vector, this is also because of Definition 4.1 and the fact that in the no
distribution of $\mathsf{Generalized\text{-}Uniform\text{-}RMD}$, the triples
$\left\lparen f_{i},M_{i},\mathbf{z}(i)\right\rparen$ are independent and
identically distributed.

##### For all $i\in[\alpha Tn]$, the marginal distribution of $\left\lparen
f_{i},M_{i},\mathbf{z}(i)\right\rparen$ conditioned on $\mathbf{x}^{*}$ is the
same.

For $0<i\leq\alpha(t-1)n$, this is because of the way Alice samples her
$\Psi^{A}$ in Line 3. For $\alpha(t-1)n<i\leq\alpha tn$, this is by definition
of $\mathcal{Y}^{\mathsf{CC}}$. For $\alpha tn<i\leq\alpha Tn$, this is
because of the way Bob samples his $\Psi^{B,2}$ in Line 4. Note that in this
case as $\mathbf{b}(i)$ is chosen uniformly from $\mathbb{Z}_{q}^{k}$, the
marginal distribution is actually independent of $\mathbf{x}^{*}$.

∎

∎

##  5 Proof of Theorem 4.3

In this section we prove that the
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}$ communication problem arising
from $\left\lparen\mathcal{F},\mathcal{D}_{Y}\right\rparen$ cannot be solved
with non-trivial advantage using $o(\sqrt{n})$ communication. The central
element in the proof is to look at the distribution of Bob’s input
$\mathbf{z}$ conditioned on Alice’s message and the matrix $M$, and to argue
that the distributions are close in the YES and NO cases. By definition, the
distribution in the NO case is uniform over $\mathbb{Z}_{q}^{km}$ and so what
needs to be really shown is that in the YES case also this distribution is
close to uniform.

Note that Alice’s message specifies a set $A\subseteq\mathbb{Z}_{q}^{n}$ such
that $\mathbf{x}^{*}\sim\textsf{Unif}(A)$. Lemma 5.2 roughly relates the
distance of the conditional distribution of $\mathbf{z}$ (in the YES case) to
the Fourier spectrum of the indicator of the set $A$ and to a somewhat complex
combinatorial parameter associated with the random hypergraph described by $M$
(see Eq. 5.1). More precisely Lemma 5.2 bounds this distance provided $M$ is
“cycle-free” according to a natural notion of cycle-freeness for hypergraphs
that we introduce below. We then state two lemmas upper-bounding the
expectation of the combinatorial parameter (Lemma 5.3) and the probability of
a cycle (Lemma 5.4), whose proofs are deferred to Section 6. We use these
bounds to complete the proof of Theorem 4.3.

The proof outline described above follows the same structure as that of
[KKS15] with two significant differences. First, the definition of cycle-
freeness is different in our work and this difference has a quantitative
effect in that the probability of being cycle-free increases to
$\Theta(\alpha^{2})$ in our setting compared to $\Theta(\alpha^{3})$ in their
work. This difference is significant in the context of “non-trivial
advantage”. Directly following the proof in [KKS15] would have led to a
$\Theta(\alpha)$ advantage and we make some changes in the proof of Theorem
4.3 to show that despite the higher probability of cycle-freeness, protocols
with non-trivial advantage require $\Omega(\sqrt{n})$ communication. The
second difference is in the combinatorial quantity of interest which sees
differences due to the higher values of $k$ and $q$, and the richness of the
distributions $\mathcal{D}_{Y}$ that we need to handle. The analysis of the
combinatorial quantity is also more complex and we describe the differences in
the next section.

###  5.1 Indististinguishability via Fourier Analysis

Conditioned on a set $A\subset\mathbb{Z}_{q}^{n}$ of $\mathbf{x}^{*}$’s
corresponding to an $\mathsf{Alice}$ message, a $k$-hypergraph
$M\in\\{0,1\\}^{k\alpha n\times n}$, and a vector
$\mathbf{D}=((f_{1},D_{1}),\ldots,(f_{m},D_{m}))\in(\mathcal{F}\times{\Delta_{\mathsf{unif}}}(\mathbb{Z}_{q}^{k}))^{m}$,
let $\mathcal{Z}_{A,M,\mathbf{D}}\in\Delta(\mathbb{Z}_{q}^{k\alpha n})$ denote
the conditional distribution of $\mathsf{Bob}$’s input $\mathbf{z}$ in the YES
case, i.e.,

$\mathcal{Z}_{A,M,\mathbf{D}}(\mathbf{z})=\Pr_{\mathbf{x}^{*}\sim\mathcal{U}(A),\mathbf{b}\sim
D_{1}\times\cdots\times D_{m}}[\mathbf{z}=M\mathbf{x}^{*}-\mathbf{b}].$

For a $k$-hypergraph $G$, let $\mathsf{cf}(G)$ denote the event that $G$ is
_cycle-free_ in the sense that its point-hyperplane incidence graph $B_{G}$
contains no cycles. Let $S_{\neq 1}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\\{\mathbf{s}\in(\mathbb{Z}_{q}^{k})^{\alpha n}:\forall i\in[\alpha
n],\|\mathbf{s}(i)\|_{0}\neq 1\\}$. Then for $\ell\in[n]$, we define the
quantity

$h_{k,\alpha}(\ell,n)\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\max_{\mathbf{v}\in\mathbb{Z}_{q}^{n},\|\mathbf{v}\|_{0}=\ell}\left(\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}\left[\mathbbm{1}_{\mathsf{cf}(M)}\cdot\left\lvert\left\\{\mathbf{s}\in
S_{\neq 1}:M^{\top}\mathbf{s}=\mathbf{v}\right\\}\right\rvert\right]\right).$
(5.1)

######  Lemma 5.2 (Fourier-analytic reduction).

Fix $n\in\mathbb{N}$, $\alpha\in(0,1/100k)$, and a vector

$\mathbf{D}=((f_{1},D_{1}),\ldots,(f_{m},D_{M}))\in(\mathcal{F}\times{\Delta_{\mathsf{unif}}}(\mathbb{Z}_{q}^{k}))^{m}.$

Then

$\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}[\mathbbm{1}_{\mathsf{cf}(M)}\cdot\|\mathcal{Z}_{A,M,\mathbf{D}}-\mathcal{U}(\mathbb{Z}_{q}^{k\alpha
n})\|_{\mathrm{tv}}^{2}]\leq\frac{q^{2n}}{|A|^{2}}\sum_{\ell=1}^{k\alpha
n}h_{k,\alpha}(\ell,n)\mathsf{W}^{\ell}[\mathbbm{1}_{A}]$

where $h_{k,\alpha}(\ell,n)$ is defined as in Eq. 5.1.

###### Proof.

Fix $\mathbf{s}\neq\mathbf{0}\in\mathbb{Z}_{q}^{\alpha kn}$ and let
$D=D_{1}\times\cdots\times D_{m}$. We have

$\displaystyle\widehat{\mathcal{Z}_{A,M,\mathbf{D}}}(\mathbf{s})$
$\displaystyle=\frac{1}{q^{\alpha
kn}}\sum_{\mathbf{z}\in\mathbb{Z}_{q}^{k\alpha
n}}\mathcal{Z}_{A,M,\mathbf{D}}(\mathbf{z})\,\omega^{-\mathbf{s}\cdot\mathbf{z}}$
(definition of $\widehat{\mathcal{Z}_{A,M,\mathbf{D}}}$)
$\displaystyle=\frac{1}{q^{\alpha
kn}}\sum_{\mathbf{z}\in\mathbb{Z}_{q}^{k\alpha
n}}\left(\mathop{\mathbb{E}}_{\mathbf{x}^{*}\sim A,\mathbf{b}\sim
D}[\mathbbm{1}_{\mathbf{z}=M\mathbf{x}^{*}-\mathbf{b}}]\right)\omega^{-\mathbf{s}\cdot\mathbf{z}}$
(definition of $\mathcal{Z}_{A,M,\mathbf{D}}$)
$\displaystyle=\frac{1}{q^{\alpha kn}}\mathop{\mathbb{E}}_{\mathbf{x}^{*}\sim
A,\mathbf{b}\sim D}[\omega^{-\mathbf{s}\cdot(M\mathbf{x}^{*}-\mathbf{b})}]$
(linearity of expectation) $\displaystyle=\frac{1}{q^{\alpha
kn}}\left(\mathop{\mathbb{E}}_{\mathbf{x}^{*}\sim
A}[\omega^{-\mathbf{s}\cdot(M\mathbf{x}^{*})}]\right)\left(\prod_{i=1}^{\alpha
n}\left(\mathop{\mathbb{E}}_{\mathbf{b}(i)\sim
D_{i}}[\omega^{\mathbf{s}(i)\cdot\mathbf{b}(i)}]\right)\right).$ (independence
and linearity)

Now if $\mathbf{s}\not\in S_{\neq 1}$, there exists $i$ such that
$\|\mathbf{s}(i)\|_{0}=1$, so for some $j\in[k]$, $s(i)_{j}\neq 0$ while
$s(i)_{j^{\prime}}=0$ for all $j^{\prime}\neq j$. Thus, we have
$\mathop{\mathbb{E}}_{\mathbf{b}(i)\sim
D_{i}}[\omega^{\mathbf{s}(i)\cdot\mathbf{b}(i)}]=\omega^{s(i)_{j}}\mathop{\mathbb{E}}_{\mathbf{b}(i)\sim
D_{i}}[\omega^{b(i)_{j}}]=0$ because $b(i)_{j}$ is uniformly distributed on
$\mathbb{Z}_{q}$ by one-wise independence of $D_{i}$, and so
$\widehat{\mathcal{Z}_{A,M,\mathbf{D}}}(\mathbf{s})=0$. Otherwise, using the
trivial upper bound $\left|\mathop{\mathbb{E}}_{\mathbf{b}(i)\sim
D_{i}}[\omega^{\mathbf{s}(i)\cdot\mathbf{b}(i)}]\right|\leq 1$, we have

$\displaystyle|\widehat{\mathcal{Z}_{A,M,\mathbf{D}}}(\mathbf{s})|$
$\displaystyle\leq\frac{1}{q^{k\alpha
n}}\left|\mathop{\mathbb{E}}_{\mathbf{x}^{*}\sim
A}[\omega^{-\mathbf{s}\cdot(M\mathbf{x}^{*})}]\right|$
$\displaystyle=\frac{1}{q^{k\alpha
n}}\left|\mathop{\mathbb{E}}_{\mathbf{x}^{*}\sim
A}[\omega^{-(M^{\top}\mathbf{s})\cdot\mathbf{x}^{*}}]\right|$ (adjointness)
$\displaystyle=\frac{q^{n}}{q^{\alpha
kn}|A|}|\widehat{\mathbbm{1}_{A}}(M^{\top}\mathbf{s})|.$ (definition of
$\widehat{\mathbbm{1}_{A}}$)

Thus, by Lemma 2.15 and taking expectation over $M$, we have

$\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}[\mathbbm{1}_{\mathsf{cf}(M)}\cdot\|\mathcal{Z}_{A,M,\mathbf{D}}-\mathcal{U}(\mathbb{Z}_{q}^{m})\|_{\mathrm{tv}}^{2}]\leq\frac{q^{2n}}{|A|^{2}}\sum_{\mathbf{s}\neq\mathbf{0}\in
S_{\neq
1}}\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}[|\widehat{\mathbbm{1}_{A}}(M^{\top}\mathbf{s})|^{2}].$

Rewriting as a sum over $\mathbf{v}=M^{\top}\mathbf{s}$ gives exactly the
desired inequality. ∎

###  5.2 Properties of random hypergraphs

Now we state two lemmas about the distribution $\mathcal{G}_{k,\alpha}(n)$
which we will prove in Section 6 below:

######  Lemma 5.3.

For all $2\leq q,k\in\mathbb{N}$, there exists $c_{h}<\infty$ and
$\alpha_{0}>0$ such that for all $\alpha\in(0,\alpha_{0})$,

$h_{k,\alpha}(\ell,n)\leq\left(\frac{c_{h}\ell}{n}\right)^{\ell/2}.$

######  Lemma 5.4.

For every $k\geq 2$, there exists $c_{\mathsf{cf}}<\infty$ and
$\alpha_{0}\in(0,1)$ such that for all $n\geq k$ and
$\alpha\in(0,\alpha_{0})$,

$\Pr_{G\sim\mathcal{G}_{k,\alpha}(n)}[\neg\mathsf{cf}(G)]\leq c\alpha^{2}.$

###  5.3 Putting the ingredients together

Modulo these lemmas, we can now prove Theorem 4.3:

###### Proof of Theorem 4.3.

Suppose $\mathsf{Alice}$ and $\mathsf{Bob}$ use a one-way communication
protocol $\Pi$ for
$\mathsf{Generalized\text{-}Uniform\text{-}RMD}_{q,k,\mathcal{F},\mathcal{D}_{Y},\alpha}$
which uses at most $s=\tau\sqrt{n}$ communication and achieves advantage
greater than $\alpha\delta$, where $\tau$ is a constant to be determined
later. By Yao’s principle [Yao77], we may assume WLOG that $\Pi$ is
deterministic and that, from $\mathsf{Bob}$’s perspective, $\mathsf{Alice}$’s
message partitions the set of possible $\mathbf{x}^{*}$’s into sets
$\\{A_{i}\subseteq\mathbb{Z}_{q}^{n}\\}_{i\in[2^{s}]}$.

Conditioned on a fixed set $A\subseteq\mathbb{Z}_{q}^{n}$, we can view
$\mathsf{Bob}$’s input $(M,\mathbf{z},\mathbf{D})$ in both the YES and NO
cases as being sampled by the following process: We sample
$M\sim\mathcal{G}_{k,\alpha}(n)$ and $\mathbf{D}\sim\mathcal{D}_{Y}^{\alpha
n}$, and then sample $\mathbf{z}$ either uniformly from
$\mathcal{U}(\mathbb{Z}_{q}^{k\alpha n})$ in the NO case or from the
conditional distribution $\mathcal{Z}_{A,M,\mathbf{D}}$ in the YES case. Thus,
$\Pi$ achieves advantage at most

$\delta_{A}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n),\mathbf{D}\sim\mathcal{D}_{Y}^{\alpha
n}}[\|\mathcal{Z}_{A,M,\mathbf{D}}-\mathcal{U}(\mathbb{Z}_{q}^{k\alpha
n})\|_{\mathrm{tv}}].$

Letting $\mathcal{A}$ denote the distribution which samples each $A_{i}$ w.p.
$|A_{i}|/q^{n}$, we have

$\alpha\delta\leq\mathop{\mathbb{E}}_{A\sim\mathcal{A}}[\delta_{A}].$ (5.5)

Our goal is to contradict Eq. 5.5 for a sufficiently small choice of $\tau$.
We set $\tau=2\tau^{\prime}$, where $\tau^{\prime}>0$ is to be determined
later, and let $s^{\prime}=\tau^{\prime}\sqrt{n}$. Also, let
$\delta^{\prime}=\frac{\alpha\delta}{2}$, and let $\alpha_{0}$ be the minimum
of $\frac{\delta}{2c_{\mathsf{cf}}}$ and the $\alpha_{0}$’s from Lemmas 5.4
and 5.3. Since $\alpha\leq\alpha_{0}$, we have
$c_{\mathsf{cf}}\alpha^{2}+\delta^{\prime}\leq\alpha\delta$, so Eq. 5.5
implies

$c_{\mathsf{cf}}\alpha^{2}+\delta^{\prime}\leq\mathop{\mathbb{E}}_{A\sim\mathcal{A}}[\delta_{A}].$
(5.6)

A “typical” $A\sim\mathcal{A}$ is large, so to contradict Eq. 5.6, we want to
show that $\delta_{A}$ is small for large $A$. Indeed, since
$s^{\prime}<s-\log_{q}(2/\delta^{\prime})$ (for sufficiently large $n$), we
have $\Pr_{A\sim\mathcal{A}}[|A|\leq
q^{n-s^{\prime}}]\leq\frac{\delta^{\prime}}{2}$, and it therefore suffices to
prove that if $|A|\geq q^{n-s^{\prime}}$, then $\delta_{A}\leq
c\alpha^{2}+\frac{\delta^{\prime}}{2}$.

Let $A\subseteq\mathbb{Z}_{q}^{n}$ with $|A|\geq q^{n-s^{\prime}}$.
Conditioning on $\mathsf{cf}(M)$ and using Jensen’s inequality and Lemma 5.4,
we have

$\displaystyle\delta_{A}$
$\displaystyle\leq\Pr[\neg\mathsf{cf}(M)]+\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}[\mathbbm{1}_{\mathsf{cf}(M)}\cdot\|\mathcal{Z}_{A,M,\mathbf{D}}-\mathcal{U}(\mathbb{Z}_{q}^{k\alpha
n})\|_{\mathrm{tv}}]$ $\displaystyle\leq
c_{\mathsf{cf}}\alpha^{2}+\sqrt{\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}[\mathbbm{1}_{\mathsf{cf}(M)}\cdot\|\mathcal{Z}_{A,M,\mathbf{D}}-\mathcal{U}(\mathbb{Z}_{q}^{k\alpha
n})\|_{\mathrm{tv}}^{2}]}.$ (5.7)

Now we apply Lemma 5.2:

$\displaystyle\mathop{\mathbb{E}}_{M\sim\mathcal{G}_{k,\alpha}(n)}[\mathbbm{1}_{\mathsf{cf}(M)}\cdot\|\mathcal{Z}_{A,M,\mathbf{D}}-\mathcal{U}(\mathbb{Z}_{q}^{k\alpha
n})\|_{\mathrm{tv}}^{2}]$
$\displaystyle\leq\frac{q^{2n}}{|A|^{2}}\sum_{\ell=1}^{k\alpha
n}h_{k,\alpha}(\ell,n)\mathsf{W}^{\ell}[\mathbbm{1}_{A}]$ We split the sum at
$\ell=4s^{\prime}$, using Lemma 2.14 for the first term and Parseval’s
identity (Proposition 2.13) for the second:
$\displaystyle=\frac{q^{2n}}{|A|^{2}}\sum_{\ell=1}^{4s^{\prime}}h_{k,\alpha}(\ell,n)\mathsf{W}^{\ell}[\mathbbm{1}_{A}]+\frac{q^{2n}}{|A|^{2}}\sum_{\ell=4s^{\prime}}^{k\alpha
n}h_{k,\alpha}(\ell,n)\mathsf{W}^{\ell}[\mathbbm{1}_{A}]$
$\displaystyle\leq\sum_{\ell=1}^{4s^{\prime}}h_{k,\alpha}(\ell,n)\left(\frac{\zeta
s^{\prime}}{\ell}\right)^{\ell}+\frac{q^{2n}}{|A|^{2}}\max_{4s^{\prime}\leq\ell\leq
k\alpha n}h_{k,\alpha}(\ell,n)$ Since $|A|\geq q^{n-s^{\prime}}$ and
$s^{\prime}=\tau^{\prime}\sqrt{n}$:
$\displaystyle\leq\sum_{\ell=1}^{4s^{\prime}}h_{k,\alpha}(\ell,n)\left(\frac{\zeta\tau^{\prime}\sqrt{n}}{\ell}\right)^{\ell}+q^{2s^{\prime}}\max_{4s^{\prime}\leq\ell\leq