Our Results deg d+1 ci deg sk+1 C2 independent sets of hypergraphs c3 of max-degree≤d+1 and max-edge-size≤k+l ( C4 partition function: Z= 入川1 元∈{0,1}n satisfying Boolean at-most-1 all constraints variables constraints uniqueness threshold for (k+1)-uniform(d+1)-regular infinite hypertree: dd Ae(k,d)=k(d-1)d+ ●λ<λc:FPTAS ·A>2+yX≈2Xe:inapproximable unless NP=.RP
Our Results • uniqueness threshold for (k+1)-uniform (d+1)-regular infinite hypertree: • λ<λc: FPTAS • : inapproximable unless NP=RP c(k, d) = dd k(d 1)d+1 > 2k+1+(1)k k+1 c ⇡ 2c Boolean variables deg ≤ d+1 deg ≤ k+1 x1 x2 x3 x4 x5 c1 c2 c3 c4 c5 c6 c7 at-most-1 constraints Z = X ~x2{0,1}n satisfying all constraints k~ xk1 independent sets of hypergraphs of max-degree ≤ d+1 and max-edge-size ≤ k+1 partition function:
=1:matchings of hypergraphs of max-degree(+1)and max-edge-size(d+1) independent sets of hypergraphs of max-degree(d+1)and max-edge-size(k+1) uniqueness threshold: uniqueness threshold dd hard 入。=kd-1)a+可 easy threshold for hardness: [Liu-Lu 201:5] 2+)λ≈2入。 k+1 : : [Dudek et al.2014] d (4,2: independent sets of 3-uniform hypergraphs of max-degree 5, the only open case for counting Boolean CSP with max-degree 5. (2,4):matchings of 3-uniform hypergraphs of max-degree 5, exact at the critical threshold: 、 dd 22 k(d-1)a+西=4.15=1
1 2 3 4 5 6 2 3 4 5 6 k d λ = 1: easy hard matchings of hypergraphs of max-degree (k+1) and max-edge-size (d+1) independent sets of hypergraphs of max-degree (d+1) and max-edge-size (k+1) (2,4): matchings of 3-uniform hypergraphs of max-degree 5, exact at the critical threshold: uniqueness threshold dd k(d 1)(d+1) = 22 4 · 15 = 1 [Dudek et al. 2014] [Liu-Lu 2015] c = dd k(d 1)(d+1) uniqueness threshold: threshold for hardness: 2k+1+(1)k k+1 c ⇡ 2c (4,2): independent sets of 3-uniform hypergraphs of max-degree 5, the only open case for counting Boolean CSP with max-degree 5
Spatial Mixing (Decay of Correlation) weak spatial mixing (WSM): Prlv is occupied oar]Prlv is occupied Tar] error exp (-t) strong spatial mixing (SSM): Prlv is occupied OaR,]Prlv is occupied TaR, H by self-reduction: Prv is occupied] ∂R is approximable with additive error g in time poly(n,1/8) FPTAS for partition function Z
Spatial Mixing (Decay of Correlation) R H v t ⇤ strong spatial mixing (SSM): error < exp (-t) @R Pr[v is occupied | @R] ⇡ Pr[v is occupied | ⌧@R] Pr[v is occupied | @R, ⇤] ⇡ Pr[v is occupied | ⌧@R, ⇤] weak spatial mixing (WSM): Pr[v is occupied | ⇤] by self-reduction: FPTAS for partition function Z is approximable with additive error ε in time poly(n, 1/ε)