Showing 2025 · math.STShow all
3 papers · 2 filters
math.ST2025
Statistical and computational challenges in ranking
Alexandra Carpentier, Nicolas Verzelen
We consider the problem of ranking experts according to their abilities, based on the correctness of their answers to questions. This is modeled by the so-called crowd-sour…
math.ST2025
Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
Bertrand Even, Christophe Giraud, Nicolas Verzelen
In many high-dimensional problems,polynomial-time algorithms fall short of achieving the statistical limits attainable without computational constraints. A powerful approach to pro…
math.ST2025
Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
Bertrand Even, Christophe Giraud, Nicolas Verzelen
In many high-dimensional problems, like sparse-PCA, planted clique, or clustering, the best known algorithms with polynomial time complexity fail to reach the statistical performan…