RECORD
Optimal Bounds for Noisy Sorting
Data Structures and Algorithms · Submitted 24 Feb 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim As our main result, we show that $$(1\pm o(1)) \left( \frac{1}{I(p)} + \frac{1}{(1-2p) \log_2 \left(\frac{1-p}p\right)} \right) 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$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that $(1\pm 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\in (0, \frac 12)$. As our main result, we show that $$(1\pm o(1)) \left( \frac{1}{I(p)} + \frac{1}{(1-2p) \log_2 \left(\frac{1-p}p\right)} \right) 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. For the related Noisy Binary Search problem, we show that $$ (1\pm o(1)) \left((1-\delta)\frac{\log_2(n)}{I(p)} + \frac{2 \log_2 \left(\frac 1\delta\right)}{(1-2p)\log_2\left(\frac {1-p}p\right)}\right) $$ 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)}$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Sorting is a fundamental problem in computer science. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s1 | In the classical setting, it is well-known that $(1\pm o(1)) n\log_2 n$ comparisons are both necessary and sufficient to sort a list of $n$ elements. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s2 | In this paper, we study the Noisy Sorting problem, where each comparison result is flipped independently with probability $p$ for some fixed $p\in (0, \frac 12)$. | background 0.65 | 0.16 | 0.02 | asserted 0.91 |
| s3 | As our main result, we show that $$(1\pm o(1)) \left( \frac{1}{I(p)} + \frac{1}{(1-2p) \log_2 \left(\frac{1-p}p\right)} \right) 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$. | result 0.98 | 0.97 | 0.98 | asserted 1.00 |
| s4 | This simultaneously improves the previous best lower and upper bounds (Wang, Ghaddar and Wang, ISIT 2022) for this problem. | interpretation 0.51 | 0.62 | 0.05 | asserted 1.00 |
| s5 | For the related Noisy Binary Search problem, we show that $$ (1\pm o(1)) \left((1-\delta)\frac{\log_2(n)}{I(p)} + \frac{2 \log_2 \left(\frac 1\delta\right)}{(1-2p)\log_2\left(\frac {1-p}p\right)}\right) $$ noisy comparisons are both necessary and sufficient to find the predecessor of an element among $n$ sorted elements with error probability $\delta$. | result 0.97 | 0.96 | 0.04 | asserted 1.00 |
| s6 | This extends the previous bounds of (Burnashev and Zigangirov, 1974), which are only tight for $\delta = 1/n^{o(1)}$. | contribution 0.38 | 0.68 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that $(1\pm 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\in (0, \frac 12)$. As our main result, we show that $$(1\pm o(1)) \left( \frac{1}{I(p)} + \frac{1}{(1-2p) \log_2 \left(\frac{1-p}p\right)} \right) 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. For the related Noisy Binary Search problem, we show that $$ (1\pm o(1)) \left((1-\delta)\frac{\log_2(n)}{I(p)} + \frac{2 \log_2 \left(\frac 1\delta\right)}{(1-2p)\log_2\left(\frac {1-p}p\right)}\right) $$ 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)}$.
Human review
References
How the literature uses it
1 arXiv paper cite this in 3 sentences
Papers citing it
Uses its method or tool 1 paper
-
This function is given in Algorithm [ref], which can be seen as a recast of Algorithm 1 in [ref] .
Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions · Upper Bound · 1.00
Cites it as background 1 paper
-
On the other hand, the noisy computation of the function has closely followed the literature on the active ranking problem (also known as “noisy sorting”) and the top-$k$ selection problem [ref] , where the ranking of a subset of the $n$ items is required.
Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions · Related Work · 0.97
What it cites · 3 sentences without a confident label
Contests 1 paper
-
However, as pointed out by [ref] , there are potential issues in [ref] 's proof.
Noisy (Binary) Searching: Simple, Fast and Correct · Introduction · contest 0.82
Compares with 1 paper
-
Concurrent work [ref] also improves over [ref] in many aspects.
Noisy Sorting Capacity · Introduction · 0.98
Cites as background 1 paper
-
Noisy Binary Search is well-studied [ref] in the noisy model we consider, as well as in some other models [ref] .
Noisy (Binary) Searching: Simple, Fast and Correct · Introduction · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.