Low-degree polynomials lower bounds for clustering in small dimension

The paper studies clustering \(n\) observations from a mixture of \(K\) isotropic distributions in \(\mathbb{R}^d\) when \(K\) is much larger than \(d\). Tensor methods recover the partition at polylogarithmic separation but need a large, non-explicit polynomial number of samples in \(dK\), while earlier low-degree lower bounds only required \(n\) to exceed \(dK^2\).

The authors build a mixture of \(2K\) product Bernoulli distributions on \(\{0,1\}^d\), with \(K = (d+1)^m\) and centres taken from a dual BCH code, so that the moment tensors match those of the uniform distribution on \(\{-1,1\}^d\) up to order \(2m+1\). For fixed \(m\) they show that low-degree polynomials fail when \(\Delta^2 \ll (K^2 d^{3/2}/n)^{1/(2m+2)} \wedge \sqrt{d}\), up to polylogarithmic factors, so polylogarithmic separation needs \(n \gtrsim K^2 d^{3/2}\). A Gaussianisation argument carries the hardness to Gaussian mixtures. The proof counts solutions of polynomial systems over the finite field \(\mathbb{F}_{d+1}\).