A 0.51-Approximation of Maximum Matching in Sublinear n^1.5 Time

We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bounds are known for it. Our result is a $0.5109$-approximation algorithm with a running time of \(\tilde{O}(n\sqrt{n})\). All previous algorithms either provide only a marginal improvement (e.g., $2^{-280}$) over the $0.5$-approximation that arises from estimating a maximal matching, or have a running time that is nearly \(n^2\). Our approach is also arguably much simpler than other algorithms beating $0.5$-approximation.