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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the computational complexity of estimating local observables forGibbs distributions. A simple combinatorial example is the average size of anindependent set in a graph. In a recent work, we established NP-hardness ofapproximating the average size of an independent set utilizing hardness of thecorresponding optimization problem and the related phase transition behavior.Here, we instead consider settings where the underlying optimization problem iseasily solvable. Our main contribution is to classify the complexity ofapproximating a wide class of observables via a generic reduction fromapproximate counting to the problem of estimating local observables. The keyidea is to use the observables to interpolate the counting problem.  Using this new approach, we are able to study observables on bipartite graphswhere the underlying optimization problem is easy but the counting problem isbelieved to be hard. The most-well studied class of graphs that was excludedfrom previous hardness results were bipartite graphs. We establish hardness forestimating the average size of the independent set in bipartite graphs ofmaximum degree 6; more generally, we show tight hardness results for generalvertex-edge observables for antiferromagnetic 2-spin systems on bipartitegraphs. Our techniques go beyond 2-spin systems, and for the ferromagneticPotts model we establish hardness of approximating the number of monochromaticedges in the same region as known hardness of approximate counting results.

Approximating observables is as hard as counting