“Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. … A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O(n1+є) time (for arbitrarily small constant ε>0). … Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive. … In this paper, we prove the first super-linear in n lower bound for this problem.”

Find the paper and authors list in the Proceedings of the 55th Annual ACM Symposium on Theory of Computing.