Counting Independent Set hardcore model:undirected graph G(V,E)fugacity>0 IV()T is an independent set in c otherwise partition function:Z=ZG(A)=>w(I) ICV e uniqueness threshold:Ac(A)= (△-1)A-1 (△-2)A △-2 Computing Zc()in graphs with constant max-degree <A ●入<λc(△)→FPTAS [Weitz06] strong spatial mixing ●λ>λc(△)→no FPRAS unless NP=RP [Galanis Stefankovie Vigoda 12][Sly Sun 12]Counting Independent Set hardcore model: • λ < λc(Δ) 㱺 FPTAS • λ > λc(Δ) 㱺 no FPRAS unless NP=RP ∀ I ⊆ V: uniqueness threshold: Computing ZG(λ) in graphs with constant max-degree ≤ ∆ [Galanis Štefankovič Vigoda 12] [Sly Sun 12] [Weitz 06] undirected graph G(V,E) fugacity λ > 0 partition function: Z = ZG(￾) = X I✓V w(I) w(I) = ( ￾|I| I is an independent set in G 0 otherwise ￾c(￾) = (￾ ￾ 1)￾￾1 (￾ ￾ 2)￾ ⟸ strong spatial mixing ⇡ e ￾ ￾ 2