# Noisy Boolean Hidden Matching with Applications

Michael Kapralov School of Computer and Communication Sciences, EPFL. E-mail:
<EMAIL_ADDRESS>Amulya Musipatla School of Computer Science, Carnegie
Mellon University. E-mail<EMAIL_ADDRESS>Jakab Tardos School of
Computer and Communication Sciences, EPFL. E-mail<EMAIL_ADDRESS>David
P. Woodruff School of Computer Science, Carnegie Mellon University. E-mail:
<EMAIL_ADDRESS>Samson Zhou School of Computer Science, Carnegie Mellon
University. E-mail<EMAIL_ADDRESS>
###### Abstract

The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of
Gavinsky et. al. [STOC’07], has played an important role in the streaming
lower bounds for graph problems such as triangle and subgraph counting,
maximum matching, MAX-CUT, Schatten $p$-norm approximation, maximum acyclic
subgraph, testing bipartiteness, $k$-connectivity, and cycle-freeness. The
one-way communication complexity of the Boolean Hidden Matching problem on a
universe of size $n$ is $\Theta(\sqrt{n})$, resulting in $\Omega(\sqrt{n})$
lower bounds for constant factor approximations to several of the
aforementioned graph problems. The related (and, in fact, more general)
Boolean Hidden Hypermatching (BHH) problem introduced by Verbin and Yu
[SODA’11] provides an approach to proving higher lower bounds of
$\Omega(n^{1-1/t})$ for integer $t\geq 2$. Reductions based on Boolean Hidden
Hypermatching generate distributions on graphs with connected components of
diameter about $t$, and basically show that long range exploration is hard in
the streaming model of computation with adversarial arrivals.

In this paper we introduce a natural variant of the BHM problem, called noisy
BHM (and its natural noisy BHH variant), that we use to obtain higher than
$\Omega(\sqrt{n})$ lower bounds for approximating several of the
aforementioned problems in graph streams when the input graphs consist only of
components of diameter bounded by a fixed constant. We also use the noisy BHM
problem to show that the problem of classifying whether an underlying graph is
isomorphic to a complete binary tree in insertion-only streams requires
$\Omega(n)$ space, which seems challenging to show using BHM or BHH alone.

##  1 Introduction

The _streaming model_ of computation has emerged as a popular model for
processing large datasets. In _insertion-only_ streams, sequential updates to
an underlying dataset arrive over time and are permanent, while in _dynamic_
or _turnstile_ streams, the sequential updates to the dataset may be
subsequently reversed by future updates. As many modern large datasets are
most naturally represented by graphs (e.g., social networks, protein
interaction networks, or communication graphs in network monitoring) there has
been a substantial amount of recent interest in graph algorithms on data
streams, both on insertion-only streams, e.g., [FKM+05, FKM+08, VY11, Kap13,
KKS14, CS14, KKS15, PS17, BGM+19] and dynamic streams, e.g., [AGM12a, AGM12b,
KW14, BHNT15, AKLY16, CCHM15, CCE+16, KLM+17, NY19].

The Boolean Hidden Matching (BHM) problem [KR06, GKdW06, BJK08, GKK+08] is an
important problem in communication complexity that has been a major tool for
showing hardness of approximation in the streaming model for a variety of
graph problems, such as triangle counting [KP17, KKP18], maximum matching
[AKL17, EHL+18, BGM+19], MAX-CUT [KKS15, KK15, KKSV17], and maximum acyclic
subgraph [GVV17]. In this problem, Alice is given a binary vector $x$ of
length $n$ and Bob is given a matching $M$ on $[n]=\\{1,2,\ldots,n\\}$ of size
$\alpha n/2$ for a small positive constant $\alpha\leq 1$, as well as a binary
vector $w$ of length $\alpha n/2$ of labels for the edges of $M$. Under the
promise that either $Mx\oplus w=0^{\alpha n/2}$ or $Mx\oplus w=1^{\alpha
n/2}$, the goal is for Alice to send a message of minimal length, so that Bob
can determine which of the two cases holds, with probability at least
$\frac{2}{3}$. Here, and in the rest of the paper, we use $M$ to denote both
the matching and its edge incidence matrix, so that $Mx$ is a vector indexed
by edges $e=(u,v)\in M$ such that $(Mx)_{e}=x_{u}\oplus x_{v}$.

Observe that if Bob determines the parity $(Mx)_{e}$ of any edge $e$ in the
matching, then Bob can check whether $(Mx)_{e}\oplus w_{e}=0$ or
$(Mx)_{e}\oplus w_{e}=1$. Thus, it suffices for Alice to send the parities of
enough vertices so that with probability at least $\frac{2}{3}$, the parities
of both vertices of some edge are revealed to Bob. Through a straightforward
birthday paradox argument, it follows that ${O}\left(\sqrt{n}\right)$
communication suffices. [KR06, GKdW06, GKK+08] showed that this plain text
protocol is essentially tight:

###### Theorem 1.1

[KR06, GKdW06, GKK+08] Any randomized one-way protocol for the Boolean Hidden
Matching problem that succeeds with probability at least $\frac{2}{3}$
requires $\Omega(\sqrt{n})$ bits of communication.

One of the main weaknesses of the Boolean Hidden Matching problem is that its
$\Omega(\sqrt{n})$ communication complexity is not strong enough to
characterize the complexity of more difficult problems.

To address this shortcoming, Verbin and Yu proposed the Boolean Hidden
Hypermatching problem (BHH) [VY11], in which Alice is given a binary vector
$x$ of length $n=kt$ and Bob is given a hypermatching $M$ on $[n]$ in which
all hyperedges contain $t$ vertices, as well as a binary vector $w$ of length
$k$. Under the promise that either $Mx\oplus w=0^{k}$ or $Mx\oplus w=1^{k}$,
the goal is for Alice to send some message of minimal length, so that Bob can
determine which of the two cases holds, with probability at least
$\frac{2}{3}$. Whereas BHM has complexity $\Omega(\sqrt{n})$, [VY11] showed
that BHH has complexity $\Omega(n^{1-1/t})$:

###### Theorem 1.2

[VY11] Any randomized protocol that succeeds with probability at least
$\frac{2}{3}$ for the Boolean Hidden Hypermatching problem with hyperedges
that contain $t$ vertices requires Alice to send $\Omega(n^{1-1/t})$ bits of
communication.

Boolean Hidden Hypermatching has been used to show stronger lower bounds for
cycle counting [VY11], maximum matching [AKL17, EHL+18, BGM+19], Schatten
$p$-norm approximation [LW16], testing biconnectivity, cycle-freeness and
bipartiteness [HP19], MAX-CUT [KKS15, KK15, KKSV17]. The hard distributions on
input graphs that are generated by these reductions typically produce a union
of connected components of diameter $\Theta(t)$, where distinguishing between
the YES and NO cases of the input distribution intuitively requires exploring
rather long paths (of length comparable to the diameter of these components).
In this work we give higher than $\Omega(\sqrt{n})$ lower bounds that at the
same time generate graphs with connected components of bounded diameter, and
therefore exploit a different source of hardness (similarly, we prove higher
than $\Omega(n^{1-1/t})$ lower bounds for several of the above problems on
graphs with components of diameter bounded by $O(t)$).

In particular, we note that a major weakness of BHH is that this problem only
yields lower bounds of $\Omega(n)$ when hyperedge size satisfies
$t=\Omega(\log n)$. Consequently in the resulting reductions, quantities such
as the diameter of the graph or the size of the largest clique often also grow
as $\Omega(\log n)$, which prevents the usage of BHH in showing hardness of
approximation for specific classes of graphs, such as graphs with bounded
diameter or bounded clique number.

###  1.1 Our Contributions

We first introduce a natural parametrization of BHM/BHH.

######  Definition 1.3 (Noisy Boolean Hidden Matching)

The $p$-Noisy Boolean Hidden Matching problem is a two party communication
problem, with parameters $p\in[0,1]$, $\alpha\in(0,1]$, and $n$.

  * •

Alice receives a binary string $x\in\\{0,1\\}^{n}$ of length $n$.

  * •

Bob receives a matching $M$ of size $\alpha n/2$ on $[n]$, as well as a binary
vector of labels of length $\alpha n/2$. In the YES instance Bob’s labels are
the true parities of the matching edges, that is $Mx$. In the NO instance
Bob’s labels are $Mx$ plus some independent random noise
$(\text{Ber}\left(p\right))$ in each coordinate.

Then the goal is for Alice to send a message of minimal length, so that Bob
can distinguish between the YES and NO cases with probability at least $2/3$.

Observe that setting $p=1$ recovers the original Boolean Hidden Matching
problem. For significantly smaller values of $p$, the Hamming distance between
YES and NO instance labels decreases correspondingly. Thus while BHM can be
viewed as a gap promise problem, the Noisy Boolean Hidden Matching problem
essentially parametrizes the gap size. Now it should be apparent that the
previously discussed plain text protocol of Alice sending the parities of
$\Theta(\sqrt{n})$ vertices should fail for sufficiently small $p$. By
birthday paradox arguments, the parities for $\Theta(\sqrt{n})$ vertices
correspond to the observation of parities for roughly $\Theta(1)$ edges.
However for $p=o(1)$, Alice and Bob already know the parities of most of the
edges, because the vectors generated in the ${\bf YES}~{}$ and ${\bf NO}~{}$
cases corresponding to the possible edge labels only differ in $o(n)$
coordinates. Thus any message of length ${O}\left(\sqrt{n}\right)$ sent by
Alice is unlikely to be helpful to Bob. Indeed, we show that the communication
complexity of the $p$-Noisy Boolean Hidden Matching problem is generally
$\Omega\left(\sqrt{\frac{n}{p}}\right)$. More generally, we define the
$p$-Noisy Boolean Hidden Hypermatching problem as a means to find tradeoffs
between the noise $p$, the complexity of the problem, and the size of
hyperedges $t$ (see Section 3).

###### Theorem 1.4

For $p=\Omega\left(\frac{1}{n}\right)$, any randomized one-way protocol that
succeeds with probability at least $\frac{2}{3}$ for the $p$-Noisy Boolean
Hidden Hypermatching problem on hyperedges with $t$ vertices requires
$\Omega\left(n^{1-1/t}p^{-1/t}\right)$ bits of communication.

Through the flexibility of the $p$-Noisy Boolean Hidden Hypermatching problem,
we show hardness of approximation for graph problems on a parametrized family
of inputs. We first use $p$-Noisy Boolean Hidden Hypermatching to show
hardness of approximation for MAX-CUT in the streaming model on graphs whose
connected components have bounded size, which is a significant obstacle for
reductions to BHH. Unlike reductions from BHM [KKS15], our methods can show
nearly linear lower bounds for approximation close to $1$ even in this
setting:

###### Theorem 1.5

Let $2\leq t\leq n/10$ be an integer. For
$p\in\left[\frac{128t}{n},\frac{1}{2}\right]$, any one-pass streaming
algorithm that outputs a $\left(1+\frac{p}{14t}\right)$-approximation to the
MAX-CUT with probability at least $\frac{2}{3}$ requires
$\Omega\left(n^{1-1/t}p^{-1/t}\right)$ space, even for graphs with components
of size bounded by $4t$.

Similarly, we show hardness of approximation for maximum matching in the
streaming model better than $\Omega(\sqrt{n})$ on graphs whose connected
components have bounded size, which is again challenging for reductions from
either BHH or BHM.

###### Theorem 1.6

Let $2\leq t\leq n/10$ be some integer. For
$p\in\left[\frac{128t}{n},\frac{1}{2}\right]$, any one-pass streaming
algorithm that outputs a $\left(1+\frac{p}{6t}\right)$-approximation to the
maximum matching with probability at least $\frac{2}{3}$ requires
$\Omega\left(n^{1-1/t}p^{-1/t}\right)$ space, even for graphs with connected
components of size bounded by ${O}\left(t\right)$.

