An Information-Oriented View of Computational Hardness

• An Investigation of Computational and Informational Limits in Gaussian Mixture Clustering
  Nathan Srebro, Gregory Shakhnarovich and Sam Roweis
  UTML-TR-2006-002, February 2006
  [Tech Report PDF]

• When is Clustering Hard?
  [Slides from September 12th Talk (PDF)]

• When is Clustering Hard?
  Nathan Srebro, Gregory Shakhnarovich and Sam Roweis
  PASCAL Workshop on Statistics and Optimization of Clustering Workshop, July 2005
  [Abstract PDF], [Slides PDF]