## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 25, 2018, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Manuela Fischer

## Local Glauber Dynamics

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].

Information for students and suggested topics for student talks