Sublinear Algorithms for (1.5+ε)-Approximate Matching

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad ‍[FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. ‍[SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time.