English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic toolfor sampling from high-dimensional distributions, a notable example is theequilibirum distribution of graphical models. The Glauber dynamics, also knownas the Gibbs sampler, is the simplest example of an MCMC algorithm; thetransitions of the chain update the configuration at a randomly chosencoordinate at each step. Several works have studied distributed versions of theGlauber dynamics and we extend these efforts to a more general family of Markovchains. An important combinatorial problem in the study of MCMC algorithms israndom colorings. Given a graph $G$ of maximum degree $\Delta$ and an integer$k\geq\Delta+1$, the goal is to generate a random proper vertex $k$-coloring of$G$.  Jerrum (1995) proved that the Glauber dynamics has $O(n\log{n})$ mixing timewhen $k>2\Delta$. Fischer and Ghaffari (2018), and independently Feng, Hayes,and Yin (2018), presented a parallel and distributed version of the Glauberdynamics which converges in $O(\log{n})$ rounds for $k>(2+\varepsilon)\Delta$for any $\varepsilon>0$. We improve this result to $k>(11/6-\delta)\Delta$ fora fixed $\delta>0$. This matches the state of the art for randomly samplingcolorings of general graphs in the sequential setting. Whereas previous worksfocused on distributed variants of the Glauber dynamics, our work presents aparallel and distributed version of the more general flip dynamics presented byVigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle(2019)), which recolors local maximal two-colored components in each step.

Improved Distributed Algorithms for Random Colorings