# sorting with noisy but persistent answers

Given a set of elements $$A$$ and a probability of noise $$p<0.5$$. For any two elements $$x,y\in A$$ we can ask the oracle $$O$$ to know where $$x$$ stands w.r.t $$y$$ (0 means $$x$$ is smaller than $$y$$ and 1 means the other way).

The oracle answers correctly with probability $$1-p$$. The noise is random and independent but persistent in a sense that if the oracle answers incorrectly for one pair $$(x,y)$$ it will give the same answer if questioned on the same pair again.

Is there any known strategy to sort $$A$$ with high probability?

• You mean, higher value of P or lower? – SiluPanda Jun 5 '19 at 17:11

For constant $$p>0$$ there is no way to exactly sort $$A$$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $$p$$ and no other comparison provides any information on their order.
In fact, if an algorithm returns a permutation of $$A$$ that has maximum dislocation1 $$D$$ with high probability, then $$D = \Omega(\log |A|)$$.
The algorithm in the paper by Braverman and Mossel suggested by Yuval returns a permutation with maximum dislocation $$O(\log |A|)$$ and, in particular, returns the maximum-likelihood permutation. However, its running time can be quite large.
The following papers have improved the time complexity (in chronological order) for the problem of sorting with (asymptotically) optimal $$O(\log |A|)$$ maximum dislocation. Here the returned permutation does not need to be the maximum-likelihood one and $$p$$ needs to be smaller than some constant ($$1/32$$, $$1/20$$, or $$1/16$$):