Answers are grounded in this paper and cite their sources.
A local computation algorithm (LCA) for matching answers ``who is the mate of v?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For n-vertex graphs of maximum degree Δ≥2, Levi et al. [Algorithmica'17] give a (1-ε)-approximate matching LCA using (Δ/ε)O(1/ε²) polylog(n) queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error ε n using ΔO(1/ε²) queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a ΔΩ(1/ε) lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive ε n error. This leaves a gap between linear and quadratic dependence on 1/ε in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with ΔO(1/ε) queries for a (1-ε)-approximate matching, and an estimator for the maximum matching size within ε n using ΔO(1/ε) queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs O(ε⁻¹logΔ) rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.
No takes yet. Share an insight, caveat, or question.
Cohen et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: