Sampling an Edge in $O(n/\sqrt{m} + \log \varepsilon^{-1})$ Time via Bernoulli Trial Simulation

Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of the graph and know a constant-factor approximation to the number of edges. An algorithm for pointwise $\varepsilon$-approximate edge sampling with complexity $O(n/\sqrt{\varepsilon m})$ has been given by Eden and Rosenbaum [SOSA 2018]. This has been later improved by T\v{e}tek and Thorup [STOC 2022] to $O(n \log(\varepsilon^{-1})/\sqrt{m})$. At the same time, $\Omega(n/\sqrt{m})$ time is necessary. We close the problem, under the assumption of knowing $m$ up to a constant factor, for all but very dense graphs by giving an algorithm with complexity $O(n/\sqrt{m} + \log \varepsilon^{-1})$. Our algorithm is based on a new technique that we call \emph{Bernoulli trial simulation}. We believe this technique could also be useful for other problems. Given access to trials of the form $Bern(p)$, this technique allows us to simulate a Bernoulli trial $Bern(f(p) \pm \varepsilon)$ (without knowing $p$), in time complexity $O(\log \varepsilon^{-1})$ for some functions $f$. We specifically use this for $f(p) = 1/(2p)$ for $p \geq 2/3$. Therefore, we can perform rejection sampling, without the algorithm having to know the desired rejection probability. We conjecture Bernoulli trial simulation for $f(p) = 1/(2p)$ can be done exactly in expected $O(1)$ samples. This would lead to an exact algorithm for sampling an edge with complexity $O(n/\sqrt{m})$, completely resolving the problem of sampling an edge, again assuming rough knowledge of $m$. We consider the problem of removing this assumption to be an interesting open problem.