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

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.