Complex Systems, Volume LXXXV: Lecture Notes of the Les Houches Summer School 2006 (Les Houches) (Les Houches)

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 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 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: 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; and, 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. This book presents topical and comprehensive survey of the emerging, interdisciplinary field of "Complex Systems", covered by recognized world experts. It includes "Les Houches lectures notes": a long tradition of excellence and long-lasting impact. It is 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 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 1) A domain of research around a multiple point where statistical physics, information theory, algorithmic computer science, and more theoretical (probabilistic) computer science 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 probability theory, computer science, information theory, physics, finance, biology, etc.ATopical and comprehensive survey of the emerging, interdisciplinary field of Complex Systems, covered by recognized world expertsALes Houches lectures a long tradition of excellence and long-lasting impactAOf interest to a broad audience (mathematics, physics, biology, informatics, finance, geology, etc.)ASome applications may have concrete impactASelected topics in complex forefront of research in the field" Content: Organizers Page ix Lecturers Pages ix-xi Seminar speakers Pages xi-xii Participants Pages xiii-xvi Auditors Page xvi Preface Pages xvii-xx Course 1 Introduction to phase transitions in random optimization problems Review Article Pages 1-65 R. Monasson Course 2 Modern coding theory: The statistical mechanics and computer science point of view Review Article Pages 67-130 Andrea Montanari, Rüdiger Urbanke Course 3 Mean field theory of spin glasses: Statics and dynamics Review Article Pages 131-178 Giorgio Parisi Course 4 Random matrices, the ulam problem, directed polymers & growth models, and sequence matching Review Article Pages 179-216 Satya N. Majumdar Course 5 Economies with interacting agents Review Article Pages 217-255 Alan Kirman Course 6 Crackling noise and avalanches: Scaling, critical phenomena, and the renormalization group Review Article Pages 257-288 James P. Sethna Course 7 Bootstrap and jamming percolation Review Article Pages 289-308 C. Toninelli Course 8 Complex networks Review Article Pages 309-342 M.E.J. Newman Course 9 Minority games Review Article Pages 343-372 Damien Challet Course 10 Metastable states in glassy systems Review Article Pages 373-393 Irene Giardina Course 11 Evolutionary dynamics Review Article Pages 395-446 Daniel S. Fisher Course 12 Statistical modelling and analysis of biological networks Review Article Pages 447-471 Johannes Berg Course 13 The slow dynamics of glassy materials: Insights from computer simulations Review Article Pages 473-482 Ludovic Berthier Course 14 Epigenetic landscape and catastrophe theory: Commentary on a correspondence Review Article Pages 483-489 Sara Franceschelli Course 15 A hike in the phases of the 1-in-3 satisfiability Review Article Pages 491-498 Elitza Maneva, Talya Meltzer, Jack Raymond, Andrea Sportiello, Lenka Zdeborová