We'll say $P$ is a symmetric property if $\forall x\in \{0,1\}^n:x\in P\iff \forall \pi \in S(n): f_{\pi }(x)\in P$ where $\forall i\in [n]:f_\pi (x)_i=x_{\pi(i)}$.

Given a symmetric property $P$ we want to find an algorithm which tests $P$, meaning given a vector $x\in \{0,1\}^n$ we want to say if $x\in P$ in sublinear time.

I know how to calculate an $\epsilon-$approximation of hamming weight in probability $\frac{2}{3}$ (can make it higher if I want to but can't get to probability $1$, just choose more indexes) in $O(\log \frac{1}{\epsilon^2})$ but can't find any way to use it.

Thought of trying to calculate the hamming weight with small enough $\epsilon$ such that I'll know if $x\in P$ or not, but can't find small enough $\epsilon$ which doesn't depend on $n$.

Any ideas?

  • $\begingroup$ In property testing we want to distinguish two cases: the input satisfied the property, or is $\epsilon$-far from every point satisfying the property. $\endgroup$ – Yuval Filmus Jan 9 '19 at 6:03
  • $\begingroup$ The problem is I can't get an approximation of hamming weight in probability $1$ which means that even if I give an algorithm there is a chance that it will fail but we want to return a correct answer in probability $1$. If I had such an approximation algorithm I could use it with $\frac{1}{3}\epsilon$ for example and if it is $\epsilon$-far in probability $1$ it won't be $\frac{1}{3}\epsilon$ far from any point satisfying the property even with the approximation because I'll get at most the correct weight+$\frac{1}{3}\epsilon$ which doesn't satisfy the property $\endgroup$ – sssss Jan 9 '19 at 6:12
  • $\begingroup$ Randomizes algorithms always have an error probability. Otherwise we could turn them into deterministic algorithm (as long as we don’t care about complexity). I suggest taking another look at the definition of a property tester. $\endgroup$ – Yuval Filmus Jan 9 '19 at 6:14
  • $\begingroup$ I see what I forgot, thank you very much, that concludes the proof and the algorithm! :) $\endgroup$ – sssss Jan 9 '19 at 6:24
  • $\begingroup$ Perhaps you can answer your own question now. $\endgroup$ – Yuval Filmus Jan 9 '19 at 6:25

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.