6 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 for clustering in moderate dimension
Alexandra Carpentier, Nicolas Verzelen
We study the fundamental problem of clustering points into groups drawn from a mixture of isotropic Gaussians in . Specifically, we investigate the requisite…
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]…
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…
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).…
Seriation of Toeplitz and latent position matrices: optimal rates and computational trade-offs
Clément Berenfeld, Alexandra Carpentier, Nicolas Verzelen
In this paper, we consider the problem of seriation of a permuted structured matrix based on noisy observations. The entries of the matrix relate to an expected quantification of i…