Pith. Sign in

REVIEW

Ulam Rank Aggregation Is Hard to Approximate for Four Rankings

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Mursalin Habib, Tien Long Nguyen

Computational Complexity · Submitted 5 Sep 2026 · 32 references

Pith's verdict: The main claim holds up: constant-factor hardness for the Ulam median at four inputs, and the stress-test's anchor-block counterexample is a misread of the proof.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 9, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 5 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2609.05874 (version 1)
Pith ID2YJAJV4V, Pith's permanent record of this paper and its review
CitationDebarati Das, Diptarka Chakraborty, Le Van Cuong, Mursalin Habib, Sk Ruhul Azgor, Tien Long Nguyen. "Ulam Rank Aggregation Is Hard to Approximate for Four Rankings." arXiv:2609.05874 (2026). https://pith.science/paper/2YJAJV4V
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Rank aggregation under the Ulam metric is hard to approximate even with only four rankings, and no PTAS exists unless P = NP.

The reading

This paper proves that finding a consensus ranking (permutation) that minimizes the total Ulam distance to a set of input rankings is computationally hard to approximate, even when the input contains only four rankings. The authors establish a constant-factor inapproximability bound of 35/34 - epsilon for any epsilon > 0. This means that unless P = NP, there is no polynomial-time algorithm that can approximate the optimal median ranking to within this factor, and similarly no polynomial-time approximation scheme (PTAS) exists. The result is sharp because the problem is solvable exactly for three rankings, showing a dramatic jump in complexity from three to four inputs. The paper also proves the same hardness for the center variant (minimizing the maximum distance). The work introduces a general framework for reducing Boolean constraint satisfaction problems to the Ulam median problem using only four permutations, which is a notable technical contribution.

What carries the argument

The central mechanism is a reduction framework that starts with a Boolean CSP (like Max-E3-Lin-2) and constructs exactly four permutations such that the optimal Ulam median encodes the satisfiability of the CSP. The framework has three main components: (1) a 'clause-witness' gadget: a pair of permutations whose LCS score on a subset of symbols equals the number of constraints satisfied by that subset; (2) a 'variable-consistency' gadget: another pair of permutations whose LCS score measures how consistently a subset assigns truth values across variable occurrences; (3) an 'anchor block' of dummy symbols that forces any near-optimal median to split the alphabet into a 'true side' and a 'false side'. The anchor-block lemma (Lemma 3.3) ensures that without loss of generality we can assume the median has a specific block structure. The framework then connects the CSP optimum to the Ulam median optimum via a decoding argument that shows any inconsistent partition can be replaced by a consistent one without losing combined score. For the specific instantiation, the paper constructs an 8-symbol parity gadget (two permutations per constraint) that has LCS 3 for satisfying assignments and 2 for unsatisfying ones, which combined with the known hardness of Max-E3-Lin-2 gives the 35/34 gap.

Extended reading notes

Core claim

The paper's central discovery is that, for any fixed epsilon > 0, it is NP-hard to approximate the Ulam median (or Ulam center) within a multiplicative factor of 35/34 - epsilon, even when the input consists of exactly four permutations. This rules out a polynomial-time approximation scheme (PTAS) for either problem under the assumption that P ≠ NP. Prior work had shown NP-hardness only for an unbounded number of inputs, and exact polynomial-time algorithms exist for three inputs. Thus the paper establishes a sharp complexity transition from tractable (3 inputs) to strongly inapproximable (4 inputs). The authors achieve this by developing a general reduction framework that transforms any Boolean CSP with local gadgetry into a four-permutation Ulam median instance, preserving approximation gaps. They instantiate this framework with Max-E3-Lin-2, using an 8-symbol parity gadget that yields the specific hardness factor.

Load-bearing premise

The paper assumes P ≠ NP, a standard complexity-theoretic hypothesis. More specifically, it relies on Håstad's gap theorem for Max-E3-Lin-2 (Theorem 2.2), which itself is proved under P ≠ NP. If P = NP, the hardness results collapse.

Editorial extensions

If this is right

  • This result closes the complexity gap for Ulam median: it is exact polynomial-time solvable for three inputs but constant-factor inapproximable for four inputs, a sharp transition.
  • No polynomial-time approximation scheme (PTAS) exists for Ulam median or Ulam center with four or more inputs unless P = NP, which contrasts with the Kendall-tau median (Kemeny) that admits a PTAS even for an unbounded number of inputs.
  • The general reduction framework may be applicable to other Boolean CSPs to derive hardness of approximation for permutation median problems with few inputs, potentially yielding stronger inapproximability factors.
  • The additive inapproximability result (Theorem 1.2) rules out any algorithm that approximates within an additive epsilon*k*d factor (where k=4, d is alphabet size), reinforcing the difficulty of the problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Since the paper shows hardness for exactly four inputs, it suggests that the inherent complexity of Ulam median is not merely about having many inputs but about a combinatorial threshold: three inputs allow a structural reduction (via dynamic programming on the LCS) while four inputs already encode enough constraints to embed hard CSPs.
  • The framework's reliance on balanced label occurrences (equal numbers of true and false labels per variable) might be a necessary condition for the reduction, and it may be possible to adapt it to produce even tighter hardness factors by using stronger CSPs or larger gadgets.
  • The result implies that practical algorithms for Ulam rank aggregation with fixed small numbers of rankings (like 4) cannot hope for high accuracy; instead, they must settle for the best approximation factors achievable (e.g., the known 1.968 factor for unbounded inputs, or the 5/4 factor for 4 inputs derived in Appendix B) unless P=NP.
