(log n)Lower Bound for Sampling Theorem (Feng,Sun,Y.'17): For any non-degenerate MRF,any distributed algorithm that samples from its distribution u within bounded total variation distance requires (log n)rounds of communications. outputs of t-round algorithm:mutually independent X.,'s path: Gibbs distribution u:exponential correlation between Xy's ou≠Tu:lg-“lTv≥exp(-O(t)>n-1/4 for a t=O(log n) drv(X,X)>是 for any product distributionXTheorem (Feng, Sun, Y. ’17): For any non-degenerate MRF, any distributed algorithm that samples from its distribution µ within bounded total variation distance requires Ω(log n) rounds of communications. outputs of t-round algorithm: mutually independent Xev Gibbs distribution µ: exponential correlation between Xv path: t >2t u v ’s ’s kµ￾u v ￾ µ⌧u ￾u 6= ⌧u : v kTV ￾ exp(￾O(t)) > n￾1/4 for a t = O(log n) dTV(X, X f ) > 1 2e for any product distribution X f Ω(log n) Lower Bound for Sampling