Metraipolis › archive › dc_243dadfb4793
Generalized Sorting via Four-Cycles — arXiv:2611.06745
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06745
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:43.035Z
- SHA-256 of the archived text
d810523e4bc5a906b12f059e18967d9b825bb6d867c2f4f8e3e039d309e4518a- Stable URL of this page
https://metraipolis.com/documento/dc_243dadfb4793
How to cite
Generalized Sorting via Four-Cycles — arXiv:2611.06745 — arXiv (en), https://arxiv.org/abs/2611.06745 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_243dadfb4793 (Metraipolis archive dc_243dadfb4793, sha256 d810523e4bc5a906b12f059e18967d9b825bb6d867c2f4f8e3e039d309e4518a)
BibTeX
@misc{dc243dadfb4793,
title = {Generalized Sorting via Four-Cycles — arXiv:2611.06745},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06745},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_243dadfb4793; sha256 d810523e4bc5a906b12f059e18967d9b825bb6d867c2f4f8e3e039d309e4518a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06745. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an $n$-vertex $m$-edge graph $G=(V, E)$ where the vertex set $V$ is to be sorted, and the edge set $E$ indicates possible comparisons. The goal is to sort $V$ with as few (adaptive) queries to $E$ as possible. When $G$ is the complete graph, the problem is equivalent to standard sorting for which $\Theta(n \log n)$ queries are sufficient and necessary. All classical sorting algorithms crucially rely on the ability to compare any pair and do not imply an $o(n^2)$-query algorithm in the general case. This was improved 15 years ago by Huang, Kannan, and Khanna [FOCS'11] who achieved a bound of $\widetilde{O}(n\sqrt{n})$. Kuszmaul and Narayanan [FOCS'21] later gave a bound of $\widetilde{O}(\sqrt{m n})$, which is more efficient for sparse graphs, but matches the $\widetilde{O}(n\sqrt{n})$ barrier for dense graphs. In this paper, we present an algorithm for generalized sorting that makes at most $\widetilde{O}(n^{4/3})$ queries, therefore breaking the longstanding $\widetilde{O}(n\sqrt{n})$ barrier for all graphs. The key to our result is to query edges that belong to many (specific types of) four-cycles. We show that querying such edges allows the algorithm to verify the direction of many other edges (specifically, their opposing edges in the four-cycles) and thus achieve a much better amortized query cost.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.06745 — 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-11-05T18:21:04.031Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).