Some Emergency Barriers to Worst-Case Dynamic MST

on YouTube ↗45m

" summary

Identifies an explicit barrier: to beat the 30-year-old O(sqrt n) worst-case update for dynamic MST one must first build an emergency cut size oracle whose preprocessing, update and query times all improve over sqrt n (queries may pay an extra Delta_s factor). Provides a concrete oracle that outputs the cut set and runs in sublinear time (preprocess ≈ n^{1/2+o(1)}, updates and queries ≈ n^{1/3+o(1)}), using sketching, high-expansion decomposition plus flow/cut-matching ingredients and persistent data structures. Results hold but stop short of polylog.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 0:34Notations
3. 2:25Our focus: emergency cut-size oracle
4. 2:57Lessons from emergency cut-size oracle barrier
5. 5:39Connectivity (simplified) Maintain if the graph is connected
6. 6:06Spanning Tree (ST) Maintain a spanning tree
7. 7:34Worst-Case Update Time T
8. 8:20Amortized Update Time T
9. 10:36Questions
10. 13:07Emergency setting Only one batch of updates
11. 13:59Example: Emergency MST
12. 14:35Why emergency barriers?
13. 16:09Example Emergency MST is a barrier to dynamic MST
14. 21:07Static cut-size oracle
15. 25:10Emergency cut-size is a barrier to dynamic MST
16. 31:48Side results
17. 34:52Techniques we need
18. 38:46High expansion decomposition
19. 40:22Algorithm for sparse H.
20. 40:48Algorithm for high-expansion H
21. 42:46Open problems