Sorting from Noisy Information

Mark Braverman, Elchanan Mossel

This paper studies problems of inferring order given noisy information. In these problems there is an unknown order (permutation) $\pi$ on $n$ elements denoted by $1,...,n$. We assum…