Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 25, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Manuela Fischer
We propose a simple Markov chain with local update rules that leads to efficient parallel and distributed sampling algorithms. In particular, our method can sample a uniform proper coloring of an n-node graph with alpha Delta colors in O(log n) rounds, where alpha > 2 is an arbitrary constant and Delta denotes the maximum degree of the graph. This thus almost fully parallelizes the (single-site) Glauber dynamics that mixes in O(n log n) steps if the number of colors is 2 Delta + 1. Moreover, it improves over the LubyGlauber algorithm by Feng, Sun, and Yin [PODC'17], which needs O(Delta log n) rounds, and their LocalMetropolis algorithm, which converges in O(log n) rounds but requires alpha > 2 + sqrt(2). We present a simple proof based on the Path Coupling Lemma by Bubley and Dyer [FOCS'97].
Automatic MiSe System Software Version 1.4803M | admin login