Sampling up to the Unigueness Threshold Yitong Yin Nanjing University Joint work with:Charis Efthymiou(Goethe-Universitat Frankfurt) Thomas P.Hayes (UNM) Daniel Stefankovic (Rochester) Eric Vigoda(Georgia Tech)
Sampling up to the Uniqueness Threshold Yitong Yin Nanjing University Joint work with: Charis Efthymiou (Goethe-Universität Frankfurt) Thomas P. Hayes (UNM) Daniel Štefankovič (Rochester) Eric Vigoda (Georgia Tech)
Sampling Independent Set undirected graph G(V,E)of max-degree A Sample(nearly)uniform random independent set
Sampling Independent Set • Sample (nearly) uniform random independent set. undirected graph G(V, E) of max-degree Δ
Sampling Independent Set undirected graph G(V,E)of max-degree A Sample (nearly)uniform random independent set. ●△≤5→poly-time Conjecture:O(n log n)time ●△≥6→NP.hard
Sampling Independent Set • Sample (nearly) uniform random independent set. • Δ ≤ 5 㱺 poly-time Conjecture: O(n log n) time • Δ ≥ 6 㱺 NP-hard undirected graph G(V, E) of max-degree Δ
Hardcore Model undirected graph G(V,E)of max-degree A fugacity parameter >0 each independent set in G is assigned a weight: w(I)=λII distribution u over all independent sets in G: w(I) (I)=Eru(① =1:uniform distribution over independent sets
Hardcore Model • fugacity parameter λ>0 • each independent set I in G is assigned a weight: • distribution μ over all independent sets in G: undirected graph G(V, E) of max-degree Δ w(I) = |I| µ(I) = w(I) P I w(I) • λ=1: uniform distribution over independent sets
Uniqueness Threshold Pr[v∈I|o] u(I)x入 △-regular tree 0-O○ o:boundary condition fixing each leaf El or g
Uniqueness Threshold regular tree ` v σ: boundary condition fixing each leaf ∈I or ∉I Pr[v 2 I | ] random independent set I Δ-
Uniqueness Threshold Pr[v∈I|o] (I)x入I △-regular tree →∞ 0-O○ o:boundary condition fixing each leaf EI org Critical phenomenon: Pr[v∈Ilo]is independent of o when /→∞ f入≤入c(△)= (△-1)A-1) (△-2)A
Uniqueness Threshold regular tree ` ! 1 v σ: boundary condition fixing each leaf ∈I or ∉I Pr[v 2 I | ] Critical phenomenon: random independent set I iff Δ- c() = ( 1)(1) ( 2) Pr[v∈I | σ] is independent of σ when l→∞
Uniqueness Threshold Pr[w∈I|o] random independent setI (I)x入I △-regular tree o:boundary condition fixing each leaf El or g Critical phenomenon: Pr[v∈IlO]is independent of o when l-∞ f入≤A(△)= (△-1)A-1) e 义 (△-2)A △- 2 Uniqueness threshold
Uniqueness Threshold regular tree ` ! 1 v σ: boundary condition fixing each leaf ∈I or ∉I Pr[v 2 I | ] Critical phenomenon: random independent set I iff Δ- c() = ( 1)(1) ( 2) ⇡ e 2 Pr[v∈I | σ] is independent of σ when l→∞ Uniqueness threshold
Phase Transition (4)=(A-1)a-) 入 6 (△-2)A 5 non-uniqueness regime 3 uniqueness regime 2 4 10 △
Phase Transition 2 4 6 8 10 1 2 3 4 5 6 Δ λ non-uniqueness regime uniqueness regime c() = ( 1)(1) ( 2)
Phase Transition (A)=(4-1)a- 入 (△-2)A non-uniqueness regime uniqueness regime 2 4 6 8 10 △ sampling(with bounded error)from the hardcore model on graphs of max-degree A and fugacity A0
Phase Transition 2 4 6 8 10 1 2 3 4 5 6 Δ λ non-uniqueness regime uniqueness regime c() = ( 1)(1) ( 2) sampling (with bounded error) from the hardcore model on graphs of max-degree Δ and fugacity λ>0
Glauber Dynamics [Glauber'63] Markov chain {Xi}=0.1.2....over independent sets in G(V,E) transition Xi→Xi+l: pick a uniform random vertex v; if ueX,for all v's neighbors u: Xt+1= X:Uf with prob. with prob. else X++1=Xi;
Glauber Dynamics pick a uniform random vertex v; if u∉Xt for all v’s neighbors u: else Xt+1 = Xt; Xt+1 = ( Xt [ {v} with prob. 1+ Xt \ {v} with prob. 1 1+ Markov chain {Xt}t=0,1,2,… over independent sets in G(V,E) transition Xt → Xt+1 : [Glauber’63]