Decay of Correlation hardcore model: Pr[v∈I|o] H(I)xIII a+I)-ur。o →∝ ○-○-○- o:fixing leaves to be occupied/unoccupied by I Decay of correlation:Pr[velI o]does not depend on o when d if入≤入。=(d-1)a+西 counting total weights n of all I.S.in graphs with max-degree <d+1 ●λ<λc→FPTAS[Weitz06] ●λ>λc→no FPRAS unless NP=RP [Sly10][Galanis Stefankovie Vigoda 12][Sly Sun 12]regular tree ` ! 1 v σ: fixing leaves to be occupied/unoccupied by I Pr[v 2 I | ￾] Decay of Correlation hardcore model: • λ < λc 㱺 FPTAS • λ > λc 㱺 no FPRAS unless NP=RP Decay of correlation: Pr[v∈I | σ] does not depend on σ when l→∞ random independent set I iff counting total weights λ|I| of all I.S. in graphs with max-degree ≤ d+1 [Sly10] [Galanis Štefankovič Vigoda 12] [Sly Sun 12] [Weitz 06] (d+1)-