We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i>₀ for some absolute constant <i>k</i>₀, and either: ... more >>>

We present a fully-polynomial randomized approximation scheme
for computing the permanent of an arbitrary matrix
with non-negative entries.

more >>>