ECCC-Report TR13-073https://eccc.weizmann.ac.il/report/2013/073Comments and Revisions published for TR13-073en-usWed, 17 Jul 2013 18:18:55 +0300
Revision 2
| On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2013/073#revision2A 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.Wed, 17 Jul 2013 18:18:55 +0300https://eccc.weizmann.ac.il/report/2013/073#revision2
Revision 1
| On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2013/073#revision1A 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.Sat, 08 Jun 2013 16:28:56 +0300https://eccc.weizmann.ac.il/report/2013/073#revision1
Paper TR13-073
| On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2013/073A 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.Tue, 14 May 2013 14:45:02 +0300https://eccc.weizmann.ac.il/report/2013/073