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

For several models of random constraint satisfaction problems, it wasconjectured by physicists and later proved that a sharp satisfiabilitytransition occurs. For random $k$-SAT and related models it happens at clausedensity $\alpha$ around $2^k$. Just below the threshold, further resultssuggest that the solution space has a "1RSB" structure of a large boundednumber of near-orthogonal clusters inside the space of variable assignments$\{0,1\}^N$. In the unsatisfiable regime, it is natural to considermax-satisfiability: violating the least number of constraints. For a simplifiedvariant, the strong refutation problem, there is strong evidence that analgorithmic transition occurs around $\alpha = N^{k/2-1}$. For $\alpha$ boundedin $N$, a very precise estimate of the max-sat value was obtained byAchlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate thenature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) showsthat for $\alpha$ very large (roughly, above $64^k$) the max-sat valueapproaches the mean-field (complete graph) limit: this is conjectured to havean "FRSB" structure where near-optimal configurations form clusters withinclusters, in an ultrametric hierarchy of infinite depth inside $\{0,1\}^N$. Astronger form of FRSB was shown in several recent works to have algorithmicimplications (again, in complete graphs). Consequently we find it of interestto understand how the model transitions from 1RSB near the satisfiabilitythreshold, to (conjecturally) FRSB for large $\alpha$. In this paper we showthat in the random regular $k$-NAE-SAT model, the 1RSB description breaks downalready above $\alpha \asymp 4^k/k^3$. This is proved by an explicitperturbation in the 2RSB parameter space, inspired by the "bug proliferation"mechanism proposed by physicists (Montanari and Ricci-Tersenghi, 2003;Krzakala, Pagnani, and Weigt, 2004).

Breaking of 1RSB in random MAX-NAE-SAT