1
$\begingroup$

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?

$\endgroup$
  • $\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 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 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 at 6:14
  • $\begingroup$ I'll try that, thanks! $\endgroup$ – sssss Jan 9 at 6:15
  • $\begingroup$ I see what I forgot, thank you very much, that concludes the proof and the algorithm! :) $\endgroup$ – sssss Jan 9 at 6:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.