(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. The (log n)lower bound holds for all MRFs with exponential correlation: non-trivial spin systems with O(1)spin states. O(log n)is the new criteria of"being local" for distributed sampling algorithms.Theorem (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. Ω(log n) Lower Bound for Sampling • The Ω(log n) lower bound holds for all MRFs with exponential correlation: • non-trivial spin systems with O(1) spin states. • O(log n) is the new criteria of “being local” for distributed sampling algorithms