Abstract
In this paper we generalize to the case of diluted spin models and random combinatorial optimization problems a technique recently introduced by Guerra (cond-mat/0205123) to prove that the replica method generates variational bounds for disordered systems. We analyze a family of models that includes the Viana–Bray model, the diluted p-spin model or random XOR-SAT problem, and the random K-SAT problem, showing that the replica/cavity method, at the various levels of approximation, provides systematic schemes to obtain lower bounds of the free-energy at all temperatures and of the ground state energy. In the case of K-SAT and XOR-SAT it thus gives upper bounds of the satisfiability threshold. Our analysis underlines deep connections with the cavity method which are not evident in the long range case.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
S. F. Edwards and P. W. Anderson, J. Phys. F: Metal Phys. 5:965-974 (1975).
M. Mezard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond (World Scientific, 1987).
O. C. Martin, R. Monasson, and R. Zecchina, Theoret. Comput. Sci. 265:3(2001).
H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction (Oxford, 2001).
For a review on the work of mathematicians on spin glass systems see: A. Bovier and P. Picco (eds.) Mathematical Aspects of Spin Glasses and Neural Networks, Progress in Probability, Vol. 41 (Birkhauser, Boston, 1997). M. Talagrand, Proceedings of the Berlin international Congress of Mathematicians. Doc. Math., Extra Volume I, (1998) 1 and references therein. We refer to the web page of M. Talagrand for the comprehensive list of references on his work: http://www.math.ohio-state.edu/ talagran/
M. Talagrand, Probab. Theory and Relat. Fields 117:303(2000), and M. TalagrandOn the p-Spin Interaction Model at Low Temperature (C. R. A. S., to appear).
A. Bovier and I. Kurkova, Rigorous Results on Some Simple Spin Glass Models, cond-mat/0206562 and references therein.
F. Guerra and F. L. Toninelli, Commun. Math. Phys. 230:1, 71 (2002).
F. Guerra, Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model, cond-mat/0205123.
M. Mezard and G. Parisi, Eur. Phys. J. B 20:217(2001).
J. S. Yedidia, W. T. Freeman, and Y. Weiss, Understanding Belief Propagation and its Generalizations, 2001. MERL technical report TR 2001-22, available at http://www.merl.com/papers/TR2001-22; J. S. Yedidia, W. T. Freeman, and Y. Weiss, in Advances in Neural Information Processing Systems 13, T. K. Leen, T. G. Dietterich, and V. Tresp, eds. (MIT Press, Cambridge, MA, 2001).
M. Mezard, G. Parisi, and R. Zecchina, Science 297:812-815 (2002); M. Mezard and R. Zecchina, cond-mat/0207194; to appear in Phys. Rev. E.
S. Franz, M. Leone, F. R. Tersenghi, and R. Zecchina, Phys. Rev. Lett. 87:127209(2001).
R. Monasson and R. Zecchina, Phys. Rev. E 56:1357(1997).
F. Ricci-Tersenghi, M. Weigt, and R. Zecchina, Phys. Rev. E 63:026702 (2001).
C. Creignou and H. Daude, Discr. Appl. Math. 96-97:41(1999).
C. Berge, Graphs and Hyper-graphs (North-Holland, 1973).
M. Talagrand, Probab. Theory and Relat. Fields 119:187(2001).
K. Nakanishi, Phys. Rev. B 23:3514(1981).
J. Pearl, Probabilistic Reasoning in Intelligent Systems: Network of Plausible Inference (Morgan Kaufmann, San Francisco, 1988).
R. G. Gallager, Low Density Parity-Check Codes (MIT Press, Cambridge, MA, 1963).
M. Mezard and G. Parisi, The Cavity Method at Zero Temperature, cond-mat/0207121.
C. Dedominicis and P. Mottishaw, J. Phys. A: Math. Gen. 20:L1267(1987); R. Monasson, J. Phys. A: Math. Gen. 31:513 (1998).
M. Leone, Ph.D. thesis, available in ps format at the URL: http://www.sissa.it/sbp/
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Franz, S., Leone, M. Replica Bounds for Optimization Problems and Diluted Spin Systems. Journal of Statistical Physics 111, 535–564 (2003). https://doi.org/10.1023/A:1022885828956
Issue Date:
DOI: https://doi.org/10.1023/A:1022885828956