Deterministic Dynamic Matching In Worst-Case Update Time
summary
Presents deterministic dynamic algorithms that give a 2+ε approximate matching with polylog worst-case update time and a 3/2+ε guarantee in Õ(√n) worst-case update time randomized against adaptive adversaries, plus a deterministic 3/2+ε variant incurring n^{o(1)} overhead. Uses a black-box transformation from amortized rebuild-based to K-batch dynamic algorithms, a semi‑linear static construction of an edge degree constrained subgraph (EDCS), random or expander-based vertex contractions, and packing multiple output “tapes” to ensure one tape is always valid.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:25Matching Problem
- 1:18Worst-Case VS Amortized Update Time
- 2:41New Results
- 4:53K Batch-Dynamic Algorithms
- 6:14Black-Box Batch Dynamic to Worst-Case
- 8:15Improving Amortized Rebuild Based Dynamic Algorithms to k Batch-Dynamic
- 9:23Design of a Worst-Case Update Time Algorithm
- 10:42A Robust Datastructure
- 11:12Underlying Datastrucure: EDCS
- 12:20Difficulties
- 12:45Õ(m) Static Algorithm for Finding an EDCS
- 17:56Possible Research Directions
related talks
01h 00mHardness for Dynamic Problems; Conclusion and Future Research
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
10mQuery, Communication and Discrepancy
46mTiming Matters: Online Dynamics in Broadcast Games
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
58mExponential-Time Algorithms
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
39mSketching and Randomization for Distributed Submodular and Coverage Optimization