Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries

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-γ -approximation, for any constant γ > 0, with probability at least 2/3, must make Ω(n 1+ε ) adjacency list queries, for some constant ε > 0 depending on γ. 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 2 n) queries.

Moreover, our lower bound also extends to the newly defined variant of the non-adaptive model, where queries are issued according to a fixed query tree, introduced by Azarmehr, Behnezhad, Ghafari, and Sudan (FOCS 2025) in the context of Local Computation Algorithms.