Lucky Talk: From Coding to Clustering

on YouTube ↗25m

" summary

Exact recovery for the stochastic block model is pinned down: with p = a log n / n and q = b log n / n the two-group symmetric case has a sharp solvability threshold, and the general K-community case is characterized by a statistical divergence (the CH divergence) between columns of the P·Q matrix. Previous polynomial methods used an SDP N^5 approach; a new algorithm attains the information-theoretic threshold with quasi-linear complexity n^{1+ε}.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 2:34Recovery Detection
3. 6:48General Results
4. 17:08The Coding Clustering

" related talks

• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 24mStochastic Block Models with R: Statistically rigorous clusteringNick Strayer · rstudio::conf 2019
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 40mClustering Under Perturbation ResilienceColin White · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)