Seminar • Algorithms and Complexity • Dynamic Matching with (2-eps) Approximation in Polylog Time

Please note: This seminar will take place in M3 4206 and online.

David Wajc, Senior Lecturer | Assistant Professor, Taub Fellow
The Technion, Israel Institute of Technology

In this talk I will present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. These algorithms answer in the affirmative (the value version of) a major open question repeatedly asked in the dynamic graph algorithms literature. I will give a high-level idea of the key ingredients needed for this result, and discuss subsequent developments.

Based on a SODA 2023 best paper, joint with Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak.

To attend this seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/92238539064.