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

We examine the problem of almost-uniform sampling proper $q$-colorings of agraph whose maximum degree is $\Delta$. A famous result, discoveredindependently by Jerrum(1995) and Salas and Sokal(1997), is that, assuming $q >(2+\delta) \Delta$, the Glauber dynamics (a.k.a. single-site dynamics) for thisproblem has mixing time $O(n \log n)$, where $n$ is the number of vertices, andthus provides a nearly linear time sampling algorithm for this problem. Anatural question is the extent to which this algorithm can be parallelized.Previous work Feng, Sun and Yin [PODC'17] has shown that a $O(\Delta \log n)$time parallelized algorithm is possible, and that $\Omega(\log n)$ time isnecessary.  We give a distributed sampling algorithm, which we call the Lazy LocalMetropolis Algorithm, that achieves an optimal parallelization of this classicalgorithm. It improves its predecessor, the Local Metropolis algorithm of Feng,Sun and Yin [PODC'17], by introducing a step of distributed symmetry breakingthat helps the mixing of the distributed sampling algorithm.  For sampling almost-uniform proper $q$-colorings of graphs $G$ on $n$vertices, we show that the Lazy Local Metropolis algorithm achieves an optimal$O(\log n)$ mixing time if either of the following conditions is true for anarbitrary constant $\delta>0$:  $\bullet$ $q\ge(2+\delta)\Delta$, on general graphs with maximum degree$\Delta$;  $\bullet$ $q \geq (\alpha^* + \delta)\Delta$, where $\alpha^* \approx 1.763$satisfies $\alpha^* = \mathrm{e}^{1/\alpha^*}$, on graphs with sufficientlylarge maximum degree $\Delta\ge \Delta_0(\delta)$ and girth at least $9$.

Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors)