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

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

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>