patternMinor
sorting with noisy but persistent answers
Viewed 0 times
sortingwithanswersbutpersistentnoisy
Problem
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?
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?
Solution
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$):
-
Tolerant algorithms: Lowers the complexity to $O(|A|^2)$.
-
Sorting with recurrent comparison errors Lowers the complexity to $O(|A|^2)$. The returned permutation also has $O(|A|)$ total dislocation in expectation. This is probably the easiest algorithm to implement.
-
Optimal Dislocation with Persistent Errors in Subquadratic Time Same dislocation bounds as the above paper but in $\tilde{O}(|A|^{3/2})$ time.
-
Optimal Sorting with Persistent Comparison Errors. Lowers the complexity to $O(|A| \log |A|)$. The returned permutation has $O(|A|)$ total dislocation, w.h.p.
1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).
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$):
-
Tolerant algorithms: Lowers the complexity to $O(|A|^2)$.
-
Sorting with recurrent comparison errors Lowers the complexity to $O(|A|^2)$. The returned permutation also has $O(|A|)$ total dislocation in expectation. This is probably the easiest algorithm to implement.
-
Optimal Dislocation with Persistent Errors in Subquadratic Time Same dislocation bounds as the above paper but in $\tilde{O}(|A|^{3/2})$ time.
-
Optimal Sorting with Persistent Comparison Errors. Lowers the complexity to $O(|A| \log |A|)$. The returned permutation has $O(|A|)$ total dislocation, w.h.p.
1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).
Context
StackExchange Computer Science Q#110274, answer score: 4
Revisions (0)
No revisions yet.