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.

A significant reorganization and trimming of the paper. The paper is now more concise, and (hopefully) much more reader-friendly.

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.

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

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.

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.

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.

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

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.