Low-degree polynomials lower bounds for clustering in small dimension
Abstract
We study the computational limits of clustering n observations drawn from a mixture of K isotropic distributions in ℝd, in the regime where the number K of groups is much larger than the dimension d. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of dK, whereas the existing low-degree lower bounds only show that n must be larger than dK2. We introduce a mixture of 2K product Bernoulli distributions on {0,1}d, with K=(d+1)m, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on {−1,1}d up to the order 2m+1. For any fixed m, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation Δ satisfies Δ2≪(K2d3/2/n)1/(2m+2)∧√d, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require n≳ K2d3/2 observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field 𝔽d+1 that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.
Related
- Sharp lower bounds for bisections of graphs with bounded maximum degree
- Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension
- Degree-one Pieri rule for non-symmetric Jack polynomials
- On the Squarefree Values of Degree-2q Polynomials
- Galois groups of random polynomials of large degree
BibTeX
@misc{carpentier2026lowdegree,
title = {{Low-degree polynomials lower bounds for clustering in small dimension}},
author = {Alexandra Carpentier and Nicolas Verzelen},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37272},
eprint = {2610.37272},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05800973v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Low-degree polynomials lower bounds for clustering in small dimension
AU - Alexandra Carpentier
AU - Nicolas Verzelen
PY - 2026
DA - 2026/10/15
PB - HAL
DO - 10.48550/arxiv.2610.37272
UR - https://hal.science/hal-05800973v1
AB - We study the computational limits of clustering n observations drawn from a mixture of K isotropic distributions in ℝ^d, in the regime where the number K of groups is much larger than the dimension d. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of dK, whereas the existing low-degree lower bounds only show that n must be larger than dK^2. We introduce a mixture of 2K product Bernoulli distributions on {0,1}^d, with K=(d+1)^m, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on {−1,1}^d up to the order 2m+1. For any fixed m, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation Δ satisfies Δ^2≪(K^2d^3/2/n)^1/(2m+2)∧√d, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require n≳ K^2d^3/2 observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field 𝔽_d+1 that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.
ER -