×

Local optima of the Sherrington-Kirkpatrick Hamiltonian. (English) Zbl 1426.82066

The Sherrington-Kirkpatrick Hamiltonian is defined by \[ H(\sigma)=\sum_{1\leq i < j\leq n}\sigma_i\sigma_jW_{ij}, \] where \(\sigma=(\sigma_i)\in \{-1,1\}^n\) is a configuration of spins and \(W_{ij}\), \(1\leq i < j\leq n\), are independent standart normed random variables.
A configuration \(\sigma\in \{-1,1\}^n\) is called local optimum if flipping the sign of any individual spin does not decrease the value of the Hamiltonian.
In the paper, the authors show that the expected number of local optima grows exponentially and the rate of growth is found. It is shown that the conditional distribution of \(H(\sigma)n^{-3/2}\) (given that \(\sigma\) is locally optimal) is concentrated on an interval of width \(O(n^{-1/4})\) and its location is determined.

MSC:

82D30 Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.; Spencer, J. H., The Probabilistic Method (2016) · Zbl 1333.05001
[2] Angel, O.; Bubeck, S.; Peres, Y.; Wei, F., Local max-cut in smoothed polynomial time, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC, 429-437 (2017) · Zbl 1369.68226
[3] Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities: A Nonasymptotic Theory of Independence (2013) · Zbl 1279.60005
[4] Crisanti, A.; Rizzo, T., Analysis of the ∞-replica symmetry breaking solution of the Sherrington-Kirkpatrick model, Phys. Rev. E, 65, 4, 046137 (2002) · Zbl 1244.82084 · doi:10.1103/physreve.65.046137
[5] Eastham, P. R.; Blythe, R. A.; Bray, A. J.; Moore, M. A., Mechanism for the failure of the Edwards hypothesis in the Sherrington-Kirkpatrick spin glass, Phys. Rev. B, 74, 020406 (2006) · doi:10.1103/physrevb.74.020406
[6] Etscheid, M.; Röglin, H., Smoothed analysis of local search for the maximum-cut problem, ACM Trans. Algorithms, 13, 2, 1 (2017) · Zbl 1421.68152 · doi:10.1145/3011870
[7] Hollander, F. D., Large Deviations (2000)
[8] Guerra, F., Broken replica symmetry bounds in the mean field spin glass model, Commun. Math. Phys., 233, 1, 1-12 (2003) · Zbl 1013.82023 · doi:10.1007/s00220-002-0773-5
[9] Panchenko, D., The Sherrington-Kirkpatrick Model (2013) · Zbl 1266.82005
[10] Parisi, G., A sequence of approximated solutions to the SK model for spin glasses, J. Phys. A: Math. Gen., 13, 4, L115 (1980) · doi:10.1088/0305-4470/13/4/009
[11] Sherrington, D.; Kirkpatrick, S., Solvable model of a spin-glass, Phys. Rev. Lett., 35, 26, 1792 (1975) · doi:10.1103/physrevlett.35.1792
[12] Talagrand, M., The Parisi formula, Ann. Math., 163, 221-263 (2006) · Zbl 1137.82010 · doi:10.4007/annals.2006.163.221
[13] Tanaka, F.; Edwards, S. F., Analytic theory of the ground state properties of a spin glass. I. Ising spin glass, J. Phys. F: Met. Phys., 10, 12, 2769 (1980) · doi:10.1088/0305-4608/10/12/017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.