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 Δ-