2001/03/31 by Silvio Franz, S. Franz, Michele Leone +5 · 2 citations
Computer Science · Physics and Astronomy · #Quantum many-body systems #Theoretical and Computational Physics #Topological and Geometric Data Analysis #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.1103/physrevlett.87.127209
published as Phys. Rev. Lett. 87 (2001) 127209 · 4 pages, 1 figure, accepted for publication in PRL
arxiv created 2001/08/15 · openalex publication_date 2001/08/31 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p\phantom\rule0ex0ex=\phantom\rule0ex0ex3, \ensuremathγd\phantom\rule0ex0ex=\phantom\rule0ex0ex0.818, and \ensuremathγs\phantom\rule0ex0ex=\phantom\rule0ex0ex0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds ( \ensuremathγcvar\phantom\rule0ex0ex=\phantom\rule0ex0ex4.396 and \ensuremathγcvar\phantom\rule0ex0ex=\phantom\rule0ex0ex2.149).