Practical Dynamic Graph Algorithms: Data Structures and Connections Between Models

on YouTube ↗43m

" summary

Describes a transferable approach: level data structures that partition vertices into O(log n) levels and move active vertices by checking induced-degree thresholds, yielding a 2+η approximation for k-core with work matching best sequential bounds and polylog depth in the batch-shared-memory model; deterministic variant adds polylog factors. The same structure converts to MPC (more rounds than static algorithms) and to local edge-differential privacy by adding independent geometric noise per activation, giving an extra O(log^2 n / ε) additive error and one-sided 2+η guarantee.

AI-written summary · about

" chapters (12)

1. 0:00Practical dynamic graph intro
2. 1:28Graph representation models
3. 4:41Batch vs streaming models
4. 6:38Adversarial models & privacy
5. 15:26Combining models for frameworks
6. 17:58Transferable graph data structures
7. 19:45Locally adjustable algorithms
8. 22:46K-core decomposition overview
9. 27:07Level data structures for k-core
10. 32:08Complexity measures overview
11. 36:46Open questions & future research
12. 38:13Q&A