Decremental Shortest Paths against an Adaptive Adversary

on YouTube ↗01h 02m

" summary

Claims a near-optimal deterministic decremental single-source shortest paths data structure that removes the oblivious-adversary assumption and achieves m^{1+o(1)} total update time for (1+ε)-approximate distances. Key tools include congestion balancing (fractional matchings with capacity doubling) to spread importance across edges, and maintaining expander witnesses / pruning to keep a robust low-diameter core under many deletions. Presents a matching subroutine (polylog updates for decremental approx matching) and potential-based analyses showing the constructions are provably efficient.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 1:50Matching
3. 5:35Lazy Approach
4. 9:23Capturing Criticality
5. 11:00Algorithm
6. 16:15New phase
7. 24:00Time analysis
8. 28:53Potential function
9. 36:35What was known
10. 38:34Data structures
11. 39:08Low diameter balls
12. 40:24Definitions
13. 40:37Example
14. 43:44Results
15. 44:55Previous attempts
16. 46:58The Simple Trick
17. 53:59Congestion Balancing