One-step replica symmetry breaking of random regular NAE-SAT

Danny Nam, Allan Sly, Youngtak Sohn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In a broad class of sparse random constraint satisfaction problems (CSP), deep heuristics from statistical physics predict that there is a condensation phase transition before the satisfiability threshold, governed by one-step replica symmetry breaking (1RSB). In fact, in random regular k-NAE-SAT, which is one of such random CSPS, it was verified [1] that its free energy is well-defined and the explicit value follows the 1RSB prediction. However, for any model of sparse random CSP, it has been unknown whether the solution space indeed condensates on O(1) clusters according to the 1RSB prediction. In this paper, we give an affirmative answer to this question for the random regular k-NAE-SAT model. Namely, we prove that with probability close to one, most of the solutions lie inside a bounded number of solution clusters whose sizes are comparable to the scale of the free energy. Furthermore, we establish that the overlap between two independently drawn solutions concentrates precisely at two values. This is the defining property of the one-step replica symmetry breaking class which we establish for the first time in a sparse random CSP, Our proof is based on a detailed moment analysis of a spin system, which has an infinite spin space that encodes the structure of solution clusters. We develop new techniques to study the partition function as well as enhance previous approaches which were only applicable to spin systems with finitely many spins. We believe that our method is applicable to a broad range of random CSPS in the 1RSB universality class.

Original languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages310-318
Number of pages9
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February
ISSN (Print)0272-5428

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period2/7/222/10/22

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • condensation phase transition
  • one-step replica symmetry breaking
  • random constraint satisfaction problems
  • random regular NAE-SAT model

Fingerprint

Dive into the research topics of 'One-step replica symmetry breaking of random regular NAE-SAT'. Together they form a unique fingerprint.

Cite this