What can be sampled locally? Yitong Yin Nanjing University Joint work with:Weiming Feng,Yuxin Sun
What can be sampled loca!y? Yitong Yin Nanjing University Joint work with: Weiming Feng, Yuxin Sun
Local Computation "What can be computed locally?" [Noar,Stockmeyer,STOC'93,SICOMP'95] the LOCAC model [Linial '87]: ● Communications are synchronized. In each round:each node can send messages of unbounded sizes to all its neighbors. Local computations are free. 0 Complexity:of rounds to terminate in the worst case. In t rounds:each node can collect information up to distance t
Local Computation • Communications are synchronized. • In each round: each node can send messages of unbounded sizes to all its neighbors. • Local computations are free. • Complexity: # of rounds to terminate in the worst case. • In t rounds: each node can collect information up to distance t. the LOCAL model [Linial ’87]: “What can be computed locally?” [Noar, Stockmeyer, STOC’93, SICOMP’95]
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 network G(E): on the network: ●proper q-coloring; ●independent set; ● Sample a uniform random feasible solution: distributed algorithms (in the LOCAC model) 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] ⑨bv Ae:[gl2→R≥0 。Each vertex ve∈imposes a weighted unary constraint: b:[gl→R≥o Gibbs distribution u:∀o∈[g]' X∈[a]V follows u L(o)Ae(ou,0)b() e=(u,v)∈E u∈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 µ