Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
Abstract
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 \(\tilde O(n)\) time.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Machine Learning and Algorithms
Optimization and Search Problems
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5027–5065
- Publication date
- 1 January 2026
- Language
- EN