Approximately counting and sampling edges uniformly, parameterized by the arboricity


Talya Eden


Govind Ramnarayan, Quanquan Liu, Sitan Chen, NIkhil Vyas
Abstract: I will start by describing an very simple algorithm for approximating the number of edges in a graph. Then I turn to describe the problem of sampling edges from a distribution that is point-wise almost uniform.
Given query access to a graph G over n vertices, m edges and a bound
\alpha on the arboricity of G, both algorithms have O((n\alpha)/m) expected query complexity, so they improve on the previous O(n/\sqrt m) bound for both problems.

This talk is based on joint works with Dana Ron, Will Rosenbaum and C.