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

Approximate counting via correlation decay is the core algorithmic techniqueused in the sharp delineation of the computational phase transition that arisesin the approximation of the partition function of anti-ferromagnetic two-spinmodels.  Previous analyses of correlation-decay algorithms implicitly depended on theoccurrence of strong spatial mixing (SSM). This means that one uses worst-caseanalysis of the recursive procedure that creates the sub-instances. We developa new analysis method that is more refined than the worst-case analysis. Wetake the shape of instances in the computation tree into consideration andamortise against certain "bad" instances that are created as the recursionproceeds. This enables us to show correlation decay and to obtain an FPTAS evenwhen SSM fails.  We apply our technique to the problem of approximately counting independentsets in hypergraphs with degree upper-bound Delta and with a lower bound k onthe arity of hyperedges. Liu and Lin gave an FPTAS for k>=2 and Delta<=5 (lackof SSM was the obstacle preventing this algorithm from being generalised toDelta=6). Our technique gives a tight result for Delta=6, showing that there isan FPTAS for k>=3 and Delta<=6. The best previously-known approximation schemefor Delta=6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer andKarpinski, which only works for k>=8.  Our technique also applies for larger values of k, giving an FPTAS fork>=Delta. This bound is not substantially stronger than existing randomisedresults in the literature. Nevertheless, it gives the first deterministicapproximation scheme in this regime. Moreover, unlike existing results, itleads to an FPTAS for counting dominating sets in regular graphs withsufficiently large degree.  We further demonstrate that approximately counting independent sets inhypergraphs is NP-hard even within the uniqueness regime.

Approximation via Correlation Decay when Strong Spatial Mixing Fails