By comparison for graphs with connected components with constant bounded
sizes, existing lower bounds for both MAX-CUT and maximum matching only show
that $\Omega(n^{C})$ space is required, for some constant $C\in(0,1)$ bounded
away from $1$.

Our third graph streaming lower bound proves hardness of approximation for
maximum acyclic subgraph in the streaming model. [GVV17] showed that an
$\frac{8}{7}$-approximation requires $\Omega(\sqrt{n})$ space through a
reduction from BHM, but it was not evident how their reduction could be
generalized to BHH, due to its hyperedge structure. Instead, we use our
$p$-Noisy Boolean Hidden Matching communication problem to show a fine-grained
lower bound for the maximum acyclic subgraph problem with tradeoffs between
approximation guarantee and space. Independently, [AKSY20] showed a lower
bound that $(1-\epsilon)$-approximation requires
$\Omega(n^{1-O(\epsilon^{c})})$ space for a fixed constant $c>0$ through a
reduction from their one-or-many cycles communication problem.

###### Theorem 1.7

Let $2\leq t\leq n/10$ be some integer. For
$p\in\left[\frac{128}{n},\frac{1}{2}\right]$, any one-pass streaming algorithm
that outputs a $\left(1+\frac{p}{22}\right)$-approximation to the maximum
acyclic subgraph problem with probability at least $\frac{2}{3}$ requires
$\Omega\left(\sqrt{\frac{n}{p}}\right)$ space.

Finally, we introduce and study the graph classification problem in data
streams. Here the goal is for the streaming algorithm to output YES if the
input graph belongs to a specified isomorphism class, and output NO otherwise.
Graph isomorphism is one of the most fundamental problems in computer science;
it asks whether there exists an isomorphism between two given graphs, or more
specifically, whether there exists a bijection between the vertices of the two
graphs that preserves edges, i.e., the image of adjacent vertices remain
adjacent. A special important case of this problem is graph isomorphism on
tree graphs.

We show hardness of graph classification for complete binary trees on
insertion-only streams. This is a class of tree graphs for which we do not
know how to prove hardness using any other technique, showing our
communication problem may be useful for ultimately resolving the general graph
classification problem on data streams. In this setting, a stream of
insertions and deletions of edges in an underlying graph with $n$ vertices
arrives sequentially and the task is to classify whether the resulting graph
is isomorphic to a complete binary tree on $n$ vertices. Although it is
possible to produce a lower bound of $\Omega(\sqrt{n})$ space from BHM, it is
not evident that reductions from BHH can produce stronger lower bounds.
Instead, we use our $p$-Noisy Boolean Hidden Matching communication problem to
show a lower bound of $\Omega(n)$ space for graph classification of complete
binary trees even on insertion-only streams.

###### Theorem 1.8

Any randomized algorithm on insertion-only streams that correctly classifies
with probability at least $\frac{3}{4}$ whether an underlying graph is a
complete binary tree uses $\Omega(n)$ space.

In fact, we show more general parametrized space lower bounds for testing on
streams whether an underlying graph is a complete binary tree or
$\epsilon$-far from being a complete binary tree, where $\epsilon$-far is
defined as follows:

###### Definition 1.9

We say that a graph $G=(V,E_{1})$ is $\epsilon$ far from another graph
$H=(V,E_{2})$ on the same vertex set $V$ if at least $\epsilon\cdot|V|$ edge
insertions or deletions are required to get from $G$ to $H$, i.e.,
$|(E_{1}\setminus E_{2})\cup(E_{2}\setminus E_{1})|\geq\epsilon\cdot|V|$.

###### Theorem 1.10

For $\epsilon\in[\tfrac{512}{n},\tfrac{1}{2}]$, any randomized algorithm on
insertion-only streams that classifies, with probability at least
$\frac{3}{4}$, whether an underlying graph is a complete binary tree or
$\epsilon/16$-far from a complete binary tree uses
$\Omega\left(\sqrt{n/\epsilon}\right)$ space.

#### Related work.

Several communication problems inspired by the Boolean Hidden (Hyper)Matching
problem have recently been used in the literature to prove tight lower bounds
for the single pass or sketching complexity of several graph problems (e.g.,
[KKSV17, KK19] for the MAX-CUT problem, [KKP18] for subgraph counting, in
[GVV17, GT19, CGV20, CGSV21] for general CSPs). The recent work of [AKSY20]
gives multipass streaming lower bounds for the space complexity of the
aforementioned one-or-many cycles communication problem, which is tightly
connected to BHH, extending many of the abovementioned single pass lower
bounds to the multipass setting. Although (to the best of our knowledge)
property testing for graph isomorphism on streams have not been previously
studied, there is an active line of work, e.g. [FKM+05, FKM+08, SW15, GMT15,
MMPS17, HP19, CFPS20, AN21] studying property testing on graphs implicitly
defined through various streaming models.

###  1.2 Overview

We now outline the analysis of the Boolean Hidden Matching problem [KR06,
GKdW06, GKK+08], and describe the key differences in our approach.

#### A natural extension of BHM analysis and why it fails.

Recall that in BHM, Alice receives a binary vector $x\in\\{0,1\\}^{n}$, and
sends Bob a message $m$ of $c$ bits. Letting $A\subseteq\\{0,1\\}^{n}$ denote
the indicator of a ‘typical’ message, one shows that for a ‘typical’ matching
$M$ of size $\alpha n$, $\alpha\in(0,1/2)$, Bob’s posterior distribution $q$
on $Mx$ conditioned on the message received from Alice is close to uniform,
which in turn implies that Bob cannot distinguish between $w=Mx$ and
$w=Mx\oplus 1^{n}$. The approach of [GKdW06] upper bounds the total variation
distance from $q$ to the uniform distribution via the $\ell_{2}$ distance:
this lets one upper bound the $\ell_{2}$ distance to uniform in Fourier
domain, and then use Cauchy-Schwarz to obtain the required bound of
$\Omega(\sqrt{n})$ on the size $c$ of Alice’s message.

Since we are trying to obtain an $\Omega(\sqrt{n/p})$ lower bound for the
$p$-noisy Boolean Hidden Matching problem, it becomes clear that one can no
longer compare Bob’s posterior to the uniform distribution (the bound of
$\Omega(\sqrt{n})$ is tight here). Instead, one would like to compare the
distribution of Bob’s labels in the YES case to the same distribution in the
NO case. A natural approach here is to compare Bob’s posterior distribution
$q$ to the noisy version of the posterior, and relating these two
distributions to the Fourier transform of Alice’s message using the noise
operator $T_{\rho}$ for an appropriate choice of the parameter $\rho$.
Interestingly, however, this approach fails: one can verify that the expected
$\ell_{2}^{2}$ (over the randomness of the matching $M$) distance is too
large111If $f:\\{0,1\\}^{n}\to\\{0,1\\}$ is the characteristic function of a
typical message from Alice, the $\ell_{2}^{2}$ distance between the two
distributions is, up to appropriate scaling factors, equal to the sum of
squares of Fourier coefficients $\widehat{f}(s)$, scaled by a
$(1-(1-2p)^{|s|})\approx p\cdot|s|$ factor. While this factor gives us exactly
the required $p$ contribution for Fourier coefficients $s$ of Hamming weight
$1$, the contribution of higher weight terms is much larger, precluding the
analysis..

#### Our approach.

We provide an information theoretic proof for the complexity of $p$-Noisy
Boolean Hidden Hypermatching222In an earlier version of the paper we claimed
that the difficulties with the standard $\ell_{2}$-based Fourier analytic
approach can be circumvented using a related method that relies on KL
divergence instead of the $\ell_{2}$ norm. We discovered an error in that
proof and it is therefore omitted from the present version.. Informally, we
create a product distribution over $\frac{1}{p}$ instances of BHH, where the
$i$-th instance has size roughly distributed as
$\operatorname*{Bin}\left(n,p\right)$ and is a YES instance with probability
$\frac{1}{2}$, and a NO instance with probability $\frac{1}{2}$. The
distribution of the sizes for each instance allows us to match the
distribution of “flipped” edges in the $p$-Noisy BHH distribution. We would
like to use the product distribution to claim that any protocol that solves
$p$-Noisy BHH on a graph with $n$ vertices must also solve $\frac{1}{p}$
instances of BHH on graphs with $np$ vertices; however, communication
complexity is not additive so we use (conditional) information complexity.

We bound the $1$-way conditional information cost of any protocol, correct on
our distribution of interest, by first using a message compression result of
[JPY12] to relate the $1$-way conditional information cost of a single
instance to the $1$-way distributional communication complexity of the
instance. Our conditional information cost is conditioned on Bob’s inputs. We
note that recent work [AKL17] only bounds external information cost and it
does not seem immediate how to derive the same lower bound for conditional
information cost from their work [Ass21]. We then observe that any protocol
which solves the $p$-Noisy BHH must also solve a constant fraction of the
$\frac{1}{p}$ instances of BHH with size $\Omega(np)$, by distributional
correctness (note it need not solve all $\frac{1}{p}$ instances). Using the
conditional information cost in a direct sum argument, the communication
complexity of the protocol must be at least
$\frac{1}{p}\cdot\Omega\left((np)^{1-1/t}\right)=\Omega\left(n^{1-1/t}p^{-1/t}\right)$,
which lower bounds the communication.

#### Lower bound applications.

The remaining lower bounds are quite simple; they result from natural
generalizations of existing BHM or BHH reductions to the $p$-Noisy BHM or BHH.
For the MAX-CUT problem, [KKS15] give a reduction from BHM that creates a
connected component with eight edges for each edge $m_{i}$ in the matching
$M$. In the case $(Mx)_{i}\oplus w_{i}=0$, the resulting graph is bipartite,
so that the max cut induced by the connected component is $8$. In the case
$(Mx)_{i}\oplus w_{i}=1$, the resulting graph is not bipartite, so that the
max cut induced by the connected component is at most $7$ (see Figure 1). Thus
the max cut for $Mx\oplus w=0^{n}$ has size $4n$ and the max cut for $Mx\oplus
w=1^{n}$ has size at most $7n/2$, so any sufficiently small constant factor
approximation algorithm to the max cut requires $\Omega(\sqrt{n})$ space.
Observe that the same reduction from $p$-Noisy BHM also works, although since
we set $\alpha=1/2<1$, we also have to consider components corresponding to
unmatched vertices. Due to the fact that only a $p$ fraction of the components
change their contribution from $8$ to $7$ in the NO case, our reduction works
for $\left(1+\Theta(p)\right)$-approximation. We give a similar argument for
$p$-Noisy BHH, which allows parametrization of the connected component size.

To show hardness of approximation for the maximum matching problem, we use a
reduction similar to that of [BGM+19]. However, we reduce from $p$-noisy BHH.
We represent each coordinate of Alice’s input with a single edge, and
represent each hyperedge of Bob with two cdisjoint cliques. Supports of the
cliques are defined in such a way that the resulting connected components have
even size exactly if $(Mx)_{i}\oplus w_{i}=0$, in which case they are
perfectly matchable (see Figure 2). In the noisy (NO) case, however, a $p$
fraction of these components of size $O(t)$ will have odd size, which leads to
an overall $(1+\Theta(p/t))$ factor loss in the size of the maximum matching.

To show hardness of approximation for maximum acyclic subgraph, we use a
reduction by [GVV17]. For each $i\in[n]$, the case $(Mx)_{i}\oplus w_{i}=1$
corresponds to an isolated subgraph with eight edges that contains no cycle,
so that its maximum acyclic subgraph has size eight. However, the case
$(Mx)_{i}\oplus w_{i}=0$ creates an isolated subgraph with eight edges that
contains a cycle, so that its maximum acyclic subgraph has size seven (see
Figure 3). Thus if $Mx\oplus w=0^{n}$ (the YES case), then all subgraphs
corresponding to matching edges contribute only $7$ to the maximum acyclic
subgraph. However, in the NO case some of these contribute $8$, increasing the
total size of the maximum acyclic subgraph by a factor $(1+\Theta(p))$.

To show hardness of classifying whether an underlying graph is a complete
binary tree, we use a gadget by [EHL+18] that embeds BHM into the bottom layer
of a binary tree. For each $i\in[n]$ where $n$ is assumed to be a power of
two, the case $(Mx)_{i}\oplus w_{i}=0$ creates two paths of length two, which
can be used to extend the binary tree to an additional layer at two different
nodes. However, the case $(Mx)_{i}\oplus w_{i}=1$ creates a path of length one
and a path of length three, which results in a non-root node having degree two
(see Figure 4). Thus the resulting graph is a complete binary tree if and only
if $Mx\oplus w=0^{n}$. While BHM requires $\Omega(\sqrt{n})$ space to
distinguish whether $Mx\oplus w=0^{n}$ or $Mx\oplus w=1^{n}$, the $p$-Noisy
version of BHM demands $\Omega\left(\sqrt{\frac{n}{p}}\right)$ space to
distinguish between the YES and NO cases. Now for
$p=\Theta\left(\frac{1}{n}\right)$, we have $Mx\oplus w\neq 0^{n}$ with high
probability in the NO case. Hence, the graph classification problem also
solves $p$-Noisy BHM in this regime of $p$ and requires $\Omega(n)$ space.

##  2 Preliminaries

We use the notation $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. We use
$\operatorname*{poly}(n)$ to denote a fixed constant degree polynomial in $n$
and $\frac{1}{\operatorname*{poly}(n)}$ to denote some arbitrary degree
polynomial in $n$ corresponding to the choice of constants in the algorithms.
We use $\operatorname*{polylog}(n)$ to denote polylogarithmic factors of $n$.
We say an event occurs with high probability if it occurs with probability at
least $1-\frac{1}{\operatorname*{poly}(n)}$. For $x,y\in\\{0,1\\}$, we use
$x\oplus y$ to denote the sum of $x$ and $y$ modulo $2$.

We define $\alpha$-approximation for maximization problems for one-sided error
(as opposed to two-sided errors):

######  Definition 2.1 ($\alpha$-Approximation for Maximization Problems)

For a parameter $\alpha\geq 1$, we say that an algorithm $\mathcal{A}$ is an
$\alpha$-approximation algorithm for a maximization problem with optimal value
$\mathsf{OPT}$ if $\mathcal{A}$ outputs some value $X$ with
$X\leq\mathsf{OPT}\leq\alpha X$.

##  3 Noisy Boolean Hidden Hypermatching

We start with the definition of the $p$-noisy Boolean Hidden Hypermatching
problem ($p$-noisy BHH), then given a simple protocol for it and show that
this protocol is asympototically tight.

###### Definition 3.1

A $t$-hypermatching on $[n]$ is a collection of disjoint subsets of $[n]$,
each of size $t$, which we call hyperedges.

The noisy Boolean Hidden Hypermatching problem is:

###### Definition 3.2

For $p\in[0,1]$ and integer $t\geq 2$ the $p$-Noisy Boolean Hidden
$t$-Hypermatching ($p$-noisy BHH) is a one way two party communication
problem:

  * •

Alice gets $x\in\\{0,1\\}^{n}$ uniformly at random.

  * •

Bob gets $M$, a $t$-hypermatching of $[n]$ with $\alpha n/t$ hyperedges, for a
constant $\alpha\in(0,1]$. $M$ is considered to be the $\alpha n/t\times n$
incidence matrix of the matching hyperedges. That is, the $i^{\text{th}}$ row
of $M$ has ones corresponding to the vertices of the $i^{\text{th}}$ matching
hyperedge, and zeros elsewhere.

  * •

Bob also receives labels for each hyperedge $m_{i}$. In the YES case Bob
receives edge labels $w=Mx$ (the true parities of each the matching hyperedges
with respect to $x$). In the NO case (the noisy case) Bob receives labels
$w\oplus z\in\\{0,1\\}^{M}$, where each $z_{i}$ is an independent
$\text{Ber}\left(p\right)$ variable.

  * •

Output: Bob must determine whether the communication game is in the YES or NO
case.

#### A protocol for $p$-noisy BHH.

We begin by presenting a simple protocol for solving Boolean hidden
hypermatching, which turns out to be nearly asymptotically optimal: for some
$c\geq t$ Alice sends a set $S$ of $c$ random bits of $x$ to Bob. Bob then
takes each hyperedge that is fully supported on $S$, and verifies that his
label is the true parity. If all such labels reflect the true parity, Bob
guesses the YES case, while if there is a discrepancy Bob guesses the NO case.

It is clear that the only way the protocol can fail is if in the NO case no
hyperedge is simultaneously supported on $S$ and mislabeled. Let us call the
event that the $i^{\text{th}}$ hyperedge, $m_{i}$ is supported on $S$ and
mislabeled $\mathcal{E}_{i}$. For each hyperedge of $M$, the probability of
being supported on $S$ is $\binom{c}{t}/\binom{n}{t}\geq c^{t}/e^{t}n^{t}$,
while the probability of being mislabeled is independently $p$. Therefore,

$\mathbb{P}(\mathcal{E}_{i})\geq p\cdot\left(\frac{c}{en}\right)^{t}.$

Since the events $\mathcal{E}_{i}$ are negatively correlated we have that

$\displaystyle\mathbb{P}\left(\bigcup_{i=1}^{\alpha
n/t}\mathcal{E}_{i}\right)$ $\displaystyle\geq 1-\prod_{i=1}^{\alpha
n/t}\left(1-\mathbb{P}(\mathcal{E}_{i})\right)$ $\displaystyle\geq
1-\left(1-p\cdot\left(\frac{c}{en}\right)^{t}\right)^{\alpha n/t}$
$\displaystyle\geq 1-\exp\left(-\frac{p\alpha
n}{t}\cdot\left(\frac{c}{en}\right)^{t}\right)$

Therefore, if $t\leq n/10$ and $c=\Omega(n^{1-1/t}(p\alpha)^{-1/t})$, this
probability is an arbitrarily large constant, and Bob can distinguish between
the YES and NO cases with high constant probability.

###  3.1 Communication Complexity of Noisy BHH

In this section, we establish our lower bound on the communication complexity
of Noisy BHH. The core of the proof is a reduction to Boolean Hidden
Hypermatching, whose complexity we defined in Theorem 1.2. The advantage of
this approach is that we are able to extend the result of the previous section
to the case of $\alpha>1/2$, and in particular to $\alpha=1$ – where Bob
receives a perfect hypermatching. However, in this setting we need to be
careful about the parity of the noise applied to the labels in the NO case.

###### Definition 3.3

We define the distribution $\mathcal{Z}_{p}^{n}$, as identical to the
independent vector of $\text{Ber}\left(p\right)$ variables of length $n$, but
with the condition that the number of ones is even:

$V\sim\text{Ber}\left(p\right)^{n}\ \Longrightarrow\
V\Big{|}2|w_{H}(V)\sim\mathcal{Z}_{p}^{n}$

where $w_{H}$ denotes the Hamming weight. More formally, if
$Z\sim\mathcal{Z}_{p}^{n}$ we have

$\mathbb{P}(Z=z)=\frac{\mathbbm{1}(2|w_{H}(z))p^{w_{H}(z)}(1-p)^{n-w_{H}(z)}}{\sum_{z^{\prime}\in\\{0,1\\}^{n}}\mathbbm{1}(2|w_{H}(z^{\prime}))p^{w_{H}(z^{\prime})}(1-p)^{n-w_{H}(z^{\prime})}}.$

Furthermore, let $|\mathcal{Z}_{p}^{n}|$ denote the distribution of the
Hamming weight of a variable from $\mathcal{Z}_{p}^{n}$.

We are now able to define the distributional communication problem of
$p$-Noisy Perfect Boolean Hidden Hypermatching:

###### Definition 3.4

For $p\in[0,1]$ and integer $t\geq 2$ the $p$-Noisy Perfect Boolean Hidden
$t$-Hypermatching ($p$-Noisy PBHH) is a one-way two-party communication
problem:

  * •

Alice gets $x\in\\{0,1\\}^{n}$.

  * •

Bob gets $M$, a perfect $t$-hypermatching of $[n]$ (that is $n/t$ hyperedges).

  * •

Bob also receives edge labels $w\in\\{0,1\\}^{n/t}$. With probability $1/2$,
we are in the YES case, and the edge labels satisfy $Mx=w$. With probability
$1/2$, we are in the NO case and the edge labels satisfy $Mx\oplus z=w$, where
$Z\sim\mathcal{Z}_{p}^{n/t}$.

  * •

Output: Bob must determine whether the communication game is in the YES or NO
case.

We prove a lower bound on the communication and information complexity of
$p$-Noisy BHH by considering the uniform input distribution: We are in the YES
and NO cases with probability $1/2$ each; $x$ is sampled uniformly at random
from all $n$-length bit strings and $M$ is sampled uniformly at random from
all $t$-hypermatchings of size $\alpha n/t$ on $[n]$. We replace the variables
$x$, $w$, and $z$ with the _r_ andom variables $X$, $W$ and $Z$ respectively.
We first define quantities from information theory in order to show a direct
sum theorem for internal information.

######  Definition 3.5 (Entropy and conditional entropy)

The _entropy_ of a random variable $X$ is defined as

$H(X):=\sum_{x}p(x)\log\frac{1}{p(x)},$

where $p(x)=\mathbf{Pr}\left[X=x\right]$. The _conditional entropy_ of $X$
with respect to a random variable $Y$ is defined as

$H(X|Y)=\underset{y}{\mathbb{E}}\left[H(X|Y=y)\right].$

######  Definition 3.6 (Mutual information and conditional mutual information)

The _mutual information_ between random variables $A$ and $B$ is defined as

$I(A;B)=H(A)-H(A|B)=H(B)-H(B|A).$

The _conditional mutual information_ between $A$ and $B$ conditioned on a
random variable $C$ is defined as

$I(A;B|C)=H(A|C)-H(A|B,C).$

######  Definition 3.7 (Communication Complexity)

Given a distributional one-way communication problem on inputs in
$\mathcal{X}\times\mathcal{Y}$ distributed according to $\mathcal{D}$, and a
one-way protocol $\Pi$, let $\Pi(X)$ denote the message of Alice under input
$X$. Then the _communication complexity_ of $\Pi$ is the maximum length of
$\Pi(X)$, over all inputs $X$ and private randomness $r$:

$\mathsf{CC}(\Pi):=\max_{X\in\text{supp}(\mathcal{D}),\textrm{ private
randomness }r}|\Pi_{r}(X)|,$

where $\Pi_{r}(X)$ is the length of Alice’s message on input $X$ with private
randomness $r$.

######  Definition 3.8 (Internal Information Cost)

Given a distributional one-way communication problem on inputs in
$\mathcal{X}\times\mathcal{Y}$ distributed according to $\mathcal{D}$, and a
one-way protocol $\Pi$, let $\Pi(X)$ denote the message of Alice under input
$X$. Then we define the _internal information cost_ of $\Pi$ with respect to
some other distribution $\mathcal{D}^{\prime}$ to be

$\mathsf{IC}_{\mathcal{D}^{\prime}}(\Pi):=I_{\mathcal{D^{\prime}}}(\Pi(X);X|Y,R),$

