Crossing the Chromatic Barrier Glauber LubyGlauber O(n log n)）→O(△logn) parallel speedup =0(n/△) △=max-degree X=chromatic no. Do not update adjacent vertices simultaneously. It takes=xsteps to update all vertices at least once. Q:"How to update all variables simultaneously and still converge to the correct distribution?Crossing the Chromatic # Barrier Glauber LubyGlauber O(n log n) O(Δ log n) ∆ = max-degree parallel speedup = θ(n /Δ) Q: “How to update all variables simultaneously and still converge to the correct distribution?” χ = chromatic no. Do not update adjacent vertices simultaneously. It takes ≥χ steps to update all vertices at least once