Return to Colloquia & Seminar listing
Approximating maximum matching requires almost quadratic time
Joint Math/CS Theory| Speaker: | Mohammad Roghani, Google Research |
| Location: | 1131 Kemper |
| Start time: | Mon, Mar 9 2026, 1:10PM |
Description
Linear-time complexity has traditionally defined the limits of algorithmic efficiency. But is it possible to break this barrier and achieve sublinear runtimes? In this talk, I explore the lower bounds of estimating maximum matching sizes. I will highlight a recent technique demonstrating that, for certain approximation ratios, achieving such estimates requires super-linear time relative to the number of nodes.
Based on joint works with Soheil Behnezhad and Aviad Rubinstein.