The problem of uniformly sampling graphs with given degrees is important for the statistical study of many real-world networks. Existing algorithms fall into two broad categories: combinatorial algorithms, which work well for sparse graphs but can be exponentially bad for dense ones, and Markov Chain Monte Carlo, which always runs in polynomial time but is impractically slow.

In this talk, I will present a new algorithm that is in some sense a hybrid of these two techniques, which achieves best-possible runtime for sparse graphs as well as an important class of dense graphs. The idea is a fairly simple one, involving expanding the state space and contracting back down in a way that maintains uniformity, and is applicable to a variety of other combinatorial families.