Showing math.STShow all
3 papers · 1 filter
math.ST2025
Minimax optimal seriation in polynomial time
Yann Issartel, Christophe Giraud, Nicolas Verzelen
We consider the seriation problem, whose goal is to recover a hidden ordering from a noisy observation of a permuted Robinson matrix. We establish sharp minimax rates under average…
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…