Fundamentals of Computation Theory

DOI10.1007/11537311MaRDI QIDQ5492913zbMATHOpenAlexFDO

Authors Magnus Bordewich, Martin Dyer, Marek Karpinski

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511202

zbMATH Keywords

Markov chainsstopping timeshypergraphmixing timeGlauber dynamicspath couplinghardness of counting

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Hypergraphs (05C65)

Abstract: 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 with stopping times, using a metric which allows us to restrict analysis to standard one-step path coupling. This approach provides insight for the design of non-standard metrics giving improvements in the analysis of specific problems. We give illustrative applications to hypergraph independent sets and SAT instances, hypergraph colourings and colourings of bipartite graphs.

Recommendations

• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Stopping Times, Metrics and Approximate Counting
• Rapid mixing of hypergraph independent sets
• Variable length path coupling
• Coupling with the stationary distribution and improved sampling for colorings and independent sets

Cited in

(3)

• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Path coupling without contraction
• Rapid mixing of hypergraph independent sets

This page was built for publication: Fundamentals of Computation Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5492913)