Id: arxiv/2602.23023 Url: https://arxiv.org/abs/2602.23023 Tags: math.ST, cs.LG, math.PR, stat.ML Score: 0 Title: Low-degree Lower bounds for clustering in moderate dimension Domain: math.ST Source: arxiv Authors: Alexandra Carpentier, Nicolas Verzelen Reviews: 0 Subject: math.ST Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-26 Page: https://delphi.science/r/arxiv/2602.23023 We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $\mathbb{R}^d$. Specifically, we investigate the requisite minimal distance $Δ$ between mean vectors to partially recover the underlying partition. While the minimax-optimal threshold for $Δ$ is well-established, a significant gap exists between this information-theoretic limit and the performance of known polynomial-time procedures. Although this gap was recently characterized in the high-dimensional regime ($n \leq dK$), it remains largely unexplored in the…