CS Paper Radar

A Near-Optimal Generalized Sorting Algorithm

Sanjeev Khanna, Aaron Putterman, Junkai Song

cs.DS ·submitted 2026-11-05 18:08 UTC · v1
theory

Abstract

We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $π$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $Θ(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+Ω(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Sorting via Four-Cycles

cs.DS ·2026-11-04 ·Soheil Behnezhad, Shane Ferrante
similarity 0.81
Abstract · 22 pages, 2 figures

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 $Θ(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.

0.30

Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons

cs.DS math.CO ·2026-10-13 ·Jonathan Cremer
theory similarity 0.64
Abstract · 11 pages, 1 figure, 4 tables. Code, certificates and Lean proofs: https://doi.org/10.5281/zenodo.23346948

Let $V_i(n)$ denote the minimum worst-case number of comparisons needed to find the $i$-th smallest of $n$ distinct elements. We construct algorithms showing $V_7(16)\le28$ and $V_8(16)\le29$, improving the previously reported upper bounds of 30 and 31. Together with known lower bounds, these results establish $V_7(16)=28$ and leave $V_8(16)\in\{28,29\}$. For 17 elements, we establish $V_5(17)=27$ and improve the upper bounds for ranks 6 through 9 to 29, 30, 31, and 31, respectively. Every new upper bound has an explicit decision-graph certificate verified by a static checker developed independently of the search. We also derive a lower bound for selection from a partially ordered state by combining the Fussenegger-Gabow weight with its order-reversed counterpart. All new upper bounds and this lower bound are formally verified in Lean 4. For $V_8(16)$, we show that a lower bound based solely on the total number of decision-tree leaves cannot establish $V_8(16)\ge29$. The algorithms were found using fixed-budget search, information-guided comparison ordering, and proof-number search. Proof-number search was decisive in finding the 28-comparison algorithm; in our experiments, refuting a comparison budget remained substantially more expensive than finding an algorithm within it.

0.37

Sorting from Counterexamples

cs.LG cs.CCcs.CGcs.DS+1 ·2026-08-21 ·Noga Alon, Shay Moran, Shlomo Moran
publishedtheory similarity 0.64
Abstract

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: \[ Θ(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 $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

0.37

Online and Fully-Dynamic Sorting

cs.DS ·2026-11-16 ·Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi +1 more
theory similarity 0.63
Abstract

Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.

0.11

Selection under partial information

cs.DS ·2026-10-23 ·Benjamin Aram Berendsohn
similarity 0.62
Abstract

The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $Θ(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs $O( k + \operatorname{OPT}(P,k) )$ comparisons, where $\operatorname{OPT}(P,k)$ is the minimum number of comparisons required for the input $(P,k)$. If $P$ is a rooted tree, we obtain an $O( \operatorname{OPT} \log (k / \operatorname{OPT}) )$ algorithm, which can be further improved to $O( \operatorname{OPT} \log \log (k/\operatorname{OPT}) )$ or $O( \operatorname{OPT} \log \operatorname{OPT})$ under mild assumptions about $P$. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.

0.20

Tight Asymptotic Bounds on the Size of Order Graphs

cs.DS ·2026-10-29 ·Ruben Becker, Adrián Gómez-Brandón, Gonzalo Navarro, Nicola Prezza
theoryhot direction similarity 0.61
Abstract

Order graphs were introduced by Arroyuelo et al.\ (TODS 2024) as a generalization of the ring index, to support worst-case optimal joins on relations of arity $d$ while storing few columns: the index stores one column per edge, so its size is proportional to the number of edges of an order graph. It was known that the minimum number of edges lies between $Ω(2^d\sqrt d)$ and $O(2^d d)$, and the lower bound had been claimed to be $42$ for $d=6$. We first exhibit an optimal order graph with only $40$ edges for $d=6$, and show that the proof of that lower bound holds only for unions of cycles, whereas order graphs can be smaller than the smallest set of cycles. We give a corrected statement and proof that holds for every order graph: there must be at least $\max_m\binom dm\lceil m/2\rceil$ edges. This bound is $40$ (hence tight) for $d=6$. We then settle the asymptotic question: the minimum size is $Θ(2^d\sqrt d)$. This is obtained via an explicit construction, based on symmetric chain decompositions of the Boolean lattice, with at most $(d-1)\binom{d}{\lfloor d/2\rfloor}+2^d$ edges. The upper bound is within a factor $4+O(d^{-1/2})$ of the lower bound, and both numerically and asymptotically better than trie switching. Finally, we cast the problem as a set cover with connectivity constraints, which yields an exact ILP formulation and a greedy heuristic. With them we find optimal order graphs for $d\le 6$ in the bidirectional and for $d \le 7$ in the unidirectional model, showing that our lower bounds are tight there, and improve the best known order graphs for $d=7$ and $8$.

0.34

The Movement Complexity of Sorting

cs.DS cs.CC ·2026-10-31 ·Sichen Wang
theory similarity 0.61
Abstract · 39 pages

The complexity of sorting is usually measured by the number of comparisons. This measure ignores the movement of the read heads between comparisons, which is a real cost on many machines. We study this cost on its own. Keys lie on a $d$-dimensional grid, two heads move over the grid and compare the keys beneath them, and the only cost is the total movement of the heads. The algorithm plans its route in $r$ rounds and sees the outcomes of each round only after running it. For every $d$ and $r$ we determine the expected movement needed to sort $n$ keys: it is $n^β$ up to polylogarithmic factors, where $β=1+D^{r-1}/(D^{r}-(D-1)^{r})$ and $D=2d$, falling from $n^{2}$ at $r=1$ to $n^{1+1/(2d)}$ with unlimited rounds. Our algorithm makes every round move about the same amount, and a matching lower bound holds against every algorithm.

0.32

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

cs.DS ·2026-10-16 ·Eliyahu Yablon
similarity 0.61
Abstract

The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized $O\left(m^{1+2/(k-1)} n^{1/(k-1)}\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors $k = c\frac{\log n}{\log \log n}$ where $c>5$, our algorithm gives a runtime of $O\left(m (\log n)^{5/c}\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\frac{\log n}{\log \log n}$ yields a running time of $O\left( \frac{cn (\log n)^{2 + 4/(3c)} }{\log \log n} + m\log n\right)$ (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call ``random filtering.'' That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.

0.18