4
$\begingroup$

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?

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

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$):


1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).

$\endgroup$
2
$\begingroup$

Your problem has been considered by Braverman and Mossel in their paper Noisy sorting without resampling. The paper has generated quite a lot of follow-up work, some of which might be more practical than the original algorithm suggested by Braverman and Mossel.

$\endgroup$

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.