# How to decode function that returns number of 1s of the XOR of (target, a number you choose, and a biased random value)?

I received this problem and unsure how to figure it out. Apparently it is possible to decode the value correctly 99% of the time.

An example: Suppose the target is 20, and there is a function (let's call it noisy_encode) that will return the number of 1's of the XOR of 20, X, and u. You can specify X, and u will range between 0 to 20, with a bias to 2 with 20% probability (remaining are uniform). You can call noisy_encode with different values as many times as you would like.

• Do I get to observe noisy_encode for many X's? Or do I have to fix a single X? – rikhavshah Oct 5 '18 at 1:59
• Many X's are allowed – Imran Q Oct 5 '18 at 19:50
• In that case, my answer below works. – rikhavshah Oct 5 '18 at 21:46

Simply set $$X=0$$. Let $$t$$ be the target.

noisy_encode returns $$t\oplus u$$ which will be $$t\oplus 2$$ about 20% of the time, and look random the rest of the time. The mode output of noisy_encode will be $$t\oplus 2$$, and so $$\text{mode}\oplus 2$$ extracts $$t$$.

If instead of XOR, noisy_encode uses AND, we can assume $$u$$ is completely uniform instead:

First pick $$X = 1$$. Then the first bit of $$X \wedge u$$ will be the same as the first bit of $$u$$, then the rest of its bits will be $$0$$. Thus $$X \wedge u$$ is either equal to $$0$$ or to $$X$$. There is a nonzero probability of each of these.

Now consider $$X\wedge u\wedge t$$. It will either be $$0\wedge t$$ or $$X\wedge t$$. In the first case, the output will be $$0$$. In the second case, the output will depend on $$t$$. Specifically, the first bit will be the same as the first bit of $$t$$, then the rest of its bits will be $$0$$. Thus, if the first bit of $$t$$ is $$0$$, then $$X\wedge u\wedge t=0$$ always. On the other hand, if this bit is $$1$$, then $$X\wedge u\wedge t$$ can be either $$0$$ or $$X$$.

If you observe the function many times over and over, you will be able to determine which case you are highly likely to be in.

Repeat this process with $$X=2,4,8,16,\cdots$$ to get all the other bits of $$t$$.

• If X=1, wouldn't the first digit of XOR(X,u) be the opposite of the first digit of u? – Imran Q Oct 12 '18 at 16:59
• You are right, I read XOR as AND. – rikhavshah Oct 17 '18 at 17:45
• I fixed my answer. – rikhavshah Oct 17 '18 at 17:50