Reproduce “Maximum Cardinality Matching in $n^{2+o(1)}$ Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
George Z. Li, Jason Li, Junkai Zhang
The algorithm finds a maximum matching in an unweighted general graph by searching a growing subgraph for regular augmenting paths and sampling edges from the full graph when a barrier blocks progress. It represents matching as integral symmetric flow and adds sampled bypass edges. It achieves n^{2+o(1)} time with high probability, a guarantee aimed at dense graphs, not measured runtime.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.