ECCC-Report TR15-072https://eccc.weizmann.ac.il/report/2015/072Comments and Revisions published for TR15-072en-usThu, 19 Oct 2017 16:47:50 +0300
Revision 4
| On Being Far from Far and on Dual Problems in Property Testing |
Roei Tell
https://eccc.weizmann.ac.il/report/2015/072#revision4This work studies a new type of problems in property testing, called dual problems. For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. Then, in property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing the set of ``no'' instances, that is $\mathcal{F}_\delta(\Pi)$: A $\delta$-tester for $\mathcal{F}_\delta(\Pi)$ needs to accept inputs from $\mathcal{F}_\delta(\Pi)$ and reject inputs that are $\delta$-far from $\mathcal{F}_\delta(\Pi)$; that is, it rejects inputs from $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$. When $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ the dual problem is essentially equivalent to the original one, but this equality does not hold in general.
Many dual problems constitute appealing testing problems that are interesting by themselves. In this work we study sets of the form $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$, and apply this study to investigate several natural dual problems. In particular, we derive lower bounds and upper bounds on the query complexity of several classes of natural dual problems: These include dual problems of properties of functions (e.g., testing error-correcting codes and testing monotone functions), of properties of distributions (e.g., testing equivalence to a known distribution), and of various graph properties in the dense graph model and in the bounded-degree model. We also show that testing any dual problem with one-sided error is either trivial or requires a linear number of queries.Thu, 19 Oct 2017 16:47:50 +0300https://eccc.weizmann.ac.il/report/2015/072#revision4
Revision 3
| On Being Far from Far and on Dual Problems in Property Testing |
Roei Tell
https://eccc.weizmann.ac.il/report/2015/072#revision3This work studies a new type of problems in property testing, called dual problems. For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. Then, in property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing the set of ``no'' instances, that is $\mathcal{F}_\delta(\Pi)$: A $\delta$-tester for $\mathcal{F}_\delta(\Pi)$ needs to accept inputs from $\mathcal{F}_\delta(\Pi)$ and reject inputs that are $\delta$-far from $\mathcal{F}_\delta(\Pi)$; that is, it rejects inputs from $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$. When $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ the dual problem is essentially equivalent to the original one, but this equality does not hold in general.
Many dual problems constitute appealing testing problems that are interesting by themselves. In this work we study sets of the form $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$, and apply this study to investigate several natural dual problems. In particular, we derive lower bounds and upper bounds on the query complexity of several classes of natural dual problems: These include dual problems of properties of functions (e.g., testing error-correcting codes and testing monotone functions), of properties of distributions (e.g., testing equivalence to a known distribution), and of various graph properties in the dense graph model and in the bounded-degree model. We also show that testing any dual problem with one-sided error is either trivial or requires a linear number of queries.Thu, 03 Dec 2015 14:39:47 +0200https://eccc.weizmann.ac.il/report/2015/072#revision3
Revision 2
| On Being Far from Far and on Dual Problems in Property Testing |
Roei Tell
https://eccc.weizmann.ac.il/report/2015/072#revision2This work studies a new type of problems in property testing, called dual problems. For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. Then, in property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing the set of ``no'' instances, that is $\mathcal{F}_\delta(\Pi)$: A $\delta$-tester for $\mathcal{F}_\delta(\Pi)$ needs to accept inputs from $\mathcal{F}_\delta(\Pi)$ and reject inputs that are $\delta$-far from $\mathcal{F}_\delta(\Pi)$; that is, it rejects inputs from $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$. When $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ the dual problem is essentially equivalent to the original one, but this equality does not hold in general.
Many dual problems constitute appealing testing problems that are interesting by themselves. In this work we study sets of the form $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$, and apply this study to investigate several natural dual problems. In particular, we derive lower bounds and upper bounds on the query complexity of several classes of natural dual problems: These include dual problems of properties of functions (e.g., testing error-correcting codes and testing monotone functions), of properties of distributions (e.g., testing equivalence to a known distribution), and of various graph properties in the dense graph model and in the bounded-degree model. We also show that testing any dual problem with one-sided error is either trivial or requires a linear number of queries.Sun, 29 Nov 2015 11:50:15 +0200https://eccc.weizmann.ac.il/report/2015/072#revision2
Revision 1
| On Being Far from Far and on Dual Problems in Property Testing |
Roei Tell
https://eccc.weizmann.ac.il/report/2015/072#revision1For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing the set of ``no'' instances, that is $\mathcal{F}_\delta(\Pi)$: A $\delta$-tester for $\mathcal{F}_\delta(\Pi)$ needs to accept inputs from $\mathcal{F}_\delta(\Pi)$ and reject inputs that are $\delta$-far from $\mathcal{F}_\delta(\Pi)$, that is reject inputs from $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$. When $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ the two problems are essentially equivalent, but this equality does not hold in general. Many dual problems constitute appealing testing problems that are interesting by themselves.
In this work we study sets of the form $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$, and apply this study to investigate dual problems in property testing. In particular, we present conditions on a metric space, on $\delta$, and on a set $\Pi$ that are sufficient and/or necessary in order for the equality $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ to hold. Using these conditions, we derive bounds on the query complexity of several classes of natural dual problems: These include dual problems of properties of functions (e.g., testing error-correcting codes and testing monotone functions), of properties of distributions (e.g., testing equivalence to a known distribution), and of various graph properties in the dense graph model and in the bounded-degree model. We also show that testing any dual problem with one-sided error is either trivial or requires a linear number of queries.Tue, 04 Aug 2015 19:24:29 +0300https://eccc.weizmann.ac.il/report/2015/072#revision1
Paper TR15-072
| On Being Far from Far and on Dual Problems in Property Testing |
Roei Tell
https://eccc.weizmann.ac.il/report/2015/072For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing the set of ``no'' instances, that is $\mathcal{F}_\delta(\Pi)$: A $\delta$-tester for $\mathcal{F}_\delta(\Pi)$ needs to accept inputs from $\mathcal{F}_\delta(\Pi)$ and reject inputs that are $\delta$-far from $\mathcal{F}_\delta(\Pi)$, that is reject inputs from $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$. When $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ the two problems are essentially equivalent, but this equality does not hold in general.
In this work we study sets of the form $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$, and apply this study to investigate dual problems in property testing. In particular, we present conditions on a metric space, on $\delta$, and on a set $\Pi$ that are sufficient and/or necessary in order for the equality $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ to hold. Using these conditions, we derive bounds on the query complexity of several classes of natural dual problems in property testing. These include the dual problems of testing codes with constant relative distance, testing monotone functions, testing whether a distribution is identical to a known distribution, and testing several graphs properties in the dense graph model. In some cases, our results are obtained by showing that $\Pi=\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$; in other cases, the results follow by showing that inputs in $\mathcal{F}_\delta(\mathcal{F}_\delta(\Pi))$ are sufficiently close to $\Pi$. We also show that testing any dual problem with one-sided error is either trivial or requires a linear number of queries.Thu, 23 Apr 2015 23:47:39 +0300https://eccc.weizmann.ac.il/report/2015/072