Polynomial-time clustering threshold for Gaussian mixtures
Statement
Let , , and be positive integers with , and let denote the separation parameter for the Gaussian-mixture clustering model. Write when is at least up to polylogarithmic factors. Polynomial-time clustering conjecture. For any , , and such that , it is possible to reconstruct the partition in polynomial time as long as
Together with the paper's low-degree lower bound and the lower bounds of Even (2025), this would identify the computational threshold up to polylogarithmic factors for the stated range of dimensions. The paper proves a matching upper bound only for specific instances, so the general assertion remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.