ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > MARKOV CHAINS:
Reports tagged with Markov Chains:
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-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results

We highlight a common theme in four relatively recent works that establish remarkable results by an iterative approach. Starting from a trivial construct, each of these works applies an ingeniously designed sequence of iterations that yields the desired result, which is highly non-trivial. Furthermore, in each iteration, the construct is ... more >>>



ISSN 1433-8092 | Imprint