6
$\begingroup$

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$"

$\endgroup$
11
$\begingroup$

There is a notion of property testing in which 1) is indeed "x is epsilon'-close to some y in L" (where epsilon' < 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.

$\endgroup$
  • 2
    $\begingroup$ Welcome to cstheory! $\endgroup$ – Henry Yuen May 6 '12 at 18:28
7
$\begingroup$

This is because there isn't really a gap between $\epsilon$-close to having a property $P$ and being $\epsilon$-far to having property $P$. As a crude example, suppose we're testing the property of being the all $0$ string. What's the difference between being $\epsilon$-far and $\epsilon$-close to the $0$ string?

You could try to distinguish between being $\epsilon/2$-close vs $\epsilon$-far, because there's a gap. However, in many applications of property testing, we're guaranteed that either the object $x$ has property $P$ or is quite far from having property $P$. For example, in probabilistically checkable proofs, the object is the PCP proof, and it's either satisfying, or far from satisfying, and we want to determine which is the case.

Hope this helps. So, short answer: there's an asymmetry because of how property testing is used "in practice".

$\endgroup$
  • $\begingroup$ just to add: PCPs for Unique Games are an important example where the PCP has to distinguish between a nearly satisfiable instance and an instance that is far from satisfiable. as you point out, it's essential that there is a big gap between the two. $\endgroup$ – Sasho Nikolov May 8 '12 at 20:35
4
$\begingroup$

To complement Alan Guo's answer, you can also note that such a tolerant tester cannot have one-sided error and still have a sublinear query complexity (since an adversary is always allowed to change some fraction of the input).

It's actually an interesting open question to tell whether there is some universal translation between property testers and tolerant property testers.

For dense graph properties a constant query tester implies a constant query tolerant tester (actually it implies a bit more, you can obtain an approximation of the distance with a constant number of queries): E. Fischer and I. Newman, Testing versus estimation of graph properties, SIAM Journal on Computing37 (2007), 482-501 http://www.cs.technion.ac.il/~eldar/genf.ps

For Boolean strings this translation cannot be too good. There are properties of Boolean string that can be tested with a constant number of queries but there exists no tolerant tester with a constant number of queries: E. Fischer and L. Fortnow, Tolerant versus intolerant testing for Boolean properties, Theory of Computing 2 (2006), Article 9, 173-183 http://www.cs.technion.ac.il/~eldar/ttg.ps

$\endgroup$
  • $\begingroup$ “To complement Alan Guo's answer, you can also note that such a tolerant tester cannot have one-sided error and still have a sublinear query complexity (since an adversary is always allowed to change some fraction of the input).” Can you elaborate? I cannot understand the reason you gave; it seems to me that the same argument would equally apply to usual (non-tolerant) testers, but this is absurd. $\endgroup$ – Tsuyoshi Ito May 8 '12 at 16:05
  • $\begingroup$ @TsuyoshiIto the way I understand what Yonatan said, the point is that a one-sided tester has perfect completeness, i.e. accepts "yes" inputs with probability 1. $\endgroup$ – Sasho Nikolov May 8 '12 at 20:29
  • $\begingroup$ @Sasho Nikolov: Yes, I interpret the claim in the same way. My point is that I cannot see why it is true, and moreover I fail to see how Yonatan used the fact that we are talking about tolerant testers in that claim (he must have used it because the same claim does not hold in the case of non-tolerant testers). $\endgroup$ – Tsuyoshi Ito May 8 '12 at 21:31
  • $\begingroup$ @TsuyoshiIto non-rigorous explanation: say a yes-instance is $<\delta$ distance from the property. since a tester with one-sided error accepts a yes-instance for any sequence of coin throws, you can fix the coin throws ahead of time and treat the tester as deterministic. then you can run an adversary argument to fool any tester that reads less than $\delta n$ bits of the input. clearly this argument is vacuous for the non-tolerant setting where $\delta = 0$. $\endgroup$ – Sasho Nikolov May 9 '12 at 3:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.