A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexityof 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 , one presents a mapping F of pairs of inputs (xy)01n+n for a two-party communication problem to (n)-bit long inputs for such that (xy) implies F(xy) and (xy) implies that F(xy) is far from . Let fi(xy) be the ixth bit of F(xy) , and suppose that B is an upper bound on the (deterministic) communication complexity of each fi and that C is a lower bound on the randomized communication complexity of . Then, testing requires at least CB queries.The foregoing formulation is generalized by considering randomized protocols (with small error) for computing the fi's.In contrast, the restricted formulation (via ``simple combining operators'') requires that each fi(xy) be a function of xi and yi only, and uses B=2 for the straightforward computation of fi.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.
展开▼
