CS Paper Radar

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

Jonathan Cremer

cs.DS math.CO ·submitted 2026-10-13 17:09 UTC · v1
theory

Abstract

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.

Comment
11 pages, 1 figure, 4 tables. Code, certificates and Lean proofs: https://doi.org/10.5281/zenodo.23346948

Closest papers

Nearest neighbours by meaning across the whole index.

A Near-Optimal Generalized Sorting Algorithm

cs.DS ·2026-11-05 ·Sanjeev Khanna, Aaron Putterman, Junkai Song
theory similarity 0.64
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.

0.05

Selection under partial information

cs.DS ·2026-10-23 ·Benjamin Aram Berendsohn
similarity 0.60
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

Generalized Sorting via Four-Cycles

cs.DS ·2026-11-04 ·Soheil Behnezhad, Shane Ferrante
similarity 0.57
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

Improved bounds for the smallest 4-chromatic graph of girth six

cs.DM math.CO ·2026-08-24 ·Glauco Rampone
theorycode/data similarity 0.56
Abstract · 12 pages, 1 figure. Ancillary files: independent verification scripts, SAT certificates, and a self-contained Lean 4 formal proof. Code and …

For integers $k,g \ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \le n_6(4) \le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \le n_6(4) \le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

0.39

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.56
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

Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences

cs.DS cs.IRcs.LGstat.ML ·2026-11-07 ·Kehan Liu, Zhaoyun Chen, Xianquan Yan
publishedcode/data similarity 0.55
Abstract · 10 pages, 3 figures, 5 tables. Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM 2027). Code: https://gi…

Pairwise probabilities arise in rank aggregation, recommendation, and human or LLM evaluation, yet converting them into a maximum-likelihood list is a weighted Kemeny problem and is NP-hard in general. Known exact algorithms for rank-two tournaments use only comparison signs and do not optimize this likelihood. We show that the weighted problem is exactly solvable when the skew-symmetric log-odds matrix $W_{ij}=\log(p_{ij}/p_{ji})$ has rank two, including when the induced preferences contain cycles. Writing $W_{ij}=\det(h_i,h_j)$ and adding the closing vector $h_0=-\sum_i h_i$ turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the $n+1$ edge vectors, cuts after $h_0$, and returns a global maximum-likelihood order in $O(n\log n)$ time from the factors. The same geometry identifies the runner-up and gives a stability certificate beyond exact rank two. When the smallest determinant $δ$ of two consecutive edges in the closed angular cycle is positive, it is exactly the best-to-runner-up log-likelihood gap. For $W=W_0+E$, the CloseSort order of $W_0$ has regret at most $\sum_{i<j}|E_{ij}|$ on $W$ and remains optimal whenever this sum is below $δ$, a worst-case tight threshold. In 5,120 determinant-logit simulations, increasing the observations per pair from 4 to 64 raises the fraction on which rank-two projection outperforms the empirical plug-in optimum from 68.6% to 85.7%. On 3,600 Arena-Hard LLM-judge profiles drawn from 63 systems and ten judges, the leading rank-two component captures 89.2% of the log-odds energy. On profiles containing a directed majority triangle, CloseSort reduces normalized regret by 44% relative to Borda and improves the mean normalized objective over each of eight baselines. With factors supplied, it is 8,407 times faster than exact dynamic programming on 18-item rankings.

0.52

Parity Tests under Ties: A One-Test Lifting Theorem

cs.DS cs.CC ·2026-09-26 ·Ron Kupfer
theory similarity 0.54
Abstract

In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such tests underlie low-depth randomized algorithms for maximum finding and top-$k$ selection, but their usual analysis assumes distinct inputs because a tie makes the product vanish. We give a black-box lifting theorem that removes this assumption. After $O(\log n)$ polynomial tests determine the number of nonzero pairwise differences, every subsequent parity test is simulated by one polynomial test, consistently with a fixed lexicographic tie-breaking order. The simulator is an elementary symmetric polynomial in masked first and second powers of all pairwise differences. Thus a depth-$D$ parity-test tree on distinct inputs becomes a polynomial decision tree of depth $D+O(\log n)$ on arbitrary inputs, with no increase in randomized pointwise error for order-selection problems. We obtain maximum finding in depth $O(\log n[\log n+\log(1/δ)])$ with error $δ$, and top-$k$ selection in depth $O(\log^2 n+k\log n)$ with inverse-polynomial error, both without any promise on ties.

0.27

How rigid is maximum cardinality search? Stability and locality of MCS orderings under edge updates, verified in Lean

cs.DS cs.LO ·2026-11-13 ·Md Thoriqul Islam Thonmay, Gregory Morse
theorycode/data similarity 0.54
Abstract · 14 pages, 1 table. Code and proofs: https://github.com/thonmay/mcs-lean . Palomar registry: PALOMAR-2026-10-04-000009

For which sets F of edge modifications do a graph G and the modified graph share a maximum cardinality search (MCS) ordering? We prove that they do whenever, along every proper common MCS prefix, each unchosen vertex's neighbour count in the second graph exceeds its count in the first by zero or one. In particular, inserting or deleting any matching, or flipping a single edge, preserves a common ordering, and under the same hypothesis every common MCS prefix extends to a full common ordering without backtracking. Neither part of the hypothesis can simply be dropped: inserting a triangle, a P_4 or a 2P_3 shows that the +1 bound cannot be relaxed to +2, and a disjoint mixed insert/delete pair shows that the one-directional condition is needed. For the canonical ordering (smallest-index tie-breaking) under a single-edge update, an insertion can first change the ordering only strictly between the endpoints' positions, and a deletion only at the later endpoint; when no break fires, the ordering is unchanged. A boolean-adjacency executable refines the abstract probe-then-repair update. All of these results, including the four obstructions, are proved in Lean 4 over Mathlib, re-checked by independent kernel checkers, and registered in the Palomar registry. On paper we further show that the first break of an insertion is located in O((deg(v)+1) log n) time, independent of the window length. We claim no worst-case asymptotic speedup over recomputation.

0.45