Sampling Counting Input:a CSP formula=(V,O,C) Output: .(sampling)almost uniform random satisfying solution .(counting)an estimation of of satisfying solutions exact counting is #P-hard self-reduction Almost Uniform [Jerrum,Valiant,Vazirani 1986] Approximate Sampling adaptive simulated annealing Counting [Stefankovic,Vempala,Vigoda 2009] Application:inference in probabilistic graphical models Gibbs distribution cw=Πc(a） where each c:&g→Ro iEvbl(c) Inference:Pr [X;=IXs =xs] X~u• exact counting is #P-hard • • Application: inference in probabilistic graphical models Sampling & Counting Input: a CSP formula Output : • (sampling) uniform random satisfying solution • (counting) # of satisfying solutions Φ = (V, Q,C) an estimation of almost Almost Uniform Sampling Approximate Counting self-reduction [Jerrum, Valiant, Vazirani 1986] adaptive simulated annealing [Štefankovič, Vempala, Vigoda 2009] c : i∈ ⨂ 𝗏𝖻𝗅(c) μ Qi → ℝ≥0 (x) ∝ Φ(x) = ∏ c∈C c (x𝗏𝖻𝗅(c)) Inference: Pr X∼μ [Xi = ⋅ ∣ XS = xS] Gibbs where each distribution