Please note: This seminar will take place in DC 1304 and online.
Vihan Shah, University of Birmingham
We study the problem of estimating the size of the maximum matching in the sublinear-time setting. This problem has been extensively studied, with several known upper and lower bounds. A notable result by Behnezhad (FOCS 2021) established a 2-approximation in O~(n) time.
However, all known upper and lower bounds are in the adaptive query model, where each query can depend on previous answers. In contrast, non-adaptive query models—where the distribution over all queries must be fixed in advance—are widely studied in property testing, often revealing fundamental gaps between adaptive and non-adaptive complexities. This raises the natural question: is adaptivity also necessary for approximating the maximum matching size in sublinear time? This motivates the goal of achieving a constant or even a polylogarithmic approximation using O~(n) non-adaptive adjacency list queries, similar to what was done by Behnezhad using adaptive queries.
We show that this is not possible by proving that any randomized non-adaptive algorithm achieving an n^{1/3 - gamma}-approximation, for any constant gamma > 0, with probability at least 2/3, must make Omega(n^{1 + eps}) adjacency list queries, for some constant eps > 0 depending on gamma. This result highlights the necessity of adaptivity in achieving strong approximations. However, non-trivial upper bounds are still achievable: we present a simple randomized algorithm that achieves an n^{1/2}-approximation in O(n \log n) queries.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.