The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation

Chenglin Fan, Wonseok Shin

Consider an unknown graph $G=(V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query co…