Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

on YouTube ↗27m

" summary

A constant-factor correlation clustering algorithm appears with only adjacency list of positive subgraph access: randomized algorithm runs in O(n log^2 n) time and outputs a clustering within a constant (practically 10^5–10^6) multiplicative factor. A single-pass streaming algorithm uses O~(n) single-pass space (about n log n edges sampled) to produce the same guarantee. Both use a new sparse-dense decomposition plus neighborhood sampling (extendable to dynamic streams via L0 sampling) and the constructions and bounds are implemented and analyzed.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:20Correlation Clustering - The motivation
3. 1:41Correlation Clustering - Problem Definition
4. 4:27Classical Results for Correlation Clustering
5. 5:10The Quest for Sublinear Correlation Clustering
6. 9:18Sublinear Space Correlation Clustering
7. 11:45Efficient Correlation Clustering - Main Challenge
8. 12:24Efficient Correlation Clustering - New Ideas
9. 17:39Graph Sparse-dense decomposition
10. 21:13Correlation Clustering - Sublinear Algorithms
11. 24:50The 'Right Model for Sublinear Time Algorithm
12. 25:29The Power of our Streaming Algorithm
13. 25:58Summary
14. 26:32Open Problems