Dynamic Matching Algorithms and Dynamic Matching Sparsifiers
Summary: In this talk I give a brief overview of the dynamic matching literature, and emphasize one key ingredient in many of the known dynamic matching algorithms: dynamically maintaining matching sparsifiers.
(Part of the STOC'22 Workshop on Dynamic Algorithms)
Dynamic Matching: Rounding & Sparsification (and New Tools)
Summary: In this talk I give an overview of key tools for polylog update time dynamic matching: rounding of fractional matchings, and sparsification. (Bonus@end: overview of a few new adaptive data structures of broader interest.)
(Part of the Simons Workshop on Dynamic Graphs and Algorithms Design)