  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}).
