Clustering Under Perturbation Resilience

on YouTube ↗40m

" summary

Shows polynomial-time exact algorithms for symmetric and asymmetric k‑center assuming 2-perturbation resilience, and proves no algorithm below 2 unless NP=RP. Symmetric case uses a 2‑approximation turned into an optimal solution via a tailored 2‑stretch perturbation; asymmetric case defines a set A of good points (points mutual within r), builds r balls, prunes by a margin and subset rules, then attaches remaining points. r* is guessed from O(n^2) candidate distances; hardness uses reductions from Dominating Set and Valiant‑Vazirani.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 6:12Perturbation Resilience
3. 13:49Prior Work
4. 17:00Case Center
5. 20:46Asymmetric Case
6. 22:37Properties
7. 24:40Useful Properties
8. 25:46Key Observation
9. 27:29Algorithm
10. 30:23Optimal Algorithm
11. 34:45Conclusion
12. 36:01Discussion

" related talks

• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 40mMonte Carlo Approximation Certificates for K-Means ClusteringDustin Mixon · Sublinear Algorithms and Nearest-Neighbor Search
• 37mPower to the Points: Local Certificates for ClusteringsSuresh Venkatasubramanian · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian MixturesPravesh K. Kothari · Computational Phase Transitions (Simons Institute, 2020)
• 51mExact Recovery via Convex RelaxationsMoses Charikar · Spectral Algorithms: From Theory to Practice 2014
• 38mRed Points and Blue PointsSantosh Vempala · The Role of TCS in Modern Machine Learning
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 48mUnstructured Hardness to Average-Case RandomnessRoei Tell · Lower Bounds, Learning, and Average-Case Complexity