where $\Pi(X)$ denotes the message sent from Alice to Bob in the protocol
$\Pi$ on input $X$. Here $R$ is the public randomness.

Here $\mathcal{D}$ is the correctness distribution for the protocol $\Pi$ and
$\mathcal{D^{\prime}}$ is a distribution for measuring information.

The following well-known theorem (e.g., Lemma 3.14 in [BR14]) shows that the
communication complexity of any protocol is at least the (internal)
information cost of the protocol.

###### Theorem 3.9

Given a distributional one-way communication problem on inputs in
$\mathcal{X}\times\mathcal{Y}$ distributed according to $\mathcal{D}$, and a
one-way protocol $\Pi$, let $\Pi(X)$ denote the message of Alice under input
$X$. Then, if
$\text{supp}(\mathcal{D}^{\prime})\subseteq\text{supp}(\mathcal{D})$,

$\mathsf{CC}(\Pi)\geq\mathsf{IC}_{\mathcal{D}^{\prime}}(\Pi).$

Note that we include the condition
$\text{supp}(\mathcal{D}^{\prime})\subseteq\text{supp}(\mathcal{D})$ since our
distributional communication problem is defined as the maximum message length
over inputs in the support of $\mathcal{D}$, and thus
$I_{\mathcal{D^{\prime}}}(\Pi(X);X|Y)\leq H(\Pi(X)|Y)\leq H(\Pi(X))\leq{\bf
E}_{X\sim\mathcal{D}^{\prime}}|\Pi(X)|$, where $|\Pi(X)|$ is the length of
Alice’s message on random input $X$, which in turn is at most
$\max_{x\in\text{supp}(\mathcal{D}^{\prime}),\textrm{ private randomness
}r}|\Pi_{r}(x)|\leq\max_{x\in\text{supp}(\mathcal{D}),\textrm{ private
randomness }r}|\Pi_{r}(x)|=\mathsf{CC}(\Pi)$. Here $|\Pi_{r}(x)|$ denotes the
length of Alice’s message on input $x$ with private randomness $r$.

The core of our proof is to show that any protocol that succeeds in solving
the $p$-Noisy PBHH with high constant probability has high internal
information cost. This statement is then reduced to a statement about the
information cost of a distributional version of the standard BHH problem,
through a method similar to that of [BJKS04].

For completeness we state this distributional version of BHH:

###### Definition 3.10

For an _even_ integer $n$, and integer $t\geq 2$, Boolean Hidden
$t$-Hypermatching (BHH) is a one-way two-party communication problem:

  * •

Alice gets $X\in\\{0,1\\}^{n}$ uniformly at random.

  * •

Bob gets $M$, a perfect $t$-hypermatching of $[n]$ (that is, $n/t$ hyperedges)
uniformly at random.

  * •

Bob also receives edge labels $W\in\\{0,1\\}^{n/t}$. With probability $1/2$,
we are in the YES case, and Bob’s edge labels satisfy $MX=W$. With probability
$1/2$, we are in the NO case and Bob’s edge labels satisfy $MX\oplus
W=1^{n/t}$.

  * •

Output: Bob must determine whether the communication game is in the YES or NO
case.

We call this input distribution of BHH $\mathcal{D}$, and call the
distributions when conditioning on the YES and NO cases $\mathcal{D}_{\bf
YES}$ and $\mathcal{D}_{\bf NO}$, respectively.

######  Lemma 3.11 (Lemma 3.4 in [JPY12] with $t=1$)

Given a distributional one-way communication problem on inputs in
$\mathcal{X}\times\mathcal{Y}$ distributed according to
$\mathcal{D}^{\prime}$. Suppose there exists a one-way communication protocol
$\Pi^{\prime}$ succeeding with probability $1-\delta$ with

$IC_{\mathcal{D}^{\prime}}(\Pi^{\prime})\leq c.$

Then for any $\epsilon>0$ there exists some other one-way communication
protocol $\Pi$ with

$CC(\Pi)\leq\frac{c+5}{\epsilon}+O\left(\log\frac{1}{\epsilon}\right),$

and succeeding with probability $1-\delta-6\epsilon$.

###### Corollary 3.12

Any randomized protocol $\Pi$ that succeeds with probability at least
$\frac{2}{3}$ over the distribution $\mathcal{D}$ for the Boolean Hidden
Hypermatching problem with hyperedges that contain $t$ vertices requires
internal information cost $\Omega(n^{1-1/t})$ when measured on the $D$
distribution.

Proof :  It is known, e.g. [AKL17], that the communication complexity of this
distributional version of BHH is $\Omega(n^{1-1/t})$ for any protocol that
succeeds with probability bounded away from $1/2$. However, any protocol with
internal information cost $o(n^{1-1/t})$, when combined with Lemma 3.11 for a
small constant $\epsilon$, would result in a better protocol for BHH; a
contradiction. $\Box$

######  Corollary 3.13 (Conditional information lower bounds for BHH)

Any randomized protocol $\Pi$ that succeeds with probability at least
$\frac{2}{3}$ over the distribution $\mathcal{D}$ for the Boolean Hidden
Hypermatching problem with hyperedges that contain $t$ vertices requires
internal information cost $\Omega(n^{1-1/t})$ when measured on the
$\mathcal{D}_{\bf YES}$ distribution. That is:

$I_{\mathcal{D}_{\bf YES}}(X;\Pi(X)|M,W)=\Omega(n^{1-1/t}).$

Proof :  By Corollary 3.12 we know that

$\displaystyle I_{\mathcal{D}}(X;\Pi(X)|M,W)=\Omega(n^{1-1/t})$

We decompose this into information complexity with respect to the
$\mathcal{D}_{\bf YES}$ and $\mathcal{D}_{\bf NO}$ distributions. Let $b$ be
the single bit denoting whether the input is in the YES or NO case. Since $b$
has entropy $1$, adding or removing the conditioning on $b$ amounts to at most
a change of $1$ in the mutual information.

$\displaystyle I_{\mathcal{D}}(X;\Pi(X)|M,W)$ $\displaystyle\leq
1+I_{\mathcal{D}}(X;\Pi(X)|M,W,b)$
$\displaystyle=1+\tfrac{1}{2}I_{\mathcal{D_{\bf
YES}}}(X;\Pi(X)|M,W,b)+\tfrac{1}{2}I_{\mathcal{D_{\bf
NO}~{}}}(X;\Pi(X)|M,W,b)$

Note that $X$ (and consequently $\Pi(X)$) follow the same distribution in both
the YES and NO cases. Furthermore, note that BHH flips each bit of the edge
labels deterministically in the NO case. Therefore, in both the YES and NO
cases, revealing $b$ and $W$ amounts to revealing the true edge parities.
Thus, two terms ($I_{\mathcal{D}_{\bf YES}}$ and
$I_{\mathcal{D}_{\textbf{NO}}}$) are equal:

$\displaystyle I_{\mathcal{D}}(X;\Pi(X)|M,W)$ $\displaystyle\leq
1+I_{\mathcal{D}_{\bf YES}}(X;\Pi(X)|M,W,b)$ $\displaystyle\leq
2+I_{\mathcal{D}_{\bf YES}}(X;\Pi(X)|M,W).$

The statement of the corollary then follows. $\Box$

We define one more distributional one-way communication problem to bridge the
gap between BHH and $p$-Noisy PBHH. It consists of $1/(2p)$ instances of BHH,
of which exactly one or none are in the NO case. Furthermore all the instances
of BHH are of variable size:

###### Definition 3.14

Let $p\in\left(\frac{t}{2n},\frac{1}{2}\right]$, where we assume for
simplicity that $Q:=1/2p$ is an integer. For $t\geq 2$ integer, the Variable
Size, $Q$-Copy Boolean Hidden $t$-Hypermatching ($\overline{\text{VBHH}}$) is
a one-way two-party communication problem:

  * •

$S_{1},\ldots,S_{Q}$ are drawn independently from $|\mathcal{Z}_{p}^{n/t}|$
(recall Definition 3.3), and $r$ is drawn independently, uniformly from $[Q]$.

  * •

In the YES case, Alice and Bob get $Q$ independent copies of BHH distributed
according to $\mathcal{D}_{\bf YES}$, where the $i^{\text{th}}$ copy is on
$t\cdot S_{i}$ vertices.

  * •

In the NO case, Alice and Bob again get $Q$ independent copies of BHH, where
the $i^{\text{th}}$ copy has size $t\cdot S_{i}$. All copies are distributed
according to $\mathcal{D}_{\bf YES}$, except the $r^{\text{th}}$ copy, which
is distributed according to $\mathcal{D}_{\bf NO}$.

  * •

Output: Bob must determine whether the communication game is in the YES or NO
case.

We call this input distribution of $\overline{\text{VBHH}}$
$\overline{\mathcal{D}}$, and call the distributions when conditioning on the
YES and NO cases $\overline{\mathcal{D}}_{\bf YES}$ and
$\overline{\mathcal{D}}_{\bf NO}$ respectively.

###### Theorem 3.15

Any randomized protocol $\Pi$ that succeeds with probability at least
$\frac{4}{5}$ over the distribution $\overline{\mathcal{D}}$ for the
$\overline{\text{VBHH}}$ parameters $n$, $2\leq t\leq n/100$ and
$p\in\left(\frac{t}{2n},\frac{1}{2}\right]$, has internal information cost
$\Omega(n^{1-1/t}p^{-1/t})$ when measured on the $\overline{\mathcal{D}}_{\bf
YES}$ distribution. That is:

$I_{\overline{\mathcal{D}}_{\bf
YES}}(X;\Pi(X)|M,W)=\Omega(n^{1-1/t}p^{-1/t}).$

Proof :  Note that in the context of $\overline{\text{VBHH}}$ $X$, $M$, and
$W$ are vectors of length $Q$, where ($X_{i}$, $M_{i}$, $W_{i}$) are
individual instances of inputs of BHH. Let $\Pi$ be a protocol that succeeds
with probability $4/5$ on $\overline{\mathcal{D}}$. Then

$\displaystyle I_{\overline{\mathcal{D}}_{\bf YES}}(X;\Pi(X)|M,W)$
$\displaystyle=\sum_{i=1}^{Q}I_{\overline{\mathcal{D}}_{\bf
YES}}(X_{i};\Pi(X)|M,W,X_{<i})$
$\displaystyle\geq\sum_{i=1}^{Q}I_{\overline{\mathcal{D}}_{\bf
YES}}(X_{i};\Pi(X)|M,W),$ (1)

where the mutual information only decreases by removing the conditioning on
$X_{<i}$ because $X_{i}$ is independent of $X_{<i}$.

Now, we know that $\Pi$ succeeds with probability at least $4/5$. Since $r$ is
distributed uniformly in $[Q]$, on at least a constant fraction of the
possible values of $r$, $\Pi$ must succeed with probability at least $3/4$ for
that specific value of $r$. Let $R\subseteq[Q]$ be the set of such values of
$r$, so that $|R|=\Omega(Q)$.

Consider a term corresponding to $i\in R$:

$\displaystyle I_{\overline{\mathcal{D}}_{\bf YES}}(X_{i};\Pi(X)|M,W).$ (2)

We will demonstrate that there exists a protocol for solving BHH as defined in
Definition 3.10 with probability at least $3/4$, with internal information
cost equal to the quantity in Equation 2. By Corollary 3.13 this will allow us
to lower bound Equation 2.

