## hardness of identifying the number of local maxima for mixture of Gaussians

I once may have heard (but I may misremember or misunderstand), that the problem of deciding how many local maxima a mixture of Gaussians has is NP-hard.

Is this true, or is the hardness of this problem is an open problem? Can anyone give a reference, if it is a well-known result?

-

This year's FOCS paper seems relevant.

"Settling the Polynomial Learnability of Mixtures of Gaussians"

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians.

Edit 10/25: Suresh has a nice summary of the two papers that appeared on this problem here http://geomblog.blogspot.com/2010/10/focs-day-1-clustering.html

-