English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Is Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for aproblem via an MCMC algorithm possible when it is known that rapid mixingprovably fails? We introduce several weight-preserving maps for theeight-vertex model on planar and on bipartite graphs, respectively. Some areone-to-one, while others are holographic which map superpositions ofexponentially many states from one setting to another, in a quantum-likemany-to-many fashion. In fact we introduce a set of such mappings that forms agroup in each case. Using some holographic maps and their compositions weobtain FPRAS for the eight-vertex model at parameter settings where it is knownthat rapid mixing provably fails due to an intrinsic barrier. This FPRAS isindeed the same MCMC algorithm, except its state space corresponds tosuperpositions of the given states, where rapid mixing holds. FPRAS is alsogiven for torus graphs for parameter settings where natural Markov chains areknown to mix torpidly. Our results show that the eight-vertex model is thefirst problem with the provable property that while NP-hard to approximate ongeneral graphs (even #P-hard for planar graphs in exact complexity), itpossesses FPRAS on both bipartite graphs and planar graphs in substantialregions of its parameter space.

FPRAS via MCMC where it mixes torpidly (and very little effort)