  Functional verification constitutes one of the most challenging tasks in the
development of modern hardware systems, and simulation-based verification
techniques dominate the functional verification landscape. A dominant paradigm
in simulation-based verification is directed random testing, where a model of
the system is simulated with a set of random test stimuli that are uniformly or
near-uniformly distributed over the space of all stimuli satisfying a given set
of constraints. Uniform or near-uniform generation of solutions for large
constraint sets is therefore a problem of theoretical and practical interest.
For Boolean constraints, prior work offered heuristic approaches with no
guarantee of performance, and theoretical approaches with proven guarantees,
but poor performance in practice. We offer here a new approach with theoretical
performance guarantees and demonstrate its practical utility on large
constraint sets.

Logic in Computer Science