Spin Glasses and Complexity

Daniel L. Stein is professor of physics and mathematics at New York University's Courant Institute of Mathematical Sciences. His books include Spin Glasses and Biology. Charles M. Newman is professor of mathematics at NYU's Courant Institute of Mathematical Sciences and at the University of California, Irvine. His books include Topics in Disordered Systems.

• Preface xi Introduction: Why Spin Glasses? 1 *1. Order, Symmetry, and the Organization of Matter 15 *1.1 The Symmetry of Physical Laws 17 *1.2 The Hamiltonian 23 *1.3 Broken Symmetry 26 *1.4 The Order Parameter 31 *1.5 Phases of Matter 35 *1.6 Phase Transitions 39 *1.7 Summary: The Unity of Condensed Matter Physics 41 2. Glasses and Quenchied Disorder 43 *2.1 Equilibrium and Non Equilibrium 43 * 2.2 The Glass Transition 45 *2.3 Localization 49 3. Magnetic Systems 51 *3.1 Spin 51 *3.2 Magnetism in Solids 53 *3.3 The Paramagnetic Phase 55 *3.4 Magnetization 55 *3.5 The Ferromagnetic Phase and Magnetic Susceptibility 57 *3.6 The Antiferromagnetic Phase 59 *3.7 Broken Symmetry and the Heisenberg Hamiltonian 59 4. Spin Glasses: General Features 63 *4.1 Dilute Magnetic Alloys and the Kondo Effect 64 *4.2 A New State of Matter? 65 *4.3 Nonequilibrium and Dynamical Behavior 71 *4.4 Mechanisms Underlying Spin Glass Behavior 74 *4.5 The Edwards-Anderson Hamiltonian 78 *4.6 Frustration 81 *4.7 Dimensionality and Phase Transitions 83 *4.8 Broken Symmetry and the Edwards-Anderson Order Parameter 85 *4.9 Energy Landscapes and Metastability 86 5. The Infinite-Range Spin Glass 90 *5.1 Mean Field Theory 90 *5.2 The Sherrington-Kirkpatrick Hamiltonian 92 *5.3 A Problem Arises 93 *5.4 The Remedy 95 *5.5 Thermodynamic States 97 *5.6 The Meaning of Replica Symmetry Breaking 98 *5.7 The Big Picture 109 6. Applications to Other Fields 112 *6.1 Computational Time Complexity and Combinatorial Optimization 113 *6.2 Neural Networks and Neural Computation 129 *6.3 Protein Folding and Conformational Dynamics 144 *6.4 Short Takes 168 7. Short-Range Spin Glasses: Some Basic Questions 175 *7.1 Ground States 177 *7.2 Pure States 188 *7.3 Scenarios for the Spin Glass Phase of the EA Model 193 *7.4 The Replica Symmetry Breaking and Droplet/Scaling Scenarios 194 *7.5 The Parisi Overlap Distribution 197 *7.6 Self-Averaging and Non-Self-Averaging 199 *7.7 Ruling Out the Standard RSB Scenario 201 *7.8 Chaotic Size Dependence and Metastates 203 *7.9 A New RSB Scenario 206 *7.10 Two More (Relatively) New Scenarios 211 *7.11 Why Should the SK Model Behave Differently from the EA Model? 214 *7.12 Summary: Where Do We Stand? 216 8. Are Spin Glasses Complex Systems? 218 *8.1 Three Foundational Papers 219 *8.2 Spin Glasses as a Bridge to Somewhere 227 *8.3 Modern Viewpoints on Complexity 228 *8.4 Spin Glasses: Old, New, and Quasi-Complexity 233 Notes 239 Glossary 265 Bibliography 285 Index 309

"The challenge that Stein and Newman faced in creating this book ... was to write for a broad range of readers and still offer interesting depth. As they state in the preface, they are aiming for a reading level that is between Scientific American and research journals. This reviewer believes they have succeeded... Stein and Newman write well and keep the mathematics to a minimum."--Choice "[A] surprisingly broad field of view is visible through the lens of the classical, equilibrium using spin glass and the authors are able to use it to explore many fascinating topics. Stein and Newman have written an excellent introduction to the field of spin glasses and the many ramifications of spin glass theory outside of condensed matter physics and statistical mechanics. Experts and novices alike will find this book interesting and useful."--Jonathan Machta, Journal of Statistical Physics "Spin Glasses and Complexity is not a journalistic book that merely reports on the subject. Based on profound mathematical insights, here distilled into an incisive presentation, it represents the fruit of the lifelong commitments two experts have made to spin-glass theory within and beyond physics... Spin Glasses and Complexity is unique in successfully bringing this thrilling theme to a broader scientific audience."--Stefan Boettcher, Physics Today "[T]he work is well presented and the reader will surely find it both inspiring and interesting."--Marco Castrillon Lopez, European Mathematical Society "Well presented and the reader will surely find it both inspiring and interesting."--Marco Castrillon Lopez, European Mathematical Society