Abstract
To date, adaptive, polylog update time dynamic matching algorithms have been developed yielding (½-ɛ) approximation, and (½+δ)-approximate size estimation. Key to both types of fast algorithms are dynamic rounding of dynamic fractional matching algorithms, using sparsification via (partial) rounding. In this talk I will overview the line of work on rounding via sparsification via rounding. Along the way, I will highlight two new algorithmic primitives robust to adaptive adversaries, and hence of potential use for the design of fast static algorithms: (1) fast almost maximal matching (AMM) algorithms, and (2) optimal dynamic subset sampling algorithms. Time permitting, I will briefly discuss the role AMMs play in the current best polylog time (½+δ)-approximate dynamic matching size estimation algorithms.