What can be sampled locally? Yitong Yin Nanjing University Joint work with:Weiming Feng(Nanjing University) Yuxin Sun (Nanjing University)
What can be sampled locally? Yitong Yin Nanjing University Joint work with: Weiming Feng (Nanjing University) Yuxin Sun (Nanjing University)
Local Computation the LOCAC model [Linial '87]: In t rounds:each node can collect information up to distance t. Locally Checkable Labeling (LCL)problems [Noar,Stockmeyer 293]: CSPs with local constraints. Construct a feasible solution: vertex/edge coloring,Lovasz local lemma Find local optimum:MIS,MM Approximate global optimum: maximum matching,minimum vertex cover,minimum dominating set network G(E) Q:"What locally definable problems are locally computable?" by local constraints in O(1)rounds or in small number of rounds
Local Computation • CSPs with local constraints. • Construct a feasible solution: vertex/edge coloring, Lovász local lemma • Find local optimum: MIS, MM • Approximate global optimum: maximum matching, minimum vertex cover, minimum dominating set Locally Checkable Labeling (LCL) problems [Noar, Stockmeyer ’93] : Q: “What locally definable problems are locally computable?” the LOCAL model [Linial ’87]: network G(V,E) • In t rounds: each node can collect information up to distance t. by local constraints in O(1) rounds or in small number of rounds
"What can be sampled locally?" CSP with local constraints on the network: ·proper q-coloring; ●independent set; ● Sample a uniform random feasible solution: distributed algorithms (in the LOCAC model) network G(,E) Q:"What locally definable joint distributions are locally sample-able?
“What can be sampled locally?” network G(V,E) • CSP with local constraints on the network: • proper q-coloring; • independent set; • Sample a uniform random feasible solution: • distributed algorithms (in the LOCAL model) Q: “What locally definable joint distributions are locally sample-able?
Markoy Random Fields (MRF) Each vertex corresponds to a network G(E): variable with finite domain [g]. ● Each edge e=(u,v)EE imposes a weighted binary constraint: X∈[q] ⑨bw Ae:[gl2→R≥0 ●Each vertex v∈E imposes a weighted unary constraint: b:[gl→R>o Gibbs distribution u:Voe[g] x∈[g]y follows u L(o)Ae(ou;0)bo(o) e=(u,w)∈E w∈V
Markov Random Fields network G(V,E): • Each vertex corresponds to a variable with finite domain [q]. • Each edge e=(u,v)∈E imposes a weighted binary constraint: • Each vertex v∈E imposes a weighted unary constraint: • Gibbs distribution µ : ∀σ∈[q]V Ae : [q] 2 ! R0 bv : [q] ! R0 µ() / Y e=(u,v)2E Ae(u, v) Y v2V bv(v) Ae bv Xv∈[q] u v (MRF) X ~ 2 [q] V follows µ
Markoy Random Fields (MRF) Gibbs distribution u:voelg] network G(E): L()II Ac(ou,o)IIbu(o) e=(u,v)∈E o proper q-coloring: X∈[q] ⊙bv 1 independent set: a-b周&-日 ∈[g]y follows u local conflict colorings [Fraigniaud,Heinrich,Kosowski'16] Ae∈{0,1}9x9,b,∈{0,1}9 Hammersley-Clifford theorem (Fundamental Thm of random fields): MRFs are universal for conditional independent positive distributions
Markov Random Fields network G(V,E): Ae bv Xv∈[q] u v X ~ 2 [q] V follows µ (MRF) • Gibbs distribution µ : ∀σ∈[q]V µ() / Y e=(u,v)2E Ae(u, v) Y v2V bv(v) • proper q-coloring: Ae = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 bv = 2 6 4 1 . . . 1 3 7 5 • independent set: bv = 1 1 Ae = 1 1 1 0 Hammersley–Clifford theorem (Fundamental Thm of random fields): MRFs are universal for conditional independent positive distributions. • local conflict colorings : [Fraigniaud, Heinrich, Kosowski’16] Ae 2 {0, 1}q⇥q, bv 2 {0, 1}q