“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 ϵn smaller than the maximum matching in n-vertex graphs of maximum degree Δ must take at least Δ^Ω(1/ε) time.”

Find the paper and full list of authors at ArXiv.