A counterexample to rapid mixing of the Ge-Stefankovic process
From MaRDI portal
Publication:428729
DOI10.1214/ECP.V17-1712zbMath1246.60094arXiv1109.5242MaRDI QIDQ428729
Leslie Ann Goldberg, Mark R. Jerrum
Publication date: 22 June 2012
Published in: Electronic Communications in Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1109.5242
Graph polynomials (05C31) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard ⋮ The complexity of approximately counting stable matchings ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
This page was built for publication: A counterexample to rapid mixing of the Ge-Stefankovic process
