  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. For instance, an algorithm of Behnezhad
[FOCS'21] obtains a 1/2-approximation in $\tilde{O}(n)$ time for $n$-vertex
graphs. A more recent algorithm by Behnezhad, Roghani, Rubinstein, and Saberi
[SODA'23] obtains a slightly-better-than-1/2 approximation in
$O(n^{1+\epsilon})$ time. On the lower bound side, Parnas and Ron [TCS'07]
showed 15 years ago that obtaining any constant approximation of maximum
matching size requires $\Omega(n)$ time. Proving any super-linear in $n$ lower
bound, even for $(1-\epsilon)$-approximations, has remained elusive since then.
  In this paper, we prove the first super-linear in $n$ lower bound for this
problem. We show that at least $n^{1.2 - o(1)}$ queries in the adjacency list
model are needed for obtaining a $(\frac{2}{3} + \Omega(1))$-approximation of
maximum matching size. This holds even if the graph is bipartite and is
promised to have a matching of size $\Theta(n)$. Our lower bound argument
builds on techniques such as correlation decay that to our knowledge have not
been used before in proving sublinear time lower bounds.
  We complement our lower bound by presenting two algorithms that run in
strongly sublinear time of $n^{2-\Omega(1)}$. The first algorithm achieves a
$(\frac{2}{3}-\epsilon)$-approximation; this significantly improves prior
close-to-1/2 approximations. Our second algorithm obtains an even better
approximation factor of $(\frac{2}{3}+\Omega(1))$ for bipartite graphs. This
breaks the prevalent $2/3$-approximation barrier and importantly shows that our
$n^{1.2-o(1)}$ time lower bound for $(\frac{2}{3}+\Omega(1))$-approximations
cannot be improved all the way to $n^{2-o(1)}$.
