Stopping times, metrics and approximate counting
(2006)
Conference Proceeding
Bordewich, M., Dyer, M., & Karpinski, M. (2006). Stopping times, metrics and approximate counting. In M. Bugliesi, B. Preneel, V. Sassone, & I. Wegener (Eds.), Automata, languages and programming : 33rd International Colloquium, ICALP 2006, 10-14 July 2006, Venice, Italy ; proceedings, part I (108-119). https://doi.org/10.1007/11786986_11
In this paper we examine the importance of the choice of metric in path coupling, and its relationship to stopping time analysis. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we p... Read More about Stopping times, metrics and approximate counting.