# Sorting from Counterexamples

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 21 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [On Communication Complexity of Classification Problems](https://mlsanity.com/paper/1711.05893/) (2017)
- [When is it Better to Compare than to Score?](https://mlsanity.com/paper/1406.6618/) (2014)
- [Learning Combinatorial Functions from Pairwise Comparisons](https://mlsanity.com/paper/1605.09227/) (2016)
- [What Does Preference Learning Recover from Pairwise Comparison Data?](https://mlsanity.com/paper/2602.10286/) (2026)
- [Simple and Fast Algorithms for Interactive Machine Learning with Random Counter-examples](https://mlsanity.com/paper/1810.00506/) (2018)
- [Applications of Littlestone dimension to query learning and to compression](https://mlsanity.com/paper/2310.04812/) (2023)
- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)

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

- [An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order](https://mlsanity.com/paper/2609.10196/) (2026)

## Abstract (arXiv)

Consider the following problem of learning an unknown linear order on n items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to k of the returned counterexamples may be untruthful, where k is not known in advance. We determine the optimal query complexity up to constant factors: [ Theta(nlog n + nk). ] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order n. The upper bound is based on a geometric representation of permutations and Gr"unbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in ℝd, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of O(d2log n+dk) and a lower bound of Omega(dlog n+dk), leaving a factor of d gap in the noiseless term.