Approximately counting and sampling edges uniformly, parameterized by the arboricity
Speaker
Talya Eden
Host
Govind Ramnarayan, Quanquan Liu, Sitan Chen, NIkhil Vyas
CSAIL MIT
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.
Seshadhri.
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.
Seshadhri.