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 introduce efficient algorithms for approximate sampling from symmetricGibbs distributions on the sparse random (hyper)graph. The examples we considerinclude (but are not restricted to) important distributions on spin systems andspin-glasses such as the q state antiferromagnetic Potts model for $q\geq 2$,including the colourings, the uniform distributions over the Not-All-Equalsolutions of random k-CNF formulas. Finally, we present an algorithm forsampling from the spin-glass distribution called the k-spin model. To ourknowledge this is the first, rigorously analysed, efficient algorithm forspin-glasses which operates in a non trivial range of the parameters.  Our approach builds on the one that was introduced in [Efthymiou: SODA 2012].For a symmetric Gibbs distribution $\mu$ on a random (hyper)graph whoseparameters are within an certain range, our algorithm has the followingproperties: with probability $1-o(1)$ over the input instances, it generates aconfiguration which is distributed within total variation distance$n^{-\Omega(1)}$ from $\mu$. The time complexity is $O((n\log n)^2)$.  The algorithm requires a range of the parameters which, for the graph case,coincide with the tree-uniqueness region, parametrised w.r.t. the expecteddegree d. For the hypergraph case, where uniqueness is less restrictive, we gobeyond uniqueness. Our approach utilises in a novel way the notion ofcontiguity between Gibbs distributions and the so-called teacher-student model.

On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs