Fetching the paper…

Reading the bibliography…

2007

Noisy Sorting Without Resampling

Braverman, Mark, Mossel, Elchanan

Original
PDF
Post on X

Understand

In this paper we study noisy sorting without re-sampling.

In this problem there is an unknown order $a_{\pi(1)} < ...
< a_{\pi(n)}$ where $\pi$ is a permutation on $n$ elements.
The input is the status of $n \choose 2$ queries of the form $q(a_i,x_j)$, where $q(a_i,a_j) = +$ with probability at least $1/2+\ga$ if $\pi(i) > \pi(j)$ for all pairs $i \neq j$, where $\ga > 0$ is a constant and $q(a_i,a_j) = -q(a_j,a_i)$ for all $i$ and $j$.

Noisy Sorting Without Resampling · Around

Built on

Spearman’s footrule as a measure of disarray
P. Diaconis and R. L. Graham · 1977
Earlier work this paper cites.
Computing with unreliable information
U. Feige, D. Peleg, P. Raghavan, and E. Upfal · 1990
Earlier work this paper cites.
Introduction to Coding and Information Theory
S. Romann · 1997
Earlier work this paper cites.

Similar

Aggregating inconsistent information: ranking and clustering
N. Ailon, M. Charikar, and A. Newman · 2005
Cited alongside, same era.
Ranking tournaments
N. Alon · 2006
Cited alongside, same era.

Then

Noisy binary serach and its applications
D. Karp and B. Kleinberg · 2007
Closest in time.
How to rank with few errors
C. Kenyon-Mathieu and W. Schudy · 2007
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…