# Statistical and computational challenges in ranking

arXiv: https://arxiv.org/abs/2512.21111 · HTML: https://mlsanity.com/paper/2512.21111/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 42 of its 64 references that are in the map.
- First posted on arXiv 24 Dec 2025.

## Builds on (most cited first, 30 of 42)

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness](https://mlsanity.com/paper/1606.09632/) (2016)
- [Universality of Computational Lower Bounds for Submatrix Detection](https://mlsanity.com/paper/1902.06916/) (2019)
- [Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix](https://mlsanity.com/paper/1502.01988/) (2015)
- [Uncoupled isotonic regression via minimum Wasserstein deconvolution](https://mlsanity.com/paper/1806.10648/) (2018)
- [Community Detection in Sparse Random Networks](https://mlsanity.com/paper/1308.2955/) (2013)
- [Optimal Rates of Statistical Seriation](https://mlsanity.com/paper/1607.02435/) (2016)
- [Optimal Permutation Recovery in Permuted Monotone Matrix Model](https://mlsanity.com/paper/1911.10604/) (2019)
- [Finding One Community in a Sparse Graph](https://mlsanity.com/paper/1502.05680/) (2015)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025)
- [Is Planted Coloring Easier than Planted Clique?](https://mlsanity.com/paper/2303.00252/) (2023)
- [Sharp Phase Transitions in Estimation with Low-Degree Polynomials](https://mlsanity.com/paper/2502.14407/) (2025)
- [Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons](https://mlsanity.com/paper/1603.06881/) (2016)

## Abstract (arXiv)

We consider the problem of ranking n experts according to their abilities, based on the correctness of their answers to d questions. This is modeled by the so-called crowd-sourcing model, where the answer of expert i on question k is modeled by a random entry, parametrized by Mi,k which is increasing linearly with the expected quality of the answer. To enable the unambiguous ranking of the experts by ability, several assumptions on M are available in the literature. We consider here the general isotonic crowd-sourcing model, where M is assumed to be isotonic up to an unknown permutation π^* of the experts - namely, M_π*-1(i),k ≥ M_π*-1(i+1),k for any i∈ [n-1], k ∈ [d]. Then, ranking experts amounts to constructing an estimator of π^*. In particular, we investigate here the existence of statistically optimal and computationally efficient procedures and we describe recent results that disprove the existence of computational-statistical gaps for this problem. To provide insights on the key ideas, we start by discussing simpler and yet related sub-problems, namely sub-matrix detection and estimation. This corresponds to specific instances of the ranking problem where the matrix M is constrained to be of the form λ mathbf 1S× T where Ssubset [n], Tsubset [d]. This model has been extensively studied. We provide an overview of the results and proof techniques for this problem with a particular emphasis on the computational lower bounds based on low-degree polynomial methods. Then, we build upon this instrumental sub-problem to discuss existing results and algorithmic ideas for the general ranking problem.