Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Martin Dyer:

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

TR05-121 | 17th October 2005
Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

On counting homomorphisms to directed acyclic graphs

We give a dichotomy theorem for the problem of counting homomorphisms to
directed acyclic graphs. $H$ is a fixed directed acyclic graph.
The problem is, given an input digraph $G$, how many homomorphisms are there
from $G$ to $H$. We give a graph-theoretic classification, showing that
for some digraphs $H$, ... 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-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 >>>

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

ISSN 1433-8092 | Imprint