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.

Short Bio:
Vihan Shah is a Postdoctoral Researcher at the University of Birmingham, working with Sagnik Mukhopadhyay in the Theory of Computation group. He received his PhD from the University of Waterloo, advised by Sepehr Assadi. His research focuses on graph algorithms in modern models of computation such as streaming, sublinear-time, and dynamic settings.