How to cite item

A counterexample to rapid mixing of the Ge-Stefankovic process

   
@article{ECP1712,
	author = {Leslie Goldberg and Mark Jerrum},
	title = {A counterexample to rapid mixing of the Ge-Stefankovic process},
	journal = {Electron. Commun. Probab.},
	fjournal = {Electronic Communications in Probability},
	volume = {17},
	year = {2012},
	keywords = {Glauber dynamics; Independent sets in graphs; Markov chains; Mixing time; Randomised algorithms},
	abstract = {
Ge and Stefankovic have recently introduced a Markov chain which, if rapidly mixing, would provide an efficientprocedure for sampling independent sets in a bipartite graph. Such a procedure would be a breakthrough because it would give an efficient randomised algorithm for approximately counting independent sets in a bipartite graph, which would in turn imply the existence of efficient approximation algorithms for a number of significant counting problems whose computational complexity is so far unresolved. Their Markov chain is based on a novel two-variable graph polynomial which, when specialised to a bipartite graph, and evaluated at the point (1/2,1), givesthe number of independent sets in the graph. The Markov chain  is promising, in the sense that it overcomes the most obvious barrier to rapid mixing.  However, we show here, by exhibiting a sequence of counterexamples, that its mixing timeis  exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.
},
	pages = {no. 5, 1-6},
	issn = {1083-589X},
	doi = {10.1214/ECP.v17-1712},    
        url = {http://ecp.ejpecp.org/article/view/1712}}