REVIEW 1 cited by
Instability of one-step replica-symmetry-broken phase in satisfiability problems
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We reconsider the one-step replica-symmetry-breaking (1RSB) solutions of two random combinatorial problems: k-XORSAT and k-SAT. We present a general method for establishing the stability of these solutions with respect to further steps of replica-symmetry breaking. Our approach extends the ideas of [A.Montanari and F. Ricci-Tersenghi, Eur.Phys.J. B 33, 339 (2003)] to more general combinatorial problems. It turns out that 1RSB is always unstable at sufficiently small clauses density alpha or high energy. In particular, the recent 1RSB solution to 3-SAT is unstable at zero energy for alpha< alpha_m, with alpha_m\approx 4.153. On the other hand, the SAT-UNSAT phase transition seems to be correctly described within 1RSB.
Forward citations
Cited by 1 Pith paper
-
Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks
NeuroSAT's internal embeddings encode classic SAT heuristic concepts, chiefly support, in the top principal components.
Discussion (0). Continue with ORCID to comment.