The protocol is as follows: Alice and Bob are given inputs of BHH distributed
according to $\mathcal{D}$, which we will call $X_{i}$, $M_{i}$, $W_{i}$.
Alice and Bob will then generate $Q-1$ more instances of BHH from the
distribution $\mathcal{D}_{\bf YES}$, called $(X_{j},M_{j},W_{j})$, for
$j=1,\ldots,i-1,i+1,\ldots,Q$. $M_{j}$ and $W_{j}$ are always generated using
public randomness, while $X_{j}$ is generated using the private randomness of
Alice. This allows Alice to have access to $M_{j}$ and $W_{j}$, which in turn
allows $X_{j}$ to be generated in such a way that $(X_{j},M_{j},W_{j})$ is
indeed distributed according to $\mathcal{D}_{\bf YES}$. Alice then simply
sends the message $\Pi(X_{1},\ldots,X_{Q})=\Pi(X)$. Since all instances of BHH
other than the $i^{\text{th}}$ one are in the YES case, the distribution
$(X,M,W)$ is exactly $\overline{\mathcal{D}}$ conditioned on $r=i$;
furthermore, it is in the YES case exactly if $(X_{i},M_{i},W_{i})$ is in the
YES case. Since $i\in R$, $\Pi$ succeeds with probability at least $3/4$,
allowing Alice and Bob to succeed in solving BHH with the same probability.

Finally, we must address the fact that the above protocol succeeds with
probability $3/4$ on an instance of BHH with variable size ($t\cdot S_{i}\sim
t\cdot|\mathcal{Z}_{p}^{n/t}|$). One can easily verify that for large enough
$n$ $\mathbb{P}(S_{i}<pn/(2t))$ is at most $1/100$. Therefore, the protocol
must succeed with probability at least $3/4-1/100\geq 2/3$ conditioned on
$S_{i}\geq pn/(2t)$. Finally, this means that the protocol must succeed with
probability at least $2/3$ for at least one specific such setting of $S_{i}$.
Therefore, by Corollary 3.13,

$I_{\overline{\mathcal{D}}_{\bf
YES}}(X_{i};\Pi(X)|M,W)\geq\Omega\left(\left(t\cdot\frac{pn}{2t}\right)^{1-1/t}\right)=\Omega\left((pn)^{1-1/t}\right).$

Therefore, returning to Equation 1, we have that

$\displaystyle I_{\overline{\mathcal{D}}_{\bf YES}}(X;\Pi(X)|M,W)$
$\displaystyle\geq\sum_{i=1}^{Q}I_{\overline{\mathcal{D}}_{\bf
YES}}(X_{i};\Pi(X)|M,W)\geq\Omega\left(Q(pn)^{1-1/t}\right)=\Omega\left(n^{1-1/t}p^{-1/t}\right).$

$\Box$

Finally, we lower bound the communication complexity of $p$-Noisy PBHH, by a
reduction from $\overline{\text{VBHH}}$.

###### Theorem 3.16

For $t\leq n/10$, and $p\in\left(\frac{t}{2n},\frac{1}{2}\right]$, the
communication complexity of $p$-Noisy Perfect Boolean Hidden Hypermatching
with success probability $5/6$ is $\Omega(n^{1-1/t}p^{-1/t})$ bits.

Proof :  Suppose there exists a one-way communication protocol solving
$p$-Noisy PBHH with probability at least $5/6$. We will construct a
communication protocol for $\overline{\text{VBHH}}$ with the same parameters
$n$, $t$ and $p$.

Let Alice and Bob receive $X,S$ and $M,W,S$ respectively, distributed
according to $\overline{\mathcal{D}}$ as defined in Definition 3.14. One can
easily verify that the total number of vertices in all subinstances of BHH,
that is $\sum t\cdot S_{i}$, is at most $n$ with probability at least $99/100$
for large enough $n$. We call this event $\mathcal{E}$; if $\mathcal{E}$ is
not true, Alice and Bob fail the protocol. From now on we condition on
$\mathcal{E}$.

Let us label the vertices from all subinstances of BHH by

$V=\\{(i,j)|i\in[Q],\ j\in[t\cdot S_{i}]\\}.$

Let $\phi$ be an embedding of $V$ into $[n]$ chosen uniformly at random using
public randomness. Since we assumed the event $\mathcal{E}$, such an embedding
exists, and since we are using public randomness to generate it, both Alice
and Bob have access to $\phi$.

Alice and Bob generate their inputs for $p$-Noisy PBHH, which they will call
$(X^{*},M^{*},W^{*})$. We call the elements of $[n]$ covered by $\phi$ (that
is $\phi(V)$), $A^{+}$; we call the remaining elements, not covered by $\phi$,
$A^{-}$. We define the inputs of Alice and Bob separately on the two parts of
$[n]$.

Bob generates his input ($M^{*}$ and $W^{*}$) on $A^{+}$ as follows: For all
$i\in[Q]$, and all hyperedges $\\{j_{1},j_{2},\ldots,j_{t}\\}\in M_{i}$, Bob
generates a hyperedge $\\{\phi(i,j_{1}),\ldots,\phi(i,j_{t})\\}\subseteq[n]$,
which inherits the label of $\\{j_{1},\ldots,j_{t}\\}\in M_{i}$. Alice
generates her input as follows: For each $(i,j)\in V$, Alice sets
$X^{*}({\phi(i,j)})$ to $X_{i}(j)$.

On $A^{-}$, Alice and Bob use public randomness to generate both of their
inputs, allowing them to be dependent. Alice sets $X^{*}$ uniformly at random
on $A^{-}$, while Bob adds a uniformly random perfect hypermatching of $A^{-}$
to $M^{*}$. Finally, the labels of this perfect matching are set to reflect
the true parities of $X^{*}$, that is $M^{*}_{i}X^{*}\oplus W^{*}_{i}=0$ for
any $M^{*}_{i}$ matching hyperedge supported on $A^{-}$.

Since $\phi$ was chosen uniformly randomly, the distribution of
$(X^{*},M^{*},W^{*})$ conforms to what is prescribed in Definition 3.4.
Indeed, $X^{*}$ and $M^{*}$ are uniformly random. Furthermore, if the original
instance of $\overline{\text{VBHH}}$ is in the YES case, the edge labels
always reflect the true parity of $X^{*}$ on the hyperdege (and thus the
constructed instance of $p$-Noisy PBHH is also in the YES case) due to the
parity assumptions on the edge labels $W$. When the original instance of
$\overline{\text{VBHH}}$ is in the NO case, a random subset of the edge labels
are flipped. This subset has size $S_{r}\sim|\mathcal{Z}_{p}^{n/t}|$, exactly
as in the NO case of $p$-Noisy PBHH.

In conclusion, if Alice and Bob can solve their newly constructed instance of
$p$-Noisy PBHH with probability $5/6$, they can solve the original instance of
$\overline{\text{VBHH}}$ with probability at least

$5/6\cdot\mathcal{P}(\mathcal{E})\geq 4/5.$

Therefore, by Theorem 3.15, and Theorem 3.9 the protocol requires space
$\Omega\left(n^{1-1/t}p^{-1/t}\right)$. $\Box$

##  4 Applications

In this section, we give a number of applications for the $p$-Noisy BHM and
$p$-Noisy BHH problems. Through a reduction from $p$-Noisy BHH, we first show
hardness of approximation for max cut in the streaming model on graphs whose
connected components have bounded size, which is a significant obstacle for
reductions to BHM. Unlike reductions from BHM, our reduction from $p$-Noisy
BHM can still show nearly linear lower bounds in this setting.

We then show hardness of approximation for maximum matching in the streaming
model better than $\Omega(\sqrt{n})$ on graphs whose connected components have
bounded size. Again our reduction displays flexibility beyond what is offered
by either BHM or BHH for both parametrization of component size and tradeoffs
between approximation guarantee and space complexity.

Finally, we show hardness of approximation for maximum acyclic subgraph.
[GVV17] show a $\Omega(\sqrt{n})$ lower bound for $\frac{8}{7}$-approximation,
but the reduction does not readily translate into a stronger lower bound from
BHH, due to the hyperedge structure of BHH. We use our $p$-Noisy BHM problem
to give a fine-grained lower bound that provides tradeoffs between the
approximation guarantee and the required space.

###  4.1 MAX-CUT

Recall the following definition of the MAX-CUT problem.

######  Problem 4.1 (MAX-CUT)

Given an unweighted graph $G=(V,E)$, the goal is to output the maximum of the
number of edges of $G$ that cross a bipartition, over all bipartitions of $V$,
i.e., $\max_{P\cup Q=V,P\cap Q=\emptyset}|E\cap(P\times Q)|$.

To show hardness of approximation of MAX-CUT in the streaming model, where the
edges of the underlying graph $G$ arrive sequentially, we use a reduction
similar to [KKS15], who gave a reduction from BHM that creates a connected
component with $8$ edges for each edge $m_{i}$ in the input matching $M$ from
BHM. The key property of the reduction of [KKS15] is that for $(Mx)_{i}\oplus
w_{i}=0$, the connected component corresponding to $m_{i}$ is bipartite and
its induced max cut has size $8$, but for $(Mx)_{i}\oplus w_{i}=1$, the
connected component is not bipartite and its induced max cut has size at most
$7$ (see Figure 1). Therefore, the max cut for $Mx\oplus w=0^{n}$ has size
$8n$ and the max cut for $Mx\oplus w=1^{n}$ has size at most $7n$, which gives
the desired separation for a constant factor approximation algorithm.

We instead reduce from Noisy Boolean Hidden Hypermatching. Suppose Alice is
given a binary vector $x$ of length $n=2kt$ and Bob is a given a hypermatching
$M$ of size $n/2t=k$ on $n$ vertices, where each edge contains $t$ vertices,
so that $\alpha=\frac{1}{2}$. Bob also receives a vector $w$ of length $k$,
generated according to the YES or NO case of the $p$-noisy BHH (see Definition
3.2). To distinguish between the two cases:

  * •

Alice creates the four vertices $a_{i}$, $b_{i}$, $c_{i}$, and $d_{i}$ for
each $i\in[n]$ corresponding to a coordinate of $x$.

  * •

If $x_{i}=0$, then Alice adds the edges $(a_{i},b_{i})$, $(c_{i},d_{i})$, and
$(a_{i},d_{i})$, but if $x_{i}=1$, then Alice instead adds the edges
$(a_{i},b_{i})$, $(c_{i},d_{i})$, and $(a_{i},c_{i})$.

  * •

For each hyperedge $m_{i}=(j_{i,1},\ldots,j_{i,t})$ of $M$, with $j_{i,s}\leq
j_{i,s+1}$, if $w_{i}=0$ Bob adds the edges $(d_{j_{i,s}},a_{j_{i,s+1}})$ for
$s\in[t-1]$, and the edge $(d_{j_{i,t}},a_{j_{i,1}})$. Otherwise if $w_{i}=1$,
then Bob instead adds the edges $(d_{j_{i,s}},a_{j_{i,s+1}})$ for $s\in[t-1]$
and the edge $(d_{j_{i,t}},b_{j_{i,1}})$.

By design, the connected component of the graph corresponding to $m_{i}$ is
bipartite if and only if $(Mx)_{i}\oplus w_{i}=0$. Hence, the max cut has size
$4t$ if $(Mx)_{i}\oplus w_{i}=0$ and size at most $4t-1$ otherwise, i.e., when
$(Mx)_{i}\oplus w_{i}=1$.

$a_{1}$$b_{1}$$d_{1}$$c_{1}$$x_{1}=0$$a_{2}$$b_{2}$$d_{2}$$c_{2}$$x_{2}=1$$a_{3}$$b_{3}$$d_{3}$$c_{3}$$x_{3}=1$$a_{4}$$b_{4}$$d_{4}$$c_{4}$$x_{4}=0$$w_{1}=1$$w_{2}=0$
Figure 1: Example of reduction from Noisy Boolean Hidden Matching (Noisy BHH
with $t=2$) to MAX-CUT. Solid lines added by Alice, dashed purple lines added
by Bob. Here we have $m_{1}=(1,2)$ and $m_{2}=(3,4)$. Note that $x_{1}\oplus
x_{2}\oplus w_{1}=0$ and has a cycle of even length while $x_{3}\oplus
x_{4}\oplus w_{2}=1$ has a cycle of odd length.

