Complex Systems

Jean-Philippe Bouchaud, Marc Mézard, Jean Dalibard Ph.D.0444530061, 9780444530066, 9780080550596

There has been recently some interdisciplinary convergence on a number of precise topics which can be considered as prototypes of complex systems. This convergence is best appreciated at the level of the techniques needed to deal with these systems, which include: 1) A domain of research around a multiple point where statistical physics, information theory, algorithmic computer science, and more theoretical (probabilistic) computer science meet: this covers some aspects of error correcting codes, stochastic optimization algorithms, typical case complexity and phase transitions, constraint satisfaction problems. 2) The study of collective behavior of interacting agents, its impact on understanding some types of economical and financial problems, their link to population and epidemics dynamics, game theory, social, biological and computer networks and evolution. The present book is the written version of the lectures given during the Les Houches summer school session on “Complex Systems”, devoted to these emerging interdisciplinary fields. The lectures consist both in a number of long methodological courses (probability theory, statistical physics of disordered systems, information theory, network structure and evolution, agent-based economics and numerical methods) and more specific, ‘problem oriented’ courses. Lecturers are all leading experts in their field; they have summarized recent results in a clear and authoritative manner. The “Les Houches lecture notes” have a long tradition of excellence and are often found to be useful for a number of years after they were written. The book is of interest to students and researchers with various backgrounds: probability theory, computer science, information theory, physics, finance, biology, etc. · Topical and comprehensive survey of the emerging, interdisciplinary field of “Complex Systems”, covered by recognized world experts · “Les Houches lectures notes”: a long tradition of excellence and long-lasting impact · Of interest to a broad audience (mathematics, physics, biology, informatics, finance, geology, etc.) · Some applications may have concrete impact · Selected topics in complex systems: forefront of research in the field

---

Table of contents :
Front cover……Page 1
Complex Systems……Page 4
Copyright page……Page 5
Previous sessions……Page 7
Lecturers……Page 10
Seminar Speakers……Page 12
Participants……Page 14
Auditors……Page 17
Preface……Page 18
Contents……Page 22
Course 1. Introduction to phase transitions in random optimization problems……Page 30
1. Introduction……Page 34
2. Basic concepts: overview of static phase transitions in K-XORSAT……Page 37
3. Advanced methods (I): replicas……Page 54
4. Advanced methods (II): cavity……Page 63
5. Dynamical phase transitions and search algorithms……Page 70
6. Conclusions……Page 88
Appendix A. A primer on large deviations……Page 89
Appendix B. Inequalities of first and second moments……Page 91
Appendix C. Corrections to the saddle-point calculation of ……Page 92
References……Page 93
Course 2. Modern coding theory: the statistical mechanics and computer science point of view……Page 96
1. Introduction and outline……Page 100
2. Background: the channel coding problem……Page 101
3. Sparse graph codes……Page 111
4. The decoding problem for sparse graph codes……Page 118
5. Belief Propagation beyond coding theory……Page 139
6. Belief Propagation beyond the binary symmetric channel……Page 143
7. Open problems……Page 153
Appendix A. A generating function calculation……Page 155
References……Page 156
Course 3. Mean field theory of spin glasses: statics and dynamics……Page 160
1. Introduction……Page 164
2. General considerations……Page 165
3. Mean field theory……Page 166
4. Many equilibrium states……Page 173
5. The explicit solution of the Sherrington Kirkpatrick model……Page 181
6. Bethe lattices……Page 192
7. Finite dimensions……Page 198
9. Conclusions……Page 203
References……Page 205
Course 4. Random matrices, the Ulam Problem, directed polymers & growth models, and sequence matching……Page 208
1. Introduction……Page 212
2. Random matrices: the Tracy-Widom distribution for the largest eigenvalue……Page 214
3. The longest common subsequence problem (or the Ulam problem)……Page 220
4. Directed polymers and growth models……Page 223
5. Sequence matching problem……Page 233
6. Conclusion……Page 240
References……Page 243
Course 5. Economies with interacting agents……Page 246
1. Introduction……Page 250
2. Models of segregation: a physical analogy……Page 253
3. Market relations……Page 260
4. Financial markets……Page 267
5. Contributions to public goods……Page 275
6. Conclusion……Page 281
References……Page 282
Course 6. Crackling noise and avalanches: scaling, critical phenomena, and the renormalization group……Page 286
2. What is crackling noise?……Page 290
3. Hysteresis and Barkhausen noise in magnets……Page 293
4. Why crackling noise?……Page 298
5. Self-similarity and its consequences……Page 305
References……Page 315
Course 7. Bootstrap and jamming percolation……Page 318
1. Introduction……Page 322
2. Bootstrap Percolation (BP)……Page 324
3. Jamming Percolation (JP)……Page 329
4. Related stochastic models……Page 336
References……Page 337
Course 8. Complex networks……Page 338
1. Introduction……Page 342
2. Network expansion and the small-world effect……Page 345
3. Degree distributions……Page 350
4. Further directions……Page 366
References……Page 368
Course 9. Minority games……Page 372
1. Introduction……Page 376
2. The minority game: definition and numerical simulations……Page 378
3. Exact solutions……Page 386
4. Application and extensions……Page 392
References……Page 399
Course 10. Metastable states in glassy systems……Page 402
1. Introduction……Page 406
2. Mean-field Spin Glasses……Page 407
3. The complexity……Page 409
4. Supersymmetry breaking and structure of the states……Page 412
5. Models in finite dimension……Page 416
6. Conclusion……Page 420
References……Page 421
Course 11. Evolutionary dynamics……Page 424
1. Introduction and Questions……Page 428
2. Analysis of phenomenological models……Page 436
3. Acquisition of multiple beneficial mutations……Page 451
4. Recombination and sex……Page 464
5. Deleterious intermediaries and combinatoric possibilities……Page 466
6. Beyond the simplest questions……Page 469
7. The state of the field……Page 473
References……Page 474
Course 12. Statistical modelling and analysis of biological networks……Page 476
1. A primer in Bayesian analysis……Page 481
2. Bayesian analysis of biological networks……Page 487
3. Applications……Page 493
4. Conclusion and outlook……Page 497
References……Page 498
Course 13. The slow dynamics of glassy materials: insights from computer simulations……Page 502
References……Page 510
Course 14. Epigenetic landscape and catastrophe theory: commentary on a correspondence……Page 512
Selected Bibliography……Page 518
Course 15. A hike in the phases of the 1-in-3 satisfiability……Page 520
1. Introduction……Page 524
2. Results……Page 525
3. Concluding remarks……Page 526
References……Page 527