Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds
summary
Recent claims: estimating maximum matching size can run sublinearly and feed fast dynamic algorithms. Concrete results include a greedy oracle that decides whether a random vertex is matched using recursive queries on a random permutation, yielding a 1/2 estimate in roughly O(n) total work and enabling a 0.58 approximation via sampling; a lazy amortization reduction turns static T-time estimators into T/n update-time dynamic algorithms; and a proven n^{1.2} lower bound rules out >2/3 approximation in sublinear time.
AI-written summary · about