Efficient Generation ε-close to G(n,p) and Generalizations

Antonio Blanca, Milena Mihail

We give an efficient algorithm to generate a graph from a distribution $\epsilon$-close to $G(n,p)$, in the sense of total variation distance. In particular, if $p$ is represented with $O…