Build a Learning Habit
Download Class Central's free printable study calendar
Download for Free
Explore dynamic matching algorithms and their applications in this lecture from the Simons Institute. Delve into adaptive, polylog update time dynamic matching algorithms yielding (½-ɛ) approximation and (½+δ)-approximate size estimation. Examine the key techniques of dynamic rounding and sparsification via partial rounding. Learn about two new algorithmic primitives robust to adaptive adversaries: fast almost maximal matching (AMM) algorithms and optimal dynamic subset sampling algorithms. Discover the role of AMMs in current polylog time (½+δ)-approximate dynamic matching size estimation algorithms. Gain insights into the latest developments in dynamic graphs and algorithm design from David Wajc of the Technion - Israel Institute of Technology.
