Complex systems : Ecole d'ete de Physique des Houches, session LXXXV, 3-28 July 2006 ; Ecole thematique du CNRS
Computational complexity System analysis Komplexes System SCIENCE TECHNOLOGY & ENGINEERING Conference proceedings sähkökirjat
Elsevier
2007
1st ed.
EISBN 9780080550596
Cover.
Previous sessions.
Organizers.
Lecturers.
Seminar Speakers.
Participants.
Auditors.
Preface.
Contents.
Course 1. Introduction to phase transitions in random optimization problems.
1. Introduction.
2. Basic concepts: overview of static phase transitions in K-XORSAT.
3. Advanced methods (I): replicas.
4. Advanced methods (II): cavity.
5. Dynamical phase transitions and search algorithms.
6. Conclusions.
Appendix A.A primer on large deviations.
Appendix B. Inequalities of first and second moments.
Appendix C. Corrections to the saddle-point calculation of.
References.
Course 2. Modern coding theory: the statistical mechanics and computer science point of view.
1. Introduction and outline.
2. Background: the channel coding problem.
3. Sparse graph codes.
4. The decoding problem for sparse graph codes.
5. Belief Propagation beyond coding theory.
6. Belief Propagation beyond the binary symmetric channel.
7. Open problems.
Appendix A.A generating function calculation.
References.
Course 3. Mean field theory of spin glasses: statics and dynamics.
1. Introduction.
2. General considerations.
3. Mean field theory.
4. Many equilibrium states.
5. The explicit solution of the Sherrington Kirkpatrick model.
6. Bethe lattices.
7. Finite dimensions.
8. Some other applications.
9. Conclusions.
References.
Course 4. Random matrices, the Ulam Problem, directed polymers & growth models, and sequence matching.
1. Introduction.
2. Random matrices: the Tracy-Widom distribution for the largest eigenvalue.
3. The longest common subsequence problem (or the Ulam problem).
4. Directed polymers and growth models.
5. Sequence matching problem.
6. Conclusion.
References.
Course 5. Economies with interacting agents.
1. Introduction.
2. Models of segregation: a physical analogy.
3. Market relations.
4. Financial markets.
5. Contributions to public goods.
6. Conclusion.
References.
Course 6. Crackling noise and avalanches: scaling, critical phenomena, and the renormalization group.
1. Preamble.
2. What is crackling noise?.
3. Hysteresis and Barkhausen noise in magnets.
4. Why crackling noise?.
5. Self-similarity and its consequences.
References.
Course 7. Bootstrap and jamming percolation.
1. Introduction.
2. Bootstrap Percolation (BP).
3. Jamming Percolation (JP).
4. Related stochastic models.
References.
Course 8. Complex networks.
1. Introduction.
2. Network expansion and the small-world effect.
3. Degree distributions.
4. Further directions.
References.
Course 9. Minority games.
1. Introduction.
2. The minority game: definition and numerical simulations.
3. Exact solutions.
4. Application and extensions.
5. Conclusions.
References.
Course 10. Me.
Previous sessions.
Organizers.
Lecturers.
Seminar Speakers.
Participants.
Auditors.
Preface.
Contents.
Course 1. Introduction to phase transitions in random optimization problems.
1. Introduction.
2. Basic concepts: overview of static phase transitions in K-XORSAT.
3. Advanced methods (I): replicas.
4. Advanced methods (II): cavity.
5. Dynamical phase transitions and search algorithms.
6. Conclusions.
Appendix A.A primer on large deviations.
Appendix B. Inequalities of first and second moments.
Appendix C. Corrections to the saddle-point calculation of
References.
Course 2. Modern coding theory: the statistical mechanics and computer science point of view.
1. Introduction and outline.
2. Background: the channel coding problem.
3. Sparse graph codes.
4. The decoding problem for sparse graph codes.
5. Belief Propagation beyond coding theory.
6. Belief Propagation beyond the binary symmetric channel.
7. Open problems.
Appendix A.A generating function calculation.
References.
Course 3. Mean field theory of spin glasses: statics and dynamics.
1. Introduction.
2. General considerations.
3. Mean field theory.
4. Many equilibrium states.
5. The explicit solution of the Sherrington Kirkpatrick model.
6. Bethe lattices.
7. Finite dimensions.
8. Some other applications.
9. Conclusions.
References.
Course 4. Random matrices, the Ulam Problem, directed polymers & growth models, and sequence matching.
1. Introduction.
2. Random matrices: the Tracy-Widom distribution for the largest eigenvalue.
3. The longest common subsequence problem (or the Ulam problem).
4. Directed polymers and growth models.
5. Sequence matching problem.
6. Conclusion.
References.
Course 5. Economies with interacting agents.
1. Introduction.
2. Models of segregation: a physical analogy.
3. Market relations.
4. Financial markets.
5. Contributions to public goods.
6. Conclusion.
References.
Course 6. Crackling noise and avalanches: scaling, critical phenomena, and the renormalization group.
1. Preamble.
2. What is crackling noise?.
3. Hysteresis and Barkhausen noise in magnets.
4. Why crackling noise?.
5. Self-similarity and its consequences.
References.
Course 7. Bootstrap and jamming percolation.
1. Introduction.
2. Bootstrap Percolation (BP).
3. Jamming Percolation (JP).
4. Related stochastic models.
References.
Course 8. Complex networks.
1. Introduction.
2. Network expansion and the small-world effect.
3. Degree distributions.
4. Further directions.
References.
Course 9. Minority games.
1. Introduction.
2. The minority game: definition and numerical simulations.
3. Exact solutions.
4. Application and extensions.
5. Conclusions.
References.
Course 10. Me.
