I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example.

I did not understand the first step of the test in the following slide. Why is the first step $S= 2/\epsilon$?

enter image description here

Could someone please explain me in more detail (i.e. with a concrete example)? I would appreciate with that.

  • 1
    $\begingroup$ Could you include enough of the material from the slides to make the question self-contained? At least the definition of the property that the example deals with, for example. The link might disappear and it would be good for the question to still make sense if that happened. $\endgroup$ – David Richerby Jul 21 '14 at 10:02

The problem is, given a string of length $n$ over $\{0,1\}$, to distinguish the following two cases:

  1. The string is entirely 0.
  2. The string is $\epsilon$-far from being entirely 0, i.e., has at least an $\epsilon$-fraction of 1s.

The proposed algorithm tests $S = 2/\epsilon$ positions, and returns (1) if all positions were 0. If the original string consisted of 0s then this algorithm always returns (1) correctly, and otherwise it makes a mistake with probability $(1-\epsilon)^S \leq e^{-2}$.

We choose $S = 2/\epsilon$ in the first step so that the error probability is constant, in particular less than $1/3$. If you want a different error probability, you'll choose a different value of $S$.

  • $\begingroup$ I have only one tiny question mentioned in this slide. What does $p$ actually explain in witness lemma? and why do they also said ' with probability $ \geq 2/3$ ' $\endgroup$ – Hakan Jul 21 '14 at 20:44
  • 2
    $\begingroup$ They explain how to amplify a test with success probability $p$ (thought of as low) to a test with success probability at least $2/3$, this being an arbitrary threshold. The idea is to repeat the test $2/p$ times. The same calculation as in the toy problem proves the lemma. $\endgroup$ – Yuval Filmus Jul 21 '14 at 21:34

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.