Optimal Bounds for Noisy Sorting

DOI10.1145/3564246.3585131MaRDI QIDQ6427493zbMATH OpenWikidataFDO

Authors Yuzhou Gu, Yinzhan Xu

Publication date 23 February 2023

Full work available at URL https://doi.org/10.1145/3564246.3585131

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that $(1pmo(1))nlo{g}_{2}n$ comparisons are both necessary and sufficient to sort a list of $n$ elements. In this paper, we study the Noisy Sorting problem, where each comparison result is flipped independently with probability $p$ for some fixed $pin(0,frac12)$. As our main result, we show that ${\displaystyle }$(1pm o(1)) left( frac{1}{I(p)} + frac{1}{(1-2p) log_2 left(frac{1-p}p ight)} ight) nlog_2 n${\displaystyle }$ noisy comparisons are both necessary and sufficient to sort $n$ elements with error probability $o(1)$ using noisy comparisons, where $I(p)=1+plo{g}_{2}p+(1-p)lo{g}_2(1-p)$ is capacity of BSC channel with crossover probability $p$. This simultaneously improves the previous best lower and upper bounds (Wang, Ghaddar and Wang, ISIT 2022) for this problem. For the related Noisy Binary Search problem, we show that ${\displaystyle }$ (1pm o(1)) left((1-delta)frac{log_2(n)}{I(p)} + frac{2 log_2 left(frac 1delta ight)}{(1-2p)log_2left(frac {1-p}p ight)} ight) ${\displaystyle }$ noisy comparisons are both necessary and sufficient to find the predecessor of an element among $n$ sorted elements with error probability $delta$. This extends the previous bounds of (Burnashev and Zigangirov, 1974), which are only tight for $delta=1/n^{o(1)}$.

Cited in

(5)

• Algorithms for the generalized poset sorting problem
• Approximate selection with unreliable comparisons in sublinear time
• Complexity of round-robin allocation with potentially noisy queries
• Complexity of round-robin allocation with potentially noisy queries
• Noisy (binary) searching: simple, fast and correct

This page was built for publication: Optimal Bounds for Noisy Sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6427493)