TY - JOUR

T1 - A separation theorem in property testing

AU - Alon, Noga

AU - Shapira, Asaf

N1 - Funding Information:
* Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.
Funding Information:
† This work forms part of the author’s Ph.D. thesis. Research supported by a Charles Clore Foundation Fellowship and by an IBM Ph.D. Fellowship.

PY - 2008/5

Y1 - 2008/5

N2 - Consider the following seemingly rhetorical question: Is it crucial for a property-tester to know the error parameter ε in advance? Previous papers dealing with various testing problems, suggest that the answer may be no, as in these papers there was no loss of generality in assuming that ε is given as part of the input, and is not known in advance. Our main result in this paper, however, is that it is possible to separate a natural model of property testing in which ε is given as part of the input from the model in which ε is known in advance (without making any computational hardness assumptions). To this end, we construct a graph property P, which has the following two properties: (i) There is no tester for P accepting ε as part of the input, whose number of queries depends only on ε. (ii) For any fixed ε, there is a tester for P (that works only for that specific ε), which makes a constant number of queries. Interestingly, we manage to construct a separating property P, which is combinatorially natural as it can be expressed in terms of forbidden subgraphs and also computationally natural as it can be shown to belong to coNP. The main tools in this paper are efficiently constructible graphs of high girth and high chromatic number, a result about testing monotone graph properties, as well as basic ideas from the theory of recursive functions. Of independent interest is a precise characterization of the monotone graph properties that can be tested with ε being part of the input, which we obtain as one of the main steps of the paper.

AB - Consider the following seemingly rhetorical question: Is it crucial for a property-tester to know the error parameter ε in advance? Previous papers dealing with various testing problems, suggest that the answer may be no, as in these papers there was no loss of generality in assuming that ε is given as part of the input, and is not known in advance. Our main result in this paper, however, is that it is possible to separate a natural model of property testing in which ε is given as part of the input from the model in which ε is known in advance (without making any computational hardness assumptions). To this end, we construct a graph property P, which has the following two properties: (i) There is no tester for P accepting ε as part of the input, whose number of queries depends only on ε. (ii) For any fixed ε, there is a tester for P (that works only for that specific ε), which makes a constant number of queries. Interestingly, we manage to construct a separating property P, which is combinatorially natural as it can be expressed in terms of forbidden subgraphs and also computationally natural as it can be shown to belong to coNP. The main tools in this paper are efficiently constructible graphs of high girth and high chromatic number, a result about testing monotone graph properties, as well as basic ideas from the theory of recursive functions. Of independent interest is a precise characterization of the monotone graph properties that can be tested with ε being part of the input, which we obtain as one of the main steps of the paper.

UR - http://www.scopus.com/inward/record.url?scp=49649129024&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49649129024&partnerID=8YFLogxK

U2 - 10.1007/s00493-008-2321-1

DO - 10.1007/s00493-008-2321-1

M3 - Article

AN - SCOPUS:49649129024

VL - 28

SP - 261

EP - 281

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 3

ER -