See 1.5 Proof :  Recall that by design, the connected component of the graph
corresponding to $m_{i}$ is bipartite if and only if $(Mx)_{i}\oplus w_{i}=0$.
Hence, the max cut has size $4t$ if and only if $(Mx)_{i}\oplus w_{i}=0$.
Otherwise, the connected component has an odd cycle, so that the max cut has
size at most $4t-1$. Connected components corresponding to unmatched elements
of $[n]$ have max cut size $3$.

Since $p\geq\frac{128t}{n}$, the probability that at least $\frac{np}{4t}$ of
the $\frac{n}{2t}$ edge labels are flipped is at least $\frac{99}{100}$. Thus,
in the NO case, the max cut has size at most

$(4t)\cdot\left(\frac{n}{2t}-\frac{np}{4t}\right)+(4t-1)\cdot\frac{np}{4t}+\frac{n}{2}\cdot
3=\frac{7n}{2}-\frac{np}{4t},$

with probability at least $\frac{99}{100}$. However, in the YES case the max
cut has size $\frac{n}{2t}(4t)+\frac{n}{2}\cdot 3=\frac{7n}{2}$. Thus, since
$p\leq 1$,

$\frac{7n/2}{7n/2-\frac{np}{4t}}\geq 1+\frac{p}{14t}.$

Therefore, any $\left(1+\frac{p}{14t}\right)$-approximation to the MAX-CUT
requires $\Omega\left(n^{1-1/t}p^{-1/t}\right)$ space. Finally, recall that
each of the ${O}\left(\frac{n}{t}\right)$ connected components has at most
$4t$ edges. $\Box$

###  4.2 MAX-MATCHING

Recall the following definition of the MAX-MATCHING problem.

######  Problem 4.2 (Maximum Matching)

Given an unweighted graph $G=(V,E)$, the goal is to output the maximum size of
a matching, that is a set of disjoint edges.

To show hardness of approximation of MAX-MATCHING in the streaming model, we
use a reduction similar to [BGM+19]. We use a reduction from noisy BHH. In the
reduction, each matching hyperedge $m_{i}$ corresponds to a gadget consisting
of two connected components of size $O(t)$. The key observation is that if
$m_{i}x\oplus w_{i}=0$, then the two components are of even size, and can be
perfectly matched, but if $m_{i}x\oplus w_{i}=1$, then the two components are
of odd size, and cannot be perfectly matched.

We reduce from Noisy Boolean Hidden Hypermatching with $\alpha=1/2$. Suppose
Alice is given a binary vector $x$ of length $n$ and Bob is a given a
hypermatching $M$ of size $n/2t$ on the vertex-set $[n]$, where each edge
contains $t$ vertices. Bob also receives a vector $w$ of length $n/2t$,
generated according to the YES or NO case of the $p$-noisy BHH (see Definition
3.2). The protocol to distinguish between the two cases slightly differs based
on the parity of $t$, but the core idea is the same. We begin by considering
odd $t$.

  * •

Alice creates the four vertices $a_{i}$, $b_{i}$, $c_{i}$, and $d_{i}$ for
each $i\in[n]$ corresponding to a coordinate of $x$.

  * •

If $x_{i}=0$, then Alice adds the single edges $(a_{i},b_{i})$, but if
$x_{i}=1$, then Alice instead adds the edge $(c_{i},d_{i})$.

  * •

For each hyperedge $m_{i}=(j_{i,1},\ldots,j_{i,t})$ of $M$, Bob adds a single
vertex $e_{i}$. Then, if $w_{i}=0$ Bob adds a clique between
$(b_{j_{i},1},b_{j_{i,2}},\ldots,b_{j_{i,t}})$ and another clique between
$(d_{j_{i},1},d_{j_{i,2}},\ldots,d_{j_{i,t}},e_{i})$. If $w_{i}=1$, Bob adds
the same two cliques, but moving $e_{i}$ from the second clique to the first.
Formally Bob adds the cliques
$(b_{j_{i},1},b_{j_{i,2}},\ldots,b_{j_{i,t}},e_{i})$ and
$(d_{j_{i},1},d_{j_{i,2}},\ldots,d_{j_{i,t}})$.

If $t$ is even, the protocol is very similar, but we state it here for
completeness:

  * •

Alice does the same thing as in the previous case: she creates the four
vertices $a_{i}$, $b_{i}$, $c_{i}$, and $d_{i}$ for each $i\in[n]$
corresponding to a coordinate of $x$.

  * •

If $x_{i}=0$, then Alice adds the single edges $(a_{i},b_{i})$, but if
$x_{i}=1$, then Alice instead adds the edge $(c_{i},d_{i})$.

  * •

For each hyperedge $m_{i}=(j_{i,1},\ldots,j_{i,t})$ of $M$, Bob adds two new
vertices $e_{i}$ and $f_{i}$. Then, if $w_{i}=0$ Bob adds a clique between
$(b_{j_{i},1},b_{j_{i,2}},\ldots,b_{j_{i,t}})$ and Bob adds another clique
between $(d_{j_{i},1},d_{j_{i,2}},\ldots,d_{j_{i,t}},e_{i},f_{i})$. If
$w_{i}=1$, Bob adds the same two cliques, but moving $e_{i}$ from the second
clique to the first. Formally Bob adds the cliques
$(b_{j_{i},1},b_{j_{i,2}},\ldots,b_{j_{i,t}},e_{i})$ and
$(d_{j_{i},1},d_{j_{i,2}},\ldots,d_{j_{i,t}},f_{i})$.

$a_{2}$$a_{1}$$b_{2}$$b_{1}$$a_{3}$$b_{3}$$x_{1}x_{2}x_{3}=011$$e_{1}$$c_{2}$$c_{1}$$d_{2}$$d_{1}$$c_{3}$$d_{3}$$a_{5}$$a_{4}$$b_{5}$$b_{4}$$a_{6}$$b_{6}$$e_{2}$$x_{4}x_{5}x_{6}=000$$c_{5}$$c_{4}$$d_{5}$$d_{4}$$c_{6}$$d_{6}$$w_{1}=1$$w_{2}=0$
Figure 2: An illustration of the graph construction for the maximum matching
reduction for $t=3$. Solid lines added by Alice, dashed lines added by Bob. On
the left side, we see the components corresponding to $m_{1}=\\{1,2,3\\}$.
Since $m_{1}x\oplus w_{1}=1$ this subgraph contributes $4$ to the maximum
matching. On the right side, we see the components corresponding to
$m_{2}=\\{4,5,6\\}$. Since $m_{2}x\oplus w_{2}=0$ this subgraph contributes
$5$ to the maximum matching.

See 1.6 Proof :  In this proof we focus on the case where $t$ is odd. The case
of even $t$ is similar.

Consider an edge of the hypermatching $M$: $m_{i}=(j_{i,1},\ldots,j_{i,t})$.
Consider further all the vertices related to this hyperedge, specifically
$a_{j}$, $b_{j}$, $c_{j}$, and $d_{j}$ for all
$j\in\\{j_{i,1},\ldots,j_{i,t}\\}$ as well as $e_{i}$. Suppose among the
values $x_{i,1},\ldots,x_{i,t}$ there are exactly $s$ ones (and
correspondingly exactly $t-s$ zeros). Let vertices of the form $a_{j_{i,k}}$
corresponding $x_{j_{i,k}}=0$ make up $A_{0}^{i}$, and ones corresponding to
$x_{j_{i,k}}=1$ make up $A_{1}^{i}$. Define $B_{0}^{i}$ and $B_{1}^{i}$,
$C_{0}^{i}$ and $C_{1}^{i}$, as well as $D_{0}^{i}$ and $D_{1}^{i}$
analogously. Note that $|A_{0}^{i}|=|B_{0}^{i}|=|C_{0}^{i}|=|D_{0}^{i}|=t-s$
and $|A_{1}^{i}|=|B_{1}^{i}|=|C_{1}^{i}|=|D_{1}^{i}|=s$.

Consider the case when $w_{i}=0$. Then, by the above construction, Bob puts
cliques between $B_{0}^{\cup}B_{1}^{i}$ and $D_{0}^{i}\cup
D_{1}^{i}\cup\\{e_{i}\\}$. Furthermore, recall that Alice puts an edge between
$a_{j}$ and $b_{j}$ when $x_{j}=0$ and an edge between $c_{j}$ and $d_{j}$
when $x_{1}$. Therefore, the connected components of this subgraph are
$A_{0}^{i}\cup B_{0}^{i}\cup B_{1}^{i}$ and $C_{1}^{i}\cup D_{0}^{i}\cup
D_{1}^{i}\cup\\{e_{i}\\}$, while vertices of $A_{1}^{\cup}C_{0}^{i}$ remain
isolated.

The size of the first component, $A_{0}^{i}\cup B_{0}^{i}\cup B_{1}^{i}$, is
$2t-s$. In the case when $s$ is even this has even size, and it is easy to
verify that it can be perfectly matched, so it contributes $t-s/2$ to the
total maximum matching size. On the other hand, if $s$ is odd, it contributes
at most $t-(s+1)/2$. Similarly, the second component, $C_{1}^{i}\cup
D_{0}^{i}\cup D_{1}^{i}\cup\\{e_{i}\\}$, has size $t+s+1$. When $s$ is even it
can be perfectly matched, contributing $(t+s+1)/2$ to the maximum matching
size. However, when $s$ is odd, it contributes only $(t+s)/2$. Overall, when
$s$ is even (corresponding to $m_{i}x\oplus w_{i}=0$) the maximum matching
size of the subgraph corresponding to $m_{i}$ is $(3t+1)/2$; however, when $s$
is odd (corresponding to $m_{i}x\oplus w_{i}=1$) it is only at most
$(3t-1)/2$.

A nearly identical analysis shows that when $w_{i}=1$, the maximum matching
size of the subgraph corresponding to $m_{i}x\oplus w_{i}=0$ is $(3t+1)/2$ and
the maximum matching size of the subgraph corresponding to $m_{i}x\oplus
w_{i}=1$ is $(3t-1)/2$. Finally, since $\alpha=1/2<1$ there will also be
vertices of $[n]$ that are not matched by any hyperedge in $M$. If some
$j\in[n]$ does not participate in any matching hyperedge, the corresponding
four vertices, $a_{j}$, $b_{j}$, $c_{j}$, and $d_{j}$ will have exactly one
edge between them regardless of the value of $x_{j}$.

Let us now consider the overall maximum matching size of the graph built by
Alice and Bob. In the YES case, it is always true that $m_{i}x\oplus w_{i}=0$.
Therefore, for $t$ odd, all the vertices corresponding to any hyperedge in $M$
will contribute exactly $(3t+1)/2$, while all remaining vertices will
contribute $1$, for a total of

$\frac{n}{2t}\cdot\frac{3t+1}{2}+\frac{n}{2}\cdot
1=\frac{5n}{4}+\frac{n}{4t}.$

In the NO case, since $p\geq\frac{128t}{n}$, the probability that at least
$\frac{np}{4t}$ of the $\frac{n}{2t}$ hyperedge labels are flipped is at least
$\frac{99}{100}$. Each flipped label decreases the contribution of the
corresponding component by $1$; thus, the maximum matching has size at most

$\frac{5n}{4}+\frac{n}{4t}-\frac{np}{4t},$

with probability at least $\frac{99}{100}$.

So the ratio between the two cases is at least

$\frac{5n/4+n/(4t)}{5n/4+n/(4t)-np/(4t)}\geq\frac{3n/2}{3n/2-np/(4t)}\geq
1+\frac{np}{6t}.$

The analysis for even $t$ is very similar. However, since we add the extra
vertex $f_{i}$ , all the vertices corresponding to any hyperedge $m_{i}$
satisfying $m_{i}x\oplus w_{i}=0$ will contribute exactly $(3t+2)/2$, while
hyperedges satisfying $m_{i}x\oplus w_{i}=1$ will contribute $3t/2$, and all
remaining vertices will contribute $1$. In the YES case this is a total of

$\frac{n}{2t}\cdot\frac{3t+2}{2}+\frac{n}{2}\cdot
1=\frac{5n}{4}+\frac{n}{2t}.$

In the NO case, each flipped label again decreases the contribution of the
corresponding component by $1$ so that the maximum matching has size at most

$\frac{5n}{4}+\frac{n}{2t}-\frac{np}{4t},$

with probability at least $\frac{99}{100}$. Thus, the ratio between the two
cases is at least

$\frac{5n/4+n/(2t)}{5n/4+n/(2t)-np/(4t)}\geq\frac{3n/2}{3n/2-np/(4t)}\geq
1+\frac{np}{6t}.$

Therefore, any $\left(1+\frac{p}{6t}\right)$-approximation to MAX-MATCHING
requires $\Omega\left(n^{1-1/t}p^{-1/t}\right)$ space. Finally, recall that
each of the connected components has at most $2t+1$ vertices. $\Box$

###  4.3 Maximum Acyclic Subgraph

In this section, we study the hardness of approximation for the maximum
acyclic subgraph on insertion-only streams.

######  Problem 4.3 (Maximum acyclic subgraph)

Given a directed graph $G=(V,E)$, the goal is to output the size of the
largest acyclic subgraph of $G$, where the size of a graph is defined to be
the number of edges in it.

To show hardness of approximation of maximum acyclic subgraph in the streaming
model, where the directed edges of $G$ arrive sequentially, we consider the
reduction of [GVV17], who created a subgraph with $8$ edges for each edge
$m_{i}$ in the input matching $M$ from BHM. The key property of the reduction
is that $(Mx)_{i}\oplus w_{i}=1$ corresponds to a subgraph with no cycles but
$(Mx)_{i}\oplus w_{i}=0$ corresponds to a subgraph with a cycle (see Figure
3). Hence, the former case allows $8$ edges in its maximum acyclic subgraph
while the latter case only allows for $7$ edges. We use the same reduction
from $p$-Noisy BHM with $\alpha=1/2$, so that there are $n/4$ matching edges.

In particular, suppose Alice is given a string $x\in\\{0,1\\}^{2n}$ and Bob is
given a matching of $[2n]$ of size $\alpha n$ with $\alpha=\frac{1}{2}$. To
distinguish between the two cases:

  * •

Alice and Bob consider a graph on $4(2n)=8n$ vertices and associate four
vertices $a_{i}$, $b_{i}$, $c_{i}$, and $d_{i}$ to each $i\in[2n]$, i.e.,
through a predetermined ordering of the vertices.

  * •

If $x_{i}=0$, then Alice creates the directed edges $(a_{i},b_{i})$ and
$(d_{i},c_{i})$, where we use the convention that $(v_{1},v_{2})$ represents
the directed edge $v_{1}\rightarrow v_{2}$. Otherwise if $x_{i}=1$, then Alice
adds the directed edges $(b_{i},a_{i})$ and $(c_{i},d_{i})$.

  * •

If $w_{i}=0$, Bob adds the four directed edges $(b_{y_{i}},a_{z_{i}})$,
$(b_{z_{i}},a_{y_{i}})$, $(d_{y_{i}},c_{z_{i}})$, and $(d_{z_{i}},c_{y_{i}})$
for each matching edge $m_{i}=(y_{i},z_{i})$ of $M$ from the $p$-Noisy Boolean
Hidden Matching problem. Otherwise if $w_{i}=1$, then Bob adds the four
directed edges $(b_{y_{i}},b_{z_{i}})$, $(a_{z_{i}},a_{y_{i}})$,
$(d_{y_{i}},d_{z_{i}})$, and $(c_{z_{i}},c_{y_{i}})$.

By design, the subgraph corresponding to $m_{i}$ has eight edges, but consists
of exactly one cycle when $x_{y_{i}}\oplus x_{z_{i}}\oplus w_{i}=0$ and zero
cycles when $x_{y_{i}}\oplus x_{z_{i}}\oplus w_{i}=1$. Finally, any unmmatched
subgraph contributes four edges due to Alice’s construction.

$a_{1}$$b_{1}$$a_{2}$$b_{2}$$c_{1}$$d_{1}$$c_{2}$$d_{2}$$x_{1}=0$,
$x_{2}=1$$a_{3}$$b_{3}$$a_{4}$$b_{4}$$c_{3}$$d_{3}$$d_{4}$$c_{4}$$x_{3}=1$,
$x_{4}=0$$w_{1}=1$$w_{2}=0$ Figure 3: Example of reduction from (Noisy)
Boolean Hidden Matching to Maximum Acyclic Subgraph. Solid lines added by
Alice, dashed lines added by Bob, and purple lines represent a cycle. Here we
have $m_{1}=(1,2)$ and $m_{2}=(3,4)$. Note that $x_{1}\oplus x_{2}\oplus
w_{1}=0$ has a cycle while $x_{3}\oplus x_{4}\oplus w_{2}=1$ has no cycles.

See 1.7 Proof :  Recall that the key property of the construction was that for
each $i\in[2n]$, the subgraph corresponding to $m_{i}$ has eight edges, but
consists of exactly one cycle when $x_{y_{i}}\oplus x_{z_{i}}\oplus w_{i}=0$
and zero cycles when $x_{y_{i}}\oplus x_{z_{i}}\oplus w_{i}=1$. Moreover, any
subgraph corresponding to an unmatched vertex (of which there are $n$) will
contribute two edges due to Alice’s construction. Thus for the YES case, when
$Mx\oplus w=0^{\alpha n}$, the maximum acyclic subgraph has size

$7\cdot\frac{n}{2}+2\cdot n=\frac{11n}{2}.$

In the NO case, the probability that at least $\frac{np}{4}$ matching labels
$w_{i}$ are flipped is at least $\frac{99}{100}$, since $p\geq\frac{128}{n}$
Therefore, in this case the maximum acyclic subgraph has size

$7\cdot\left(\frac{n}{2}-\frac{np}{4}\right)+8\cdot\frac{np}{4}+2\cdot
n=\frac{11n}{2}+\frac{np}{4},$

with probability at least $\frac{99}{100}$. For $p\leq 1$, it follows that

$\frac{11n/2+np/4}{11n/2}=1+\frac{p}{22}.$

Hence, any $\left(1+\frac{p}{22}\right)$-approximation to the size of the
maximum acyclic subgraph requires $\Omega\left(\sqrt{\frac{n}{p}}\right)$
space. $\Box$

###  4.4 Streaming Binary Tree Classification

In this section, we study the hardness of tree classification on insertion-
only streams. In this setting, a stream of edge-insertions in an underlying
graph with $n$ vertices arrive sequentially and the task is to classify
whether the resulting graph is isomorphic to a complete binary tree on $n$
vertices, or $\delta$-far from one.

######  Problem 4.4 (Graph Classification)

Given a stream for the set of edges between $n$ vertices, determine whether
the resulting graph induced by the stream is isomorphic to a complete binary
tree on $n$ vertices. Here we assume that the number of vertices is $2^{k}-1$
for some integer $k$.

[EHL+18] used the following construction to show hardness of approximation for
maximum matching size in the streaming model. Given an instance of Boolean
Hidden Matching with an input vector $x\in\\{0,1\\}^{2n}$, a binary string
$w\in\\{0,1\\}^{n}$, and a matching
$M=\\{(m_{1},m^{\prime}_{1}),(m_{2},m^{\prime}_{2}),\ldots,(m_{n},m^{\prime}_{n})\\}$
of $[2n]$, let $G$ be a graph with $6n$ vertices. Each bit $x_{i}$ is
associated with vertices $v_{i},v_{i,0},v_{i,1}$ in $G$. Alice connects vertex
$v_{i}$ to $v_{i,x_{i}}$ in $G$, e.g., if $v_{i}=0$ then Alice connects
$v_{i}$ to $v_{i,0}$ and if $v_{i}=1$ then Alice connects $v_{i}$ to
$v_{i,1}$. If $w_{i}=0$, then Bob creates an edge between $v_{m_{i},0}$ and
$v_{m^{\prime}_{i},1}$, as well as an edge between $v_{m_{i},1}$ and
$v_{m^{\prime}_{i},0}$. Otherwise if $w_{i}=1$, then Bob creates an edge
between $v_{m_{i},0}$ and $v_{m^{\prime}_{i},0}$, as well as an edge between
$v_{m_{i},1}$ and $v_{m^{\prime}_{i},1}$. Under this construction, if
$x_{m_{i}}\oplus x_{m^{\prime}_{i}}\oplus w_{i}=1$, then the six vertices
$v_{m_{i}},v_{m_{i},0},v_{m_{i},1},v_{m^{\prime}_{i}},v_{m^{\prime}_{i},0},v_{m^{\prime}_{i},1}$
form a path of length one and a path of length three. Otherwise, if
$x_{m_{i}}\oplus x_{m^{\prime}_{i}}\oplus w_{i}=0$, then the six vertices form
two paths of length two. We call this the EHLMO construction. See Figure 4 for
an illustration.

$v_{2}$$v_{2,0}$$v_{2,1}$$v_{4}$$v_{4,0}$$v_{4,1}$ (a) Suppose
$(m_{4},m^{\prime}_{4})=(2,3)$, $x_{2}=0$, $x_{3}=1$, and $w_{4}=0$. Then
$x_{2}\oplus x_{3}\oplus w_{4}=1$ and the construction forms a path of length
one and a path of length three. Solid lines added by Alice, dashed lines added
by Bob.

$v_{5}$$v_{5,0}$$v_{5,1}$$v_{7}$$v_{7,0}$$v_{7,1}$ (b) Suppose
$(m_{6},m^{\prime}_{6})=(5,7)$, $x_{5}=1$, $x_{7}=0$, and $w_{6}=1$. Then
$x_{5}\oplus x_{7}\oplus w_{6}=0$ and the construction forms two paths of
length two. Solid lines added by Alice, dashed lines added by Bob.

Figure 4: Construction of graph from instance of Boolean Hidden Matching.
Observe that in the case $Mx\oplus w=1^{n}$, $v_{5,1}$ and $v_{7,0}$ can be
embedded into the bottom layer of a complete binary tree to form another
complete binary tree, while in the $Mx\oplus w=0^{n}$ case, $v_{2,0}$ and
$v_{4,1}$ will induce a cycle in the graph.

To show hardness of classifying whether an underlying graph is a complete
binary tree, we use the EHLMO construction to embed an instance of $p$-Noisy
BHM of size $2n$ into the bottom layer of a binary tree with $4n-1$ total
nodes. For each $i\in[2n]$, the case $(Mx)_{i}\oplus w_{i}=0$ creates two
paths of length two. We use these two paths of length two to extend the binary
tree to an additional layer at two different nodes. On the other hand, the
case $(Mx)_{i}\oplus w_{i}=1$ creates a path of length one and a path of
length three. By using the same construction, the case $(Mx)_{i}\oplus
w_{i}=1$ thus results in a non-root node in the tree having degree two; hence
the resulting graph is a complete binary tree if and only if $Mx\oplus
w=0^{n}$.

Formally, let $n$ be a power of $2$ and let $T$ be a complete binary tree with
$2n$ leaves. Consider the EHLMO construction to embed an instance of the above
Noisy Boolean Hidden Matching problem with noise $p=\frac{4}{n}$ into the
bottom layer of a tree, so that in the case where $Mx\oplus w=0^{n}$, the
resulting graph is a complete binary tree, while in the case $Mx\oplus w\neq
0^{n}$, the resulting graph contains a cycle. More formally:

  * •

Alice creates a complete $6n$ vertices $v_{i},v_{i,0},v_{i,1}$ for each
$i\in[2n]$.

  * •

Alice creates a complete binary tree with leaves $v_{i,x_{i}}$ for $i\in[2n]$
(and new non-leaf vertices, distinct from any previously created).

  * •

Alice also creates an edge between vertices $v_{i}$ and $v_{i,x_{i}}$ for each
$i\in[2n]$.

  * •

For each edge $m_{i}=(y_{i},z_{i})$ of the matching $M$ with $i\in[n]$, Bob
creates an edge between $v_{y_{i},0}$ and $v_{z_{i},w_{i}\oplus 1}$ as well as
an edge between $v_{y_{i},1}$ and $v_{z_{i},w_{i}}$.

See 1.8 Proof :  We claim that the resulting construction is a complete binary
tree in the case where $Mx\oplus w=0^{n}$ and is not a complete binary tree in
the case where $Mx\oplus w\neq 0^{n}$, which happens with high constant
probability in the NO case of the underlying $p$-Noisy BHM instance. We first
consider the YES case, i.e., $Mx\oplus w=0^{n}$, so that $x_{y_{i}}\oplus
x_{z_{i}}\oplus w_{i}=0$ for all $i\in[n]$, where we recall that the edge
$m_{i}=(y_{i},z_{i})$. Observe that if $w_{i}=0$ and $x_{y_{i}}\oplus
x_{z_{i}}\oplus w_{i}=0$, then $x_{y_{i}}\neq x_{z_{i}}$. Since Bob connects
$v_{y_{i},0}$ with $v_{z_{i},0}$ and $v_{y_{i},1}$ with $v_{z_{i},1}$ if
$w_{i}=1$, then $v_{y_{i},x_{y_{i}}}$ will be the middle node of a path of
length two. Similarly, $v_{z_{i},x_{z_{i}}}$ will be the middle node of a path
of length two. Hence, the resulting graph will be a complete binary tree.

In the NO case, each $i\in[n]$ has $x_{y_{i}}\oplus x_{z_{i}}\oplus w_{i}=1$
with probability $\frac{4}{n}$. Let $\mathcal{E}$ be the event that we are in
the NO case and there exists some $i\in[n]$ such that $x_{y_{i}}\oplus
x_{z_{i}}\oplus w_{i}=1$. Since we are in the NO case with probability
$\frac{1}{2}$, then

$\mathbf{Pr}\left[\mathcal{E}\right]=\frac{1}{2}\left(1-\left(1-\frac{4}{n}\right)^{n}\right)>\frac{1}{2}\left(1-\frac{1}{e^{4}}\right)\geq\frac{15}{32}.$

Conditioned on $\mathcal{E}$, Bob connects $v_{y_{i},0}$ with $v_{z_{i},1}$
and $v_{y_{i},1}$ with $v_{z_{i},0}$, so there exists an edge between
$v_{y_{i},x_{y_{i}}}$ and $v_{z_{i},x_{z_{i}}}$ and the resulting graph
contains a cycle.

Hence, any algorithm $\mathcal{A}$ that classifies whether the underlying
graph is a complete binary tree with probability $\frac{3}{4}$ also solves the
Noisy Boolean Hidden Matching problem with probability at least
$\frac{1}{2}\frac{3}{4}\cdot\frac{1}{2}\cdot\frac{15}{32}=\frac{39}{64}>\frac{2}{3}$,
where the first term in the summand represents the probability of success in
the YES case and the second term in the summand represents the probability of
success in the NO case. Thus by Theorem 3.16 with $t=2$, $\mathcal{A}$ uses
$\Omega\left(\sqrt{\frac{n}{p}}\right)=\Omega(n)$ space. $\Box$

We note that Theorem 1.8 also follows by a reduction from the standard INDEX
communication problem. The following more general Theorem 1.10, however, does
not. It follows by the same reduction we use for Theorem 1.10 and follows from
a nearly identical proof, with the only change being that the variable $p$ is
set to $\epsilon$ in the reduction from $p$-Noisy BHM.

See 1.10 Proof :  We use the identical reduction to the proof of Theorem 1.8,
with the parameter $p$ set to $\epsilon$ instead of $\tfrac{4}{n}$. It is
still true that in the YES case the resulting graph is isomorphic to a
complete binary tree. In the NO case, of the $n$ edge labels, we expect
$pn=\epsilon n$ of edge labels to be flipped. In fact, since
$\epsilon>\tfrac{64}{n}$, at least $\epsilon n/2$ edges are flipped with
probability at least $99/100$. This results in $\epsilon n/2$ disjoint cycles
in the underlying graph. As a result, the underlying graph requires at least
$\epsilon n/2$ edge insertions or deletions to be transformed into a complete
binary tree (or in fact a tree of any kind). Since $|V|=8n-1$, this means the
underlying graph in the NO case is at least $\epsilon/16$ far from being a
complete binary tree.

The statement of the theorem then follows by Theorem 3.16. $\Box$

## Acknowledgements

Michael Kapralov and Jakab Tardos would like to thank support from ERC
Starting Grant 759471. David P. Woodruff and Samson Zhou would like to thank
support from NSF grant No. CCF-181584 and a Simons Investigator Award.

## References

  * [AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 459–467, 2012.
  * [AGM12b] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 5–14, 2012.
  * [AKL17] Sepehr Assadi, Sanjeev Khanna, and Yang Li.  On estimating maximum matching size in graph streams.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1723–1742, 2017.
  * [AKLY16] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev.  Maximum matchings in dynamic graph streams and the simultaneous communication model.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1345–1364, 2016.
  * [AKSY20] Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu.  Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 354–364, 2020.
  * [AN21] Sepehr Assadi and Vishvajeet N.  Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma.  In STOC: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 612–625, 2021.
  * [Ass21] Sepehr Assadi.  Personal communication, 2021.
  * [BGM+19] Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, and Samson Zhou.  Structural results on matching estimation with applications to streaming.  Algorithmica, 81(1):367–392, 2019.
  * [BHNT15] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis.  Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 173–182, 2015.
  * [BJK08] Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis.  Exponential separation of quantum and classical one-way communication complexity.  SIAM J. Comput., 38(1):366–384, 2008.
  * [BJKS04] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar.  An information statistics approach to data stream and communication complexity.  J. Comput. Syst. Sci., 68(4):702–732, 2004.
  * [BR14] Mark Braverman and Anup Rao.  Information equals amortized communication.  IEEE Trans. Inf. Theory, 60(10):6058–6069, 2014.
  * [CCE+16] Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova.  Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1326–1344, 2016.
  * [CCHM15] Rajesh Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh.  Parameterized streaming: Maximal matching and vertex cover.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1234–1251, 2015.
  * [CFPS20] Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler.  Testable properties in general graphs and random order streaming.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, 2020.
  * [CGSV21] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy.  Approximability of all boolean csps in the dynamic streaming setting.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2021.  (to appear).
  * [CGV20] Chi-Ning Chou, Sasha Golovnev, and Santhoshini Velusamy.  Optimal streaming approximations for all boolean max-2csps and max-ksat.  In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 330–341, 2020.
  * [CS14] Michael Crouch and Daniel S. Stubbs.  Improved streaming algorithms for weighted matching, via unweighted matching.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 96–104, 2014.
  * [EHL+18] Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak.  Streaming algorithms for estimating the matching size in planar graphs and beyond.  ACM Trans. Algorithms, 14(4):48:1–48:23, 2018.
  * [FKM+05] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  Theor. Comput. Sci., 348(2-3):207–216, 2005.
  * [FKM+08] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  Graph distances in the data-stream model.  SIAM J. Comput., 38(5):1709–1727, 2008.
  * [GKdW06] Dmitry Gavinsky, Julia Kempe, and Ronald de Wolf.  Exponential separation of quantum and classical one-way communication complexity for a boolean function.  CoRR, abs/quant-ph/0607174, 2006.
  * [GKK+08] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf.  Exponential separation for one-way quantum communication complexity, with applications to cryptography.  SIAM J. Comput., 38(5):1695–1708, 2008.
  * [GMT15] Sudipto Guha, Andrew McGregor, and David Tench.  Vertex and hyperedge connectivity in dynamic graph streams.  In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS, pages 241–247, 2015.
  * [GT19] Venkatesan Guruswami and Runzhou Tao.  Streaming hardness of unique games.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 5:1–5:12, 2019.
  * [GVV17] Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy.  Streaming complexity of approximating max 2csp and max acyclic subgraph.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 81, pages 8:1–8:19, 2017\.
  * [HP19] Zengfeng Huang and Pan Peng.  Dynamic graph stream algorithms in o(n) space.  Algorithmica, 81(5):1965–1987, 2019.
  * [JPY12] Rahul Jain, Attila Pereszlényi, and Penghui Yao.  A direct product theorem for bounded-round public-coin randomized communication complexity.  CoRR, abs/1201.1666, 2012.
  * [Kap13] Michael Kapralov.  Better bounds for matchings in the streaming model.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1679–1697, 2013.
  * [KK15] Dmitry Kogan and Robert Krauthgamer.  Sketching cuts in graphs and hypergraphs.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS, pages 367–376, 2015.
  * [KK19] Michael Kapralov and Dmitry Krachun.  An optimal space lower bound for approximating MAX-CUT.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 277–288, 2019.
  * [KKP18] John Kallaugher, Michael Kapralov, and Eric Price.  The sketching complexity of graph and hypergraph counting.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 556–567, 2018\.
  * [KKS14] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.  Approximating matching size from random streams.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 734–751, 2014.
  * [KKS15] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.  Streaming lower bounds for approximating MAX-CUT.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1263–1282, 2015.
  * [KKSV17] Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker.  $(1+\omega(1))$-approximation to MAX-CUT requires linear space.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1703–1722, 2017.
  * [KLM+17] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford.  Single pass spectral sparsification in dynamic streams.  SIAM J. Comput., 46(1):456–477, 2017.
  * [KP17] John Kallaugher and Eric Price.  A hybrid sampling scheme for triangle counting.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1778–1797, 2017.
  * [KR06] Iordanis Kerenidis and Ran Raz.  The one-way communication complexity of the boolean hidden matching problem.  CoRR, abs/quant-ph/0607173, 2006.
  * [KW14] Michael Kapralov and David P. Woodruff.  Spanners and sparsifiers in dynamic streams.  In ACM Symposium on Principles of Distributed Computing, PODC, pages 272–281, 2014.
  * [LW16] Yi Li and David P. Woodruff.  On approximating functions of the singular values in a stream.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 726–739, 2016.
  * [MMPS17] Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler.  Testable bounded degree graph properties are random order streamable.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP, pages 131:1–131:14, 2017.
  * [NY19] Jelani Nelson and Huacheng Yu.  Optimal lower bounds for distributed and streaming spanning forest computation.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1844–1860, 2019.
  * [PS17] Ami Paz and Gregory Schwartzman.  A (2 + $\epsilon$-approximation for maximum weight matching in the semi-streaming model.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2153–2161, 2017.
  * [SW15] Xiaoming Sun and David P. Woodruff.  Tight bounds for graph problems in insertion streams.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 435–448, 2015.
  * [VY11] Elad Verbin and Wei Yu.  The streaming complexity of cycle counting, sorting by reversals, and other problems.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 11–25, 2011.