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

The local behavior of typical solutions of random constraint satisfactionproblems (CSP) describes many important phenomena including clusteringthresholds, decay of correlations, and the behavior of message passingalgorithms. When the constraint density is low, studying the planted model is apowerful technique for determining this local behavior which in many exampleshas a simple Markovian structure. Work of Coja-Oghlan, Kapetanopoulos,M\"{u}ller (2020) showed that for a wide class of models, this descriptionapplies up to the so-called condensation threshold.  Understanding the local behavior after the condensation threshold is morecomplex due to long-range correlations. In this work, we revisit the randomregular NAE-SAT model in the condensation regime and determine the local weaklimit which describes a random solution around a typical variable. This limitexhibits a complicated non-Markovian structure arising from the space ofsolutions being dominated by a small number of large clusters. This is thefirst description of the local weak limit in the condensation regime for anysparse random CSPs in the one-step replica symmetry breaking (1RSB) class. Ourresult is non-asymptotic, and characterizes the tight fluctuation $O(n^{-1/2})$around the limit. Our proof is based on coupling the local neighborhoods of aninfinite spin system, which encodes the structure of the clusters, to abroadcast model on trees whose channel is given by the 1RSB belief-propagationfixed point. We believe that our proof technique has broad applicability torandom CSPs in the 1RSB class.

Local geometry of NAE-SAT solutions in the condensation regime