Optimal Bounds for Noisy Sorting

Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that (1± o(1)) nlog2 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 p∈ (0, frac 12). As our main result, we show that (1± o(1)) left( frac1I(p) + frac1(1-2p) log2 left(frac1-ppright) right) nlog2 n noisy comparisons are both necessary and sufficient to sort n elements with error probability o(1) using noisy comparisons, where I(p)=1 + plog2 p+(1-p)log2 (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 (1± o(1)) left((1-δ)fraclog2(n)I(p) + frac2 log2 left(frac 1δright)(1-2p)log2left(frac 1-ppright)right) noisy comparisons are both necessary and sufficient to find the predecessor of an element among n sorted elements with error probability δ. This extends the previous bounds of (Burnashev and Zigangirov, 1974), which are only tight for δ = 1/no(1).