# Testing for a symmetric property $P$

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?

• In property testing we want to distinguish two cases: the input satisfied the property, or is $\epsilon$-far from every point satisfying the property. – Yuval Filmus Jan 9 '19 at 6:03
• 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 – sssss Jan 9 '19 at 6:12
• 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. – Yuval Filmus Jan 9 '19 at 6:14
• I see what I forgot, thank you very much, that concludes the proof and the algorithm! :) – sssss Jan 9 '19 at 6:24
• Perhaps you can answer your own question now. – Yuval Filmus Jan 9 '19 at 6:25