ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR15-072 | 3rd December 2015 14:39

On Being Far from Far and on Dual Problems in Property Testing

RSS-Feed




Revision #3
Authors: Roei Tell
Accepted on: 3rd December 2015 14:39
Downloads: 322
Keywords: 


Abstract:

This 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.



Changes to previous version:

Addition: A graph property in the dense graph model whose dual problem to not reduce to tolerant testing.


Revision #2 to TR15-072 | 29th November 2015 11:49

On Being Far from Far and on Dual Problems in Property Testing





Revision #2
Authors: Roei Tell
Accepted on: 29th November 2015 11:50
Downloads: 204
Keywords: 


Abstract:

This 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.



Changes to previous version:

Added a section and a corresponding introduction part about generalized dual problems (with two distance parameters); added an example of a property whose dual problem does not reduce to tolerant testing; simplified the proof for the dual problem of k-colorable graphs; revised the open questions section; some typo fixes and minor revisions.


Revision #1 to TR15-072 | 4th August 2015 19:24

On Being Far from Far and on Dual Problems in Property Testing





Revision #1
Authors: Roei Tell
Accepted on: 4th August 2015 19:24
Downloads: 330
Keywords: 


Abstract:

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$. 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.



Changes to previous version:

Added new results about testing dual problems in the bounded-degree graphs model. Revised the introduction.


Paper:

TR15-072 | 23rd April 2015 21:36

On Being Far from Far and on Dual Problems in Property Testing





TR15-072
Authors: Roei Tell
Publication: 23rd April 2015 23:47
Downloads: 387
Keywords: 


Abstract:

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$. 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.



ISSN 1433-8092 | Imprint