We consider the problem of clustering mixtures of mean-separated Gaussians in high dimensions. We are given samples from a mixture of $k$ identity covariance Gaussians, so that the minimum pairwise distance between any two pairs of means is at least $Δ$, for some parameter $Δ> 0$, and the goal is to recover the ground truth clustering of these samples. It is folklore that separation $Δ= Θ(\sqrt…