hardcore model monomer-dimer model undirected graph G=V,E) activity入 configurations: independent sets matchings M weight: w(D=入M w(M)=入M partition function: Z=1:independent sets in GW(D =EM:matchingsin G W(M) Gibbs distribution: u(D)=w(D/Z u(M)=w(M)/Z approximate counting: FPTAS/FPRAS for Z sampling:sampling from u within TV-distance s in time poly(n,log1/8)hardcore model monomer-dimer model configurations: independent sets I matchings M weight: w(I) = λ|I| w(M) = λ|M| partition function: Z = ΣI:independent sets in G w(I) Z = ΣM:matchings in G w(M) Gibbs distribution: μ(I) = w(I) / Z μ(M) = w(M) / Z approximate counting: sampling: FPTAS/FPRAS for Z sampling from μ within TV-distance ε in time poly(n, log1/ε) G = (V,E) undirected graph λ λ λ λ λ λ λ activity λ λ λ