Exact solutions for diluted spin glasses and optimization problems
<|reference_start|>Exact solutions for diluted spin glasses and optimization problems: 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=3, \gamma_d=0.818 and \gamma_s=0.918 resp.), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds (\gamma_c^{var}=4.396 and \gamma_c^{var}=2.149 resp.).<|reference_end|>
@article{franz2001exact,
    title={Exact solutions for diluted spin glasses and optimization problems},
    author={S. Franz, M. Leone, F. Ricci-Tersenghi and R. Zecchina},
    journal={Phys. Rev. Lett. 87 (2001) 127209},
    year={2001},
    doi={10.1103/PhysRevLett.87.127209},
    archivePrefix={arXiv},
    eprint={cond-mat/0103328},
    primaryClass={cond-mat.dis-nn cond-mat.stat-mech cs.CC}
}