7 papers
Phase Transition for Stochastic Block Model with more than Communities
Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen
Predictions from statistical physics postulate that recovery of the communities in the Stochastic Block Model (SBM) with a fixed number of communities is possible in polynomial…
Low-degree lower bounds via almost orthonormal bases
Alexandra Carpentier, Simone Maria Giancola, Christophe Giraud +1
Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical-computational gaps across a variety of high-dimensional statistical models [Wein25]…
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…
Phase Transition for Stochastic Block Model with more than Communities (II)
Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen
A fundamental theoretical question in network analysis is to determine under which conditions community recovery is possible in polynomial time in the Stochastic Block Model (SBM).…
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…
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…