## On the Communication Complexity Methodology for Proving
Lower Bounds on the Query Complexity of Property Testing

#### Webpage for a paper by Oded Goldreich

#### Abstract

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.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.