Return to Colloquia & Seminar listing
A framework for boosting matching approximation: parallel, distributed, and dynamic
Joint Math/CS Theory| Speaker: | Wen-Horng Sheu, UC Davis |
| Related Webpage: | https://whsheu.github.io/ |
| Location: | 1131 Kemper |
| Start time: | Mon, Apr 6 2026, 1:10PM |
Description
In this talk, I will discuss a framework for boosting the approximation guarantee of maximum matching algorithms. As input, the framework receives a parameter ε > 0 and oracle access to an O(1)-approximate maximum matching algorithm A. Then, by invoking A for poly(1/ε) many times, the framework outputs a (1+ε)-approximation of a maximum matching. Compared to prior work, the framework yields several improvements in terms of the number of invocations to A:
1. In the MPC and CONGEST models, the framework invokes A for O(1/ε^7 · log(1/ε)) times, substantially improving on O(1/ε^39) invocations following from [Fischer et al., STOC’22] and [Mitrovic et al., arXiv:2412.19057].
2. In both online and offline fully dynamic settings, the framework yields an improvement in the dependence on 1/ε from exponential [Assadi et al., SODA25 and Liu, FOCS24] to polynomial.
This talk is based on joint work with Slobodan Mitrović.