Two Solutions to Diluted p-Spin Models and XORSAT Problems

M. Mézard; F. Ricci-Tersenghi; R. Zecchina

doi:10.1023/A:1022886412117

Journal of Statistical Physics

May 2003, Volume 111, Issue 3, pp 505–533

Two Solutions to Diluted p-Spin Models and XORSAT Problems

Authors
Authors and affiliations

M. Mézard
F. Ricci-Tersenghi
R. Zecchina

M. Mézard
- 1
F. Ricci-Tersenghi
- 2
R. Zecchina
- 3

1.Laboratoire de Physique Théorique et Modèles StatistiquesUniversité Paris SudOrsayFrance
2.Dipartimento di Fisica and INFMUniversità di Roma “La Sapienza,”Roma (Italy)
3.International Center for Theoretical PhysicsTriesteItaly

Article

DOI: 10.1023/A:1022886412117

Cite this article as:: Mézard, M., Ricci-Tersenghi, F. & Zecchina, R. Journal of Statistical Physics (2003) 111: 505. doi:10.1023/A:1022886412117

Abstract

We derive analytical solutions for p-spin models with finite connectivity at zero temperature. These models are the statistical mechanics equivalent of p-XORSAT problems in theoretical computer science. We give a full characterization of the phase diagram: location of the phase transitions (static and dynamic), together with a description of the clustering phenomenon taking place in configurational space. We use two alternative methods: the cavity approach and a rigorous derivation.

Spin glasssatisfiabilityleaf removalcavity method

Download to read the full article text

REFERENCES

1.
M. Mézard and G. Parisi, Eur. Phys. J. B 20:217(2001).Google Scholar
2.
O. C. Martin, R. Monasson, and R. Zecchina, Theoret. Comput. Sci. 265:3(2001).Google Scholar
3.
S. Franz, M. Mézard, F. Ricci-Tersenghi, M. Weigt, and R. Zecchina, Europhys. Lett. 55:465(2001).Google Scholar
4.
T. J. Schaefer, in Proc. 10th STOC (San Diego, CA, USA, ACM, 1978), p. 216. N. Creignou, H. Daudé, and O. Dubois, preprint arXiv:cs.DM/0106001.
5.
J. Hastad, J. ACM 48, 798(2001).Google Scholar
6.
F. Ricci-Tersenghi, M. Weigt, and R. Zecchina, Phys. Rev. E 63:026702(2001).Google Scholar
7.
A. Braunstein, M. Leone, F. Ricci-Tersenghi, and R. Zecchina, J. Phys. A 35:7559(2002), preprint arXiv: cond-mat/0203613, for the role of the dynamical transition on global algorithms.Google Scholar
8.
M. Mézard, G. Parisi, and R. Zecchina, Science 297:812(2002).Google Scholar
9.
M. Mézard and R. Zecchina, Phys. Rev. E 66:056126(2002), arXiv:cond-mat/0207194.Google Scholar
10.
For a very recent review on mathematical results on spin glass models see A. Bovier and I. Kurkova, preprint arXiv:cond-mat/0206562, and references therein.
11.
M. Leone, F. Ricci-Tersenghi, and R. Zecchina, J. Phys. A 34:4615(2001).Google Scholar
12.
S. Franz, M. Leone, F. Ricci-Tersenghi, and R. Zecchina, Phys. Rev. Lett. 87:127209(2001).Google Scholar
13.
M. Mézard, G. Parisi, and M. Virasoro, Spin Glass Theory and Beyond (World Scientific, Singapore, 1987).Google Scholar
14.
M. Mézard and G. Parisi, J. Stat. Phys. 111:1(2003), arXiv:cond-mat/0207121.Google Scholar
15.
V. F. Kolchin, Random Graphs (Cambridge University Press, 1999).
16.
B. Pittel, J. Spencer, and N. Wormald, J. Comb. Theory B 67:111(1996).Google Scholar
17.
M. Bauer and O. Golinelli, Eur. Phys. J. B 24:339(2001).Google Scholar
18.
M. Weigt, Eur. Phys. J. B 28:369(2002), preprint arXiv:cond-mat/0203281.Google Scholar
19.
S. Cocco, O. Dubois, J. Mandler, and R. Monasson, Phys. Rev. Lett. 90:047205(2003), preprint arXiv:cond-mat/0206239.Google Scholar

Two Solutions to Diluted p-Spin Models and XORSAT Problems

Abstract

Copyright information

Cookies