  We study local computation algorithms (LCA) for maximum matching. An LCA does
not return its output entirely, but reveals parts of it upon query. For
matchings, each query is a vertex $v$; the LCA should return whether $v$ is
matched -- and if so to which neighbor -- while spending a small time per
query.
  In this paper, we prove that any LCA that computes a matching that is at most
an additive of $\epsilon n$ smaller than the maximum matching in $n$-vertex
graphs of maximum degree $\Delta$ must take at least
$\Delta^{\Omega(1/\varepsilon)}$ time. This comes close to the existing upper
bounds that take $(\Delta/\epsilon)^{O(1/\epsilon^2)} polylog(n)$ time.
  In terms of sublinear time algorithms, our techniques imply that any
algorithm that estimates the size of maximum matching up to an additive error
of $\epsilon n$ must take $\Delta^{\Omega(1/\epsilon)}$ time. This negatively
resolves a decade old open problem of the area (see Open Problem 39 of
sublinear.info) on whether such estimates can be achieved in
$poly(\Delta/\epsilon)$ time.
