Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RAPID MIXING:
Reports tagged with Rapid mixing:
TR00-079 | 12th September 2000
Mark Jerrum, Eric Vigoda

#### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

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

more >>>

TR04-009 | 22nd January 2004
Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

#### Randomly coloring constant degree graphs

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

TR05-002 | 6th January 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

#### Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

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

TR05-075 | 4th July 2005
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

#### Dobrushin conditions and Systematic Scan

Revisions: 1

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

TR05-151 | 7th December 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

#### Metric Construction, Stopping Times and Path Coupling.

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

ISSN 1433-8092 | Imprint