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

We characterize the uniqueness condition in the hardcore model for bipartitegraphs with degree bounds only on one side, and provide a nearly linear timesampling algorithm that works up to the uniqueness threshold. We show that theuniqueness threshold for bipartite graph has almost the same form of the treeuniqueness threshold for general graphs, except with degree bounds only on oneside of the bipartition. The hardcore model from statistical physics can beseen as a weighted enumeration of independent sets. Its bipartite version(#BIS) is a central open problem in approximate counting. Compared to the sameproblem in a general graph, surprising tractable regime have been identifiedthat are believed to be hard in general. This is made possible by two lines ofalgorithmic approach: the high-temperature algorithms starting from Liu and Lu(STOC 2015), and the low-temperature algorithms starting from Helmuth, Perkins,and Regts (STOC 2019).  In this work, we study the limit of these algorithms in the high-temperaturecase. Our characterization of the uniqueness condition is obtained by provingdecay of correlations for arguably the best possible regime, which involveslocating fixpoints of multivariate iterative rational maps and showing theircontraction. We also give a nearly linear time sampling algorithm based onsimulating field dynamics only on one side of the bipartite graph that works upto the uniqueness threshold. Our algorithm is very different from the originalhigh-temperature algorithm of Liu and Lu, and it makes use of a connectionbetween correlation decay and spectral independence of Markov chains. Last butnot the least, we are able to show that the standard Glauber dynamics on bothside of the bipartite graph mixes in polynomial time up to the uniqueness.

Uniqueness and Rapid Mixing in the Bipartite Hardcore Model