# Uniform generation of random regular graphs

arXiv: https://arxiv.org/abs/1511.01175 · HTML: https://mlsanity.com/paper/1511.01175/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2015.

## Built on by (most cited first, 4 of 4)

- [Lifted Algorithms for Symmetric Weighted First-Order Model Sampling](https://mlsanity.com/paper/2308.08828/) (2023)
- [On Exact Sampling in the Two-Variable Fragment of First-Order Logic](https://mlsanity.com/paper/2302.02730/) (2023)
- [Energy-efficient Decentralized Learning via Graph Sparsification](https://mlsanity.com/paper/2401.03083/) (2024)
- [A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers](https://mlsanity.com/paper/2605.03391/) (2026)

## Abstract (arXiv)

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd^3), provided that d=o(n^{1/2}). Our result significantly improves the previously best uniform sampler, which works efficiently only when d=O(n^{1/3}), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d=o(n^{1/2}).