  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.
