{"ID":2825473,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.21111","arxiv_id":"2512.21111","title":"Statistical and computational challenges in ranking","abstract":"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 $M_{i,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} \\geq M_{π^{*-1}(i+1),k}$ for any $i\\in [n-1], k \\in [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 1\\{S\\times T\\}$ where $S\\subset [n], T\\subset [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.","short_abstract":"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 $M_{i,k}$ which is increasing linea...","url_abs":"https://arxiv.org/abs/2512.21111","url_pdf":"https://arxiv.org/pdf/2512.21111v1","authors":"[\"Alexandra Carpentier\",\"Nicolas Verzelen\"]","published":"2025-12-24T11:18:06Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"stat.ML\"]","methods":"[]","has_code":false}