When Does Clustering Become Easy, and Should We Care About Other Cases?
summary
Survey argues that many formal “clusterable” definitions let algorithms run fast but only under unrealistically strong gaps (e.g. epsilon-separateness ≈ 200× gap, or center-stability requiring factor >2; below 2 NP‑hard). Tools include perturbation‑robustness, uniqueness‑of‑optimum ↔ statistical stability, and cost‑gap notions. Main constructive result shows a semi‑supervised active protocol that uses O(K log N) same/different queries to turn NP‑hard instances into near‑linear solutions (robust to some label noise), demonstrating cheap supervision can bridge worst‑case/practice.
AI-written summary · about
chapters (14)
- 0:00Intro
- 1:06The major theme of this week
- 1:37Approaches ! - Algorithm based
- 2:19Approaches 2 - Input based
- 3:38Approaches 3 - Combined
- 6:10Themes of this talk
- 11:11Outline of the rest of the talk
- 12:56Desiderata for notions of clusterability
- 15:11The main open question
- 17:28Perturbation robustness notions
- 32:47Provable reason for concern
- 34:02Implications of 2 center stability
- 36:33The bottom line
- 47:15Basic algorithm's idea
related talks
26mMathematical Approaches to Clustering
47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower Bounds
01h 04m"More is Different." Also in Computing?
37mPower to the Points: Local Certificates for Clusterings
47mAssessing the quality of a clustering
33mClustering Using Pairwise Comparisons
01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms