On the replica symmetric solution of the K-sat model
Abstract
In this paper we translate Talagrand’s solution of the K-sat model at high temperature into the language of asymptotic Gibbs measures. Using exact cavity equations in the infinite volume limit allows us to remove many technicalities of the inductions on the system size, which clarifies the main ideas of the proof. This approach also yields a larger region of parameters where the system is in a pure state and, in particular, for small connectivity parameter one can prove the replica symmetric formula for the free energy at any temperature.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-17
Publication Date: August 11, 2014
DOI: 10.1214/EJP.v19-2963
References
- Aldous, David J. Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 (1981), no. 4, 581--598. MR0637937
- Austin, T.: Exchangeable random measures. To appear in phAnn. Inst. Henri Poincaré Probab. Stat., arXiv:1302.2116 (2013).
- Franz, Silvio; Leone, Michele. Replica bounds for optimization problems and diluted spin systems. J. Statist. Phys. 111 (2003), no. 3-4, 535--564. MR1972121
- Hoover, D. N. Row-column exchangeability and a generalized model for probability. Exchangeability in probability and statistics (Rome, 1981), pp. 281--291, North-Holland, Amsterdam-New York, 1982. MR0675982
- Kallenberg, Olav. On the representation theorem for exchangeable arrays. J. Multivariate Anal. 30 (1989), no. 1, 137--154. MR1003713
- Montanari, Andrea; Shah, Devavrat. Counting good truth assignments of random $k$-SAT formulae. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1255--1264, ACM, New York, 2007. MR2485278
- Panchenko, Dmitry; Talagrand, Michel. Bounds for diluted mean-fields spin glass models. Probab. Theory Related Fields 130 (2004), no. 3, 319--336. MR2095932
- Panchenko, Dmitry. Spin glass models from the point of view of spin distributions. Ann. Probab. 41 (2013), no. 3A, 1315--1361. MR3098679
- Talagrand, Michel. The high temperature case for the random $K$-sat problem. Probab. Theory Related Fields 119 (2001), no. 2, 187--212. MR1818246
- Talagrand, Michel. Spin glasses: a challenge for mathematicians. Cavity and mean field models. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], 46. Springer-Verlag, Berlin, 2003. x+586 pp. ISBN: 3-540-00356-8 MR1993891
- Talagrand, M.: Mean-Field Models for Spin Glasses. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge A Series of Modern Surveys in Mathematics, Vol. 54, Springer-Verlag, Berlin, 2011. xviii+485 pp. ISBN: 978-3-642-15201-6 MR2731561
This work is licensed under a Creative Commons Attribution 3.0 License.