Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Mark Jerrum:

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

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

ISSN 1433-8092 | Imprint