Mark Jerrum, Eric Vigoda

We present a fully-polynomial randomized approximation scheme

for computing the permanent of an arbitrary matrix

with non-negative entries.

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

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 Δ. 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> ≥ <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

We give a new method for analysing the mixing time of a Markov chain using

path coupling with stopping times. We apply this approach to two hypergraph

problems. We show that the Glauber dynamics for independent sets in a

hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ...
more >>>

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

We consider Glauber dynamics on finite spin systems.

The mixing time of Glauber dynamics can be bounded

in terms of the influences of sites on each other.

We consider three parameters bounding these influences ---

$\alpha$, the total influence on a site, as studied by Dobrushin;

$\alpha'$, the total influence ...
more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

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