A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via ``simple combining operators'')
and also hinted towards a more general formulation, which we spell out in this paper.

A special case of the general formulation proceeds as follows:
In order to derive a lower bound on testing the property $\Pi$, one presents a mapping $F$ of pairs of inputs $(x,y)\in\{0,1\}^{n+n}$
for a two-party communication problem $\Psi$ to $\ell(n)$-bit long inputs for $\Pi$ such that $(x,y)\in\Psi$ implies $F(x,y)\in\Pi$ and $(x,y)\not\in\Psi$ implies that $F(x,y)$ is far from $\Pi$. Let $f_i(x,y)$ be the $i^\xth$ bit of $F(x,y)$, and suppose that $B$ is an upper bound on the (deterministic) communication complexity of each $f_i$ and that $C$ is a lower bound on the randomized communication complexity of $\Psi$. Then, testing $\Pi$ requires at least $C/B$ queries.

The foregoing formulation is generalized by considering randomized protocols (with small error) for computing the $f_i$'s.
In contrast, the restricted formulation (via ``simple combining operators'') requires that each $f_i(x,y)$ be a function of $x_i$ and $y_i$ only, and uses $B=2$ for the straightforward computation of $f_i$.

We show that the general formulation cannot yield significantly stronger lower bounds than those that can be obtained by the restricted formulation.
Nevertheless, we advocate the use of the general formulation, because we believe that it is easier to work with.
Following Blais et al., we also describe a version of the methodology for nonadaptive testers and one-way communication complexity.

We got informed that, prior to our work,
Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev
took a move in the same direction.
Specifically, to streamline their proof, they replaced the simple
combining operators of~\cite[Def.~2.3]{BBM}
with a ``one-bit one-way combining operator''
(see Definition~2.4 and Lemma~2.5 in~\cite{BRY}).

\bibitem{BRY} E.~Blais, S.~Raskhodnikova, and G.~Yaroslavtsev.
\newblock Lower Bounds for Testing Properties of Functions on
Hypergrid Domains.
\newblock {\em ECCC}, TR13-036, March 2013.

Hence, the second sentence in the fourth paragraph of our
paper is inaccurate and we added a footnote to correct it.
The revised paragraph reads as follows ---

While Blais, Brody, and Matulef hint towards the formulation that
we will present here (see a few lines before~\cite[Def.~2.3]{BBM}),
they preferred to present a more restricted formulation,
which is pivoted at ``simple combining operators''
(see~\cite[Def.~2.3]{BBM}).
Furthermore, it seems that this restricted formulation
is the one that is disseminating in the literature.%
\footnote{A notable exception is provided by the recent
work of~\cite{BRY}: To streamline their proof, they take
a move that is analogous to ours by replacing the simple
combining operators of~\cite[Def.~2.3]{BBM}
with a ``one-bit one-way combining operator''
(see Definition~2.4 and Lemma~2.5 in~\cite{BRY}).}
%
The main purpose of this paper is to explicitly present
a more general and flexible formulation,
and demonstrate the ease of using it
(in comparison to the use of the restricted formulation).

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via ``simple combining operators'')
and also hinted towards a more general formulation, which we spell out in this paper.

A special case of the general formulation proceeds as follows:
In order to derive a lower bound on testing the property $\Pi$, one presents a mapping $F$ of pairs of inputs $(x,y)\in\{0,1\}^{n+n}$
for a two-party communication problem $\Psi$ to $\ell(n)$-bit long inputs for $\Pi$ such that $(x,y)\in\Psi$ implies $F(x,y)\in\Pi$ and $(x,y)\not\in\Psi$ implies that $F(x,y)$ is far from $\Pi$. Let $f_i(x,y)$ be the $i^\xth$ bit of $F(x,y)$, and suppose that $B$ is an upper bound on the (deterministic) communication complexity of each $f_i$ and that $C$ is a lower bound on the randomized communication complexity of $\Psi$. Then, testing $\Pi$ requires at least $C/B$ queries.

The foregoing formulation is generalized by considering randomized protocols (with small error) for computing the $f_i$'s.
In contrast, the restricted formulation (via ``simple combining operators'') requires that each $f_i(x,y)$ be a function of $x_i$ and $y_i$ only, and uses $B=2$ for the straightforward computation of $f_i$.

We show that the general formulation cannot yield significantly stronger lower bounds than those that can be obtained by the restricted formulation.
Nevertheless, we advocate the use of the general formulation, because we believe that it is easier to work with.
Following Blais et al., we also describe a version of the methodology for nonadaptive testers and one-way communication complexity.

We augmented the current version with a suggestion by David Woodruff,
which relates nonadaptive testers and simultaneous communication
(see Theorem 5.2).
This led us to further generalize the methodology (for general testers)
by considering multi-party communication complexity (see Appendix).

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via ``simple combining operators'')
and also hinted towards a more general formulation, which we spell out in this paper.

A special case of the general formulation proceeds as follows:
In order to derive a lower bound on testing the property $\Pi$, one presents a mapping $F$ of pairs of inputs $(x,y)\in\{0,1\}^{n+n}$
for a two-party communication problem $\Psi$ to $\ell(n)$-bit long inputs for $\Pi$ such that $(x,y)\in\Psi$ implies $F(x,y)\in\Pi$ and $(x,y)\not\in\Psi$ implies that $F(x,y)$ is far from $\Pi$. Let $f_i(x,y)$ be the $i^\xth$ bit of $F(x,y)$, and suppose that $B$ is an upper bound on the (deterministic) communication complexity of each $f_i$ and that $C$ is a lower bound on the randomized communication complexity of $\Psi$. Then, testing $\Pi$ requires at least $C/B$ queries.

The foregoing formulation is generalized by considering randomized protocols (with small error) for computing the $f_i$'s.
In contrast, the restricted formulation (via ``simple combining operators'') requires that each $f_i(x,y)$ be a function of $x_i$ and $y_i$ only, and uses $B=2$ for the straightforward computation of $f_i$.

We show that the general formulation cannot yield significantly stronger lower bounds than those that can be obtained by the restricted formulation.
Nevertheless, we advocate the use of the general formulation, because we believe that it is easier to work with.
Following Blais et al., we also describe a version of the methodology for nonadaptive testers and one-way communication complexity.