@inbook {IOPORT.06569690,
author = {Tell, Roei},
title = {On being far from far and on dual problems in property testing (extended abstract).},
year = {2016},
booktitle = {Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS'16, Cambridge, MA, USA, January 14--16, 2016},
isbn = {978-1-4503-4057-1},
pages = {103-110},
publisher = {New York, NY: Association for Computing Machinery (ACM)},
doi = {10.1145/2840728.2840732},
abstract = {Summary: This work studies a new type of problems in property testing, called dual problems. For a set in a metric space and $\delta > 0$, denote by $\mathcal{F}_{\delta}(\Pi)$ the set of elements that are $\delta$-far from. Then, in property testing, a {$\delta$}-tester for {$\Pi$} is required to accept inputs from 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.},
identifier = {06569690},
}