Preprint
Oct 2026
Low-degree polynomials lower bounds for clustering in small dimension
A low-degree polynomial lower bound is established showing that clustering is hard as long as the separation $\Delta$ satisfies $\Delta^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors.
Alexandra Carpentier, Nicolas Verzelen
· 0 citations