A theorem of Goldreich and Trevisan [1] on property testing in the dense graph model states the following (docusing on the one-sided part):

Suppose there exists a one-sided testing graph algorithm for a property $\mathcal{P}$ with query complexity $q$. Then, the "canonical tester" which looks at a randomly chosen subgraph of $2q$ vertices and queries all $\binom{2q}{2}$ possible edges and checks if the resulting subgraph satisfies a (related) property $\mathcal{P}'$ is a one-sided tester for $\mathcal{P}$.

The way I've always understood that result is that one can (almost) wlog focus on such "canonical" testers, and try to establish a bound on the probability to detect violations on a randomly chosen subgraphs. For triangle freeness, or more generally subgraph freeness, for instance, this uses removal lemmas to bound the density of forbidden subgraphs.

My question is: has this theorem been used to do the converse? Come up with any one-sided testing algorithm (possibly adaptive, etc) in order to derive a lower bound on the density of violations in a graph?

Are there examples where this theorem has been used to derive removal-type lemmas from one-sided algorithms, rather than the other way around?

[1] Goldreich, Oded; Trevisan, Luca. Three theorems regarding testing graph properties. Random Structures Algorithms 23 (2003), no. 1, 23--57.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.