Decay of Correlation (Weak Spatial Mixing,WSM) Pr[v∈I|o] hardcore model: I-u →∞ (d+1)-regular tree ---0 boundary condition o:fixing leaves at level l to be occupied/unoccupied by I WSM:Pr[lv∈I|o]does not depend on o when l-→o uniqueness threshold:Xc= (d-1)d+1) ●入≤入c台VSM holds on(d+l)-regular tree台Gibbs measure is unique ·Veitz'06]:λ<λc→FPTAS for graphs with max-degree≤dtl [Galanis,Stefankovic,Vigoda'12;Sly,Sun'12]:>e inapproximable unless NP=RP(d+1)-regular tree ` ! 1 v boundary condition σ : fixing leaves at level l to be occupied/unoccupied by I Pr[v 2 I | ￾] Decay of Correlation ￾c = dd (d ￾ 1)(d+1) hardcore model: (Weak Spatial Mixing, WSM) uniqueness threshold: • λ ≤ λc 㱻 WSM holds on (d+1)-regular tree 㱻 Gibbs measure is unique • [Weitz ‘06]: λ < λc 㱺 FPTAS for graphs with max-degree ≤ d+1 • [Galanis, Štefankovič, Vigoda ‘12; Sly, Sun ‘12]: λ > λc 㱺 inapproximable unless NP=RP WSM: Pr[v∈I | σ] does not depend on σ when l→∞ I ∼μ