Explore the complexities of clustering algorithms in Lp metrics through this 21-minute IEEE conference talk. Delve into the structure of computational problems, focusing on continuous clustering and its inherent difficulties. Examine approximation algorithms and the hardness of approximation in this context. Learn about key concepts such as the Vertex Edge Game, randomness, and graph embedding. Understand the significance of the Johnson Coverage Hypothesis in inapproximability. Gain valuable insights into the challenges of clustering problems and their implications in computational complexity theory.
Overview
Syllabus
Introduction
Structure of computational problems
Clustering
Continuous Clustering
Clustering is a Hard Problem
Approximation Algorithms
Hardness of Approximation
Results
Proof
Vertex Edge Game
Randomness
Graph embedding
Key takeaways
Johnson Coverage Hypothesis
In Approximability
Conclusion
Questions
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
-
Smoothed Complexity of 2-player Nash Equilibria
-
Hardness Magnification for All Sparse NP Languages
-
Communication Complexity of Nash Equilibrium in Potential Games
-
Tree-Depth and the Formula Complexity of Subgraph Isomorphism
-
Is it Easier to Prove Statements that are Guaranteed to be True?
-
On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs
