  We study the problem of estimating the size of maximum matching and minimum
vertex cover in sublinear time. Denoting the number of vertices by $n$ and the
average degree in the graph by $\bar{d}$, we obtain the following results for
both problems:
  * A multiplicative $(2+\epsilon)$-approximation that takes
$\tilde{O}(n/\epsilon^2)$ time using adjacency list queries.
  * A multiplicative-additive $(2, \epsilon n)$-approximation in
$\tilde{O}((\bar{d} + 1)/\epsilon^2)$ time using adjacency list queries.
  * A multiplicative-additive $(2, \epsilon n)$-approximation in
$\tilde{O}(n/\epsilon^{3})$ time using adjacency matrix queries.
  All three results are provably time-optimal up to polylogarithmic factors
culminating a long line of work on these problems.
  Our main contribution and the key ingredient leading to the bounds above is a
new and near-tight analysis of the average query complexity of the randomized
greedy maximal matching algorithm which improves upon a seminal result of
Yoshida, Yamamoto, and Ito [STOC'09].
