Is it easier to count communities than find them?

on YouTube ↗24m

" summary

Defines a planted dense submatrix model with additive Gaussian noise and studies testing between one planted community and M planted communities (the count 1 vs M problem). Main claims: a degree‑1 diagonal sum test separates cases when Mλk vs λk concentrates, a signed‑triangle statistic handles the binary graph case, and low‑degree polynomial lower bounds (degree up to O(log n)) match recovery thresholds, so counting is as hard as recovery in the same parameter regimes.

AI-written summary · about

" chapters (14)

1. 0:00Introduction
2. 0:35The model
3. 1:35Phase diagrams
4. 2:24Mplanted communities
5. 4:32Formal Statement
6. 5:58Hardness
7. 7:20Binary model
8. 8:07No diagonal entries
9. 9:37Reduction
10. 11:32No guarantee
11. 11:51Calculating sum
12. 12:52Determining sum
13. 13:41Print techniques
14. 15:18R structure

" related talks

• 25mFundamental Limit of Community Detection in Stochastic Block ModelsEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)Fedrico Ricci-Tersenghi · Random Instances and Phase Transitions (Simons Institute, 2016)
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional ClustCris Moore · Random Instances and Phase Transitions (Simons Institute, 2016)
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)