# Parallel Algorithms for Select and Partition with Noisy Comparisons

arXiv: https://arxiv.org/abs/1603.04941 · HTML: https://mlsanity.com/paper/1603.04941/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2016.

## Built on by (most cited first, 6 of 6)

- [Adaptivity Complexity for Causal Graph Discovery](https://mlsanity.com/paper/2306.05781/) (2023)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)
- [Regret Minimization with Noisy Observations](https://mlsanity.com/paper/2207.09435/) (2022)
- [Efficient Portfolio Selection through Preference Aggregation with Quicksort and the Bradley--Terry Model](https://mlsanity.com/paper/2504.16093/) (2025)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)

## Abstract (arXiv)

We consider the problem of finding the kth highest element in a totally ordered set of n elements (select), and partitioning a totally ordered set into the top k and bottom n-k elements (partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability 1-γ), and noisy (where comparisons are correct with probability 1/2+γ/2 and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.