Nicolas
Verzelen
INRAE, Université Montpellier
Statistical–Computational Trade-offs: Low-Degree Polynomials and Community Recovery
Abstract.
In many high-dimensional problems, such as planted clique, sparse PCA, clustering and community detection, the signal strength needed by the best known polynomial-time algorithms is much larger than what is information-theoretically necessary. Is this gap intrinsic? Since NP-hardness says nothing about random instances, evidence of hardness must come from other sources: average-case reductions, or lower bounds for broad classes of algorithms. In the first part, I will introduce the low-degree polynomial framework, starting from testing problems in additive models. In the Gaussian additive model, the χ² divergence and the low-degree advantage admit simple expressions in terms of the overlap between two independent copies of the signal. Comparing them shows how truncating at a low degree discards the rare large overlaps that only exhaustive search can exploit. In the second part, based on joint work with Alexandra Carpentier and Christophe Giraud, I will consider community recovery in the stochastic block model with more than √n communities. We prove that low-degree polynomials fail below a threshold conjectured by Chin, Mossel, Sohn and Wein, for any graph density, and that this threshold lies below the Kesten–Stigum threshold. We also show that counting suitable motifs succeeds above it in moderately sparse regimes. These motifs are dictated by the lower-bound analysis: cliques, paths, and blow-ups of cycles.