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.