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)) n log 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 p ∈ (0, 1/2). As our main result, we show that (1± o (1)) ( 1/ I ( p ) + 1/(1−2 p ) log 2 (1− p / p ) ) n log 2 n noisy comparisons are both necessary and sufficient to sort n elements with error probability o (1) using noisy comparisons, where I ( p )=1 + p log 2 p +(1− p )log 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.

Authors

• Yuzhou Gu
• Yinzhan Xu

Keywords

• information theory
• noisy binary search
• noisy sorting
• query complexity