Reproduce “The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation” 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
Chenglin Fan, Wonseok Shin
The authors estimate edge counts and fixed degree moments from random edge samples and endpoint-degree queries, without graph-parameter advice. Their query bounds depend on matching number ν: O(min{ν/ε, 1/ε² + √ν/ε}) for edges and O(min{ν^(1−1/s)/ε^(2/s), ν^(1−1/(2s−1))/ε^(2/(2s−1))}) for moments. The rates are worst-case optimal for matching number at most k and sufficiently small ε; individual graphs may be easier.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.