FPRAS via MCMC where it mixes torpidly (and very little effort)
share
Is Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for a problem via an MCMC algorithm possible when it is known that rapid mixing provably fails? We introduce several weight-preserving maps for the eight-vertex model on planar and on bipartite graphs, respectively. Some are one-to-one, while others are holographic which map superpositions of exponentially many states from one setting to another, in a quantum-like many-to-many fashion. In fact we introduce a set of such mappings that forms a group in each case. Using some holographic maps and their compositions we obtain FPRAS for the eight-vertex model at parameter settings where it is known that rapid mixing provably fails due to an intrinsic barrier. This FPRAS is indeed the same MCMC algorithm, except its state space corresponds to superpositions of the given states, where rapid mixing holds. FPRAS is also given for torus graphs for parameter settings where natural Markov chains are known to mix torpidly. Our results show that the eight-vertex model is the first problem with the provable property that while NP-hard to approximate on general graphs (even #P-hard for planar graphs in exact complexity), it possesses FPRAS on both bipartite graphs and planar graphs in substantial regions of its parameter space.
READ FULL TEXT