Sampling vs Counting [Jerrum-Valiant-Vazirani86]:for all self-reducible problems approx counting exact sampling vol(R) X=(X1,X2,,X) Poly-Time Turing approx inference X~2 Machine Pr[X,=·|X=o] DOMIZED RANDOM GENERATION OF COMBINATORIAL STRUCTURES RITHMS FROM A UNIFORM DISTRIBUTION Mark R.JERRUM Department of Computer Science,University of Edinburgh,Edinburgh EH9 3JZ United Kingdom Leslie G.VALIANT Aiken Computation Laboratory,Harvard University,Cambridge,MA 02138,U.S.A. Vijay V.VAZIRANI** Computer Science Department,Comell University,Ithaca,NY 14853,U.S.A.Sampling vs Counting sampling exact approx { } X = (X1, X2, …, Xn) approx counting vol(Ω) approx inference Pr[Xi = ⋅ ∣ XS = σ] ( [Jerrum-Valiant-Vazirani ’86]: Poly-Time Turing Machine for all self-reducible problems X ∼ Ω