Metraipolis › archive › dc_a57820f2ccdb

Sorting from Counterexamples — arXiv:2608.21579

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.21579
License (as archived)
CC0-1.0
Archived
2026-10-18T08:35:50.091Z
SHA-256 of the archived text
145b24713333a0d5d5c4ecec84a2fae0d6237106838090f50d0fe4db6d7acf81
Stable URL of this page
https://metraipolis.com/documento/dc_a57820f2ccdb

How to cite

Sorting from Counterexamples — arXiv:2608.21579 — arXiv (en), https://arxiv.org/abs/2608.21579 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a57820f2ccdb (Metraipolis archive dc_a57820f2ccdb, sha256 145b24713333a0d5d5c4ecec84a2fae0d6237106838090f50d0fe4db6d7acf81)
BibTeX
@misc{dca57820f2ccdb,
  title = {Sorting from Counterexamples — arXiv:2608.21579},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.21579},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a57820f2ccdb; sha256 145b24713333a0d5d5c4ecec84a2fae0d6237106838090f50d0fe4db6d7acf81},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.21579. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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(n\log 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ünbaum'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 $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $\Omega(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.CO).
Categorie arXiv: Machine Learning (cs.LG) ; Computational Complexity (cs.CC); Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.21579 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T08:27:54.467Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).