Recent Progress on Sublinear Time Algorithms for Maximum Matching: Lower Bounds
summary
Proves a concrete hardness: any better-than-2/3 approximation to maximum matching in the adjacency‑list model requires about n^{1.2} queries by building a dense “core + dummy” distribution with core degree d = n^{0.2} and showing sub‑n^{1.2} probes cannot see cycles. Key tools are a correlation decay argument that reduces querying to indistinguishable random trees and a careful counterexample (random‑walks defeat naive hardness) so the lower bound survives adaptive algorithms.
AI-written summary · about