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.

  • $\begingroup$ Do I get to observe noisy_encode for many X's? Or do I have to fix a single X? $\endgroup$ – rikhavshah Oct 5 '18 at 1:59
  • $\begingroup$ Many X's are allowed $\endgroup$ – Imran Q Oct 5 '18 at 19:50
  • $\begingroup$ In that case, my answer below works. $\endgroup$ – 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$.

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

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.