Original abstract

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ulam distances to the input rankings, while in the \emph{Ulam center} problem, the objective is to minimize the maximum such distance. We prove that, for every $0<\varepsilon< 1/34$, it is $\mathrm{NP}$-hard to approximate either Ulam median or Ulam center within a factor of $35/34-\varepsilon$, even when the input consists of only four rankings. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. Prior to our work, only the exact versions of both problems were known to be $\mathrm{NP}$-hard, and that too only when the number of input rankings is unbounded [Fischer et al., ESA'25 and Bachmaier et al., J. of Discrete Algorithms'15]. Furthermore, our inapproximability results are optimal in terms of the number of input rankings since for three inputs it is already known to be polynomial-time solvable [Chakraborty, Das, Krauthgamer, SODA'21]. En route, we introduce a new general framework for reducing Boolean constraint satisfaction problems (CSP) to the Ulam median with only four inputs. As a specific instantiation of the reduction framework, we obtain our hardness-of-approximation results. The corresponding hardness for the Ulam center follows from a reduction from the Ulam median.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,143 input tokens.

What the abstract itself states, as probabilities: claims first 0.63 · states limitation 0.42 · human participants 0.02 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.97 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ulam distances to the input rankings, while in the \emph{Ulam center} problem, the objective is to minimize the maximum such distance. We prove that, for every $0<\varepsilon< 1/34$, it is $\mathrm{NP}$-hard to approximate either Ulam median or Ulam center within a factor of $35/34-\varepsilon$, even when the input consists of only four rankings. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. Prior to our work, only the exact versions of both problems were known to be $\mathrm{NP}$-hard, and that too only when the number of input rankings is unbounded [Fischer et al., ESA'25 and Bachmaier et al., J. of Discrete Algorithms'15]. Furthermore, our inapproximability results are optimal in terms of the number of input rankings since for three inputs it is already known to be polynomial-time solvable [Chakraborty, Das, Krauthgamer, SODA'21]. En route, we introduce a new general framework for reducing Boolean constraint satisfaction problems (CSP) to the Ulam median with only four inputs. As a specific instantiation of the reduction framework, we obtain our hardness-of-approximation results. The corresponding hardness for the Ulam center follows from a reduction from the Ulam median.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 We study the approximability of rank aggregation under the Ulam metric. contribution 0.54 0.81 0.03 asserted 0.66
s1 In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ulam distances to the input rankings, while in the \emph{Ulam center} problem, the objective is to minimize the maximum such distance. background 1.00 0.11 0.03 asserted 0.97
s2 We prove that, for every $0<\varepsilon< 1/34$, it is $\mathrm{NP}$-hard to approximate either Ulam median or Ulam center within a factor of $35/34-\varepsilon$, even when the input consists of only four rankings. result 0.99 0.97 0.91 asserted 1.00
s3 We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. result 0.98 0.94 0.15 asserted 1.00
s4 Prior to our work, only the exact versions of both problems were known to be $\mathrm{NP}$-hard, and that too only when the number of input rankings is unbounded [Fischer et al., ESA'25 and Bachmaier et al., J. of Discrete Algorithms'15]. gap 0.84 0.06 0.05 asserted 1.00
s5 Furthermore, our inapproximability results are optimal in terms of the number of input rankings since for three inputs it is already known to be polynomial-time solvable [Chakraborty, Das, Krauthgamer, SODA'21]. result 0.44 0.21 0.11 asserted 1.00
s6 En route, we introduce a new general framework for reducing Boolean constraint satisfaction problems (CSP) to the Ulam median with only four inputs. method 0.67 0.97 0.04 asserted 1.00
s7 As a specific instantiation of the reduction framework, we obtain our hardness-of-approximation results. method 0.82 0.94 0.05 asserted 0.99
s8 The corresponding hardness for the Ulam center follows from a reduction from the Ulam median. method 0.89 0.92 0.04 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. illustrates the two mechanisms: reversing the occurrence order within each clause block and swapping the blocks of positive and negative occurrences for each variable. (a) Clause witnesses β1 β2 · · · · · · aj bj cj cj bj aj · · · · · · At most one LCS match from each clause (b) Variable consistency α1 α2 · · · · · · B0 x B1 x B1 x B0 x · · · · · · At most one label class from each variable
Figure 2. From four input permutations to a partition, and from an arbitrary partition to a consistent
Figure 3. The eight-symbol parity gadget for x ⊕ y ⊕ z = 1. For the indicated local assignment a, the four symbols in A are the ones whose labels (indicated as subscripts) agree with a and shown with solid borders; the other four disagreeing symbols are gray and dashed. Teal nodes and connecting lines exhibit a longest common subsequence of the restrictions to A: y0z0 in the unsatisfied example and y0z1x (2) 0 in the satisfied example. In general, the restricted LCS has length 2 for every unsatisfying assignment and length 3 for every satisfying assignment. Median hardness to center hardness
Figure 4. The median-to-center reduction for k = 4. Cyclic shifts place every original input once in every row and column, preserving the optimum. Proof of Theorem B.1. It suffices to analyze the approximation factor of the permutation σ. Apply￾ing Lemma B.4 and Lemma B.2, we have costΠ(σ) = 1 2 X k i=1 ED(σ, πi) ≤ 1 2  E + (k − 2 − 12∤k)M  ≤ 1 2 E  1 + ⌊k/2⌋ − 1 k  ≤ OPT αk. C Reduction from the Ulam Median to the Ulam Center Proof of Lemma 6.1. For each i ∈ Zk, let Σ (i) be a disjoint copy of Σ. For a permutation π ∈ P(Σ), let π (i) denote its copy on Σ (i) . The center instance is…

Figures reproduced from arXiv:2609.05874 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.