Asymmetry in Property Testing Definition Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$.

More precisely we want to distinguish
1)  $x \in L$
2)  $x$ epsilon-far from every $y \in L$.

Here, epsilon-far is generally taken to mean hamming distance.

I don't quite understand why property testing has this asymmetric definition, i.e. why don't we want 1) to be  "$x$ epsilon-close to some $y \in L$"
There is a notion of property testing in which 1) is indeed "x is epsilon'-close to some y in L" (where epsilon' &lt; epsilon), which is called tolerant property testing. In general, tolerant testers are harder to design than property tester (since property testing is a special case).

In many cases, one can actually construct a one-sided error property tester which accepts all x in L with probability 1. These constructions rely on locally testing some sort of condition which things in L satisfy globally (and hence anything in L always passes) whereas inputs that are far away from L are unlikely to pass. For example, say you want to test whether a boolean function is linear, i.e. f(x) + f(y) = f(x+y). A natural test would be to randomly pick two points x,y and verify that f(x) + f(y) = f(x+y). Any f that is already linear always passes this test, and one can easily show that those f which are far from being linear fail this test with high constant probability. The problem with detecting if f is close to being linear comes from the fact that the probability of detecting this is too small.