| |
| |
| |
| Independence | |
| |
| |
| |
| The random energy model | |
| |
| |
| |
| Definition of the model | |
| |
| |
| |
| Thermodynamics of the REM | |
| |
| |
| |
| The condensation phenomenon | |
| |
| |
| |
| A comment on quenched and annealed averages | |
| |
| |
| |
| The random subcube model | |
| |
| |
| Notes | |
| |
| |
| |
| The random code ensemble | |
| |
| |
| |
| Code ensembles | |
| |
| |
| |
| The geometry of the random code ensemble | |
| |
| |
| |
| Communicating over a binary symmetric channel | |
| |
| |
| |
| Error-free communication with random codes | |
| |
| |
| |
| Geometry again: Sphere packing | |
| |
| |
| |
| Other random codes | |
| |
| |
| |
| A remark on coding theory and disordered systems | |
| |
| |
| |
| Appendix: Proof of Lemma 6.2 | |
| |
| |
| Notes | |
| |
| |
| |
| Number partitioning | |
| |
| |
| |
| A fair distribution into two groups? | |
| |
| |
| |
| Algorithmic issues | |
| |
| |
| |
| Partition of a random list: Experiments | |
| |
| |
| |
| The random cost model | |
| |
| |
| |
| Partition of a random list: Rigorous results | |
| |
| |
| Notes | |
| |
| |
| |
| Introduction to replica theory | |
| |
| |
| |
| Replica solution of the random energy model | |
| |
| |
| |
| The fully connected p-spin glass model | |
| |
| |
| |
| Extreme value statistics and the REM | |
| |
| |
| |
| Appendix: Stability of the RS saddle point | |
| |
| |
| Notes | |
| |
| |
| |
| Models on Graphs | |
| |
| |
| |
| Factor graphs and graph ensembles | |
| |
| |
| |
| Factor graphs | |
| |
| |
| |
| Ensembles of factor graphs: Definitions | |
| |
| |
| |
| Random factor graphs: Basic properties | |
| |
| |
| |
| Random factor graphs: The giant component | |
| |
| |
| |
| The locally tree-like structure of random graphs | |
| |
| |
| Notes | |
| |
| |
| |
| Satisfiability | |
| |
| |
| |
| The satisfiability problem | |
| |
| |
| |
| Algorithms | |
| |
| |
| |
| Random K-satisfiability ensembles | |
| |
| |
| |
| Random 2-SAT | |
| |
| |
| |
| The phase transition in random K(>q; 3)-SAT | |
| |
| |
| Notes | |
| |
| |
| |
| Low-density parity-check codes | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| The geometry of the codebook | |
| |
| |
| |
| LDPC codes for the binary symmetric channel | |
| |
| |
| |
| A simple decoder: Bit flipping | |
| |
| |
| Notes | |
| |
| |
| |
| Spin glasses | |
| |
| |
| |
| Spin glasses and factor graphs | |
| |
| |
| |
| Spin glasses: Constraints and frustration | |
| |
| |
| |
| What is a glass phase? | |
| |
| |
| |
| An example: The phase diagram of the SK model | |
| |
| |
| Notes | |
| |
| |
| |
| Bridges: Inference and the Monte Carlo method | |
| |
| |
| |
| Statistical inference | |
| |
| |
| |
| The Monte Carlo method: Inference via sampling | |
| |
| |
| |
| Free-energy barriers | |
| |
| |
| Notes | |
| |
| |
| |
| Short-Range Correlations | |
| |
| |
| |
| Belief propagation | |
| |
| |
| |
| Two examples | |
| |
| |
| |
| Belief propagation on tree graphs | |
| |
| |
| |
| Optimization: Max-product and min-sum | |
| |
| |
| |
| Loopy BP | |
| |
| |
| |
| General message-passing algorithms | |
| |
| |
| |
| Probabilistic analysis | |
| |
| |
| Notes | |
| |
| |
| |
| Decoding with belief propagation | |
| |
| |
| |
| BP decoding: The algorithm | |
| |
| |
| |
| Analysis: Density evoluation | |
| |
| |
| |
| BP decoding for an erasure channel | |
| |
| |
| |
| The Bethe free energy and MAP decoding | |
| |
| |
| Notes | |
| |
| |
| |
| The assignment problem | |
| |
| |
| |
| The assignment problem and random assignment ensembles | |
| |
| |
| |
| Message passing and its probabilistic analysis | |
| |
| |
| |
| A polynomial message-passing algorithm | |
| |
| |
| |
| Combinatorial results | |
| |
| |
| |
| An exercise: Multi-index assignment | |
| |
| |
| Notes | |
| |
| |
| |
| Ising models on random graphs | |
| |
| |
| |
| The BP equations for Ising spins | |
| |
| |
| |
| RS cavity analysis | |
| |
| |
| |
| Ferromagnetic model | |
| |
| |
| |
| Spin glass models | |
| |
| |
| Notes | |
| |
| |
| |
| Long-Range Correlations | |
| |
| |
| |
| Linear equations with Boolean variables | |
| |
| |
| |
| Definitions and general remarks | |
| |
| |
| |
| Belief propagation | |
| |
| |
| |
| Core percolation and BP | |
| |
| |
| |
| The Sat-Unsat threshold in random Xorsat | |
| |
| |
| |
| The Hard-Sat phase: Clusters of solutions | |
| |
| |
| |
| An alternative approach: The cavity method | |
| |
| |
| Notes | |
| |
| |
| |
| The 1RSB cavity method | |
| |
| |
| |
| Beyond BP: Many states | |
| |
| |
| |
| The 1RSB cavity equations | |
| |
| |
| |
| A first application: Xorsat | |
| |
| |
| |
| The special value x=1 | |
| |
| |
| |
| Survey propagation | |
| |
| |
| |
| The nature of 1RSB phases | |
| |
| |
| |
| Appendix: The SP(y) equations for Xorsat | |
| |
| |
| Notes | |
| |
| |
| |
| Random K-satisfiability | |
| |
| |
| |
| Belief propagation and the replica-symmetric analysis | |
| |
| |
| |
| Survey propagation and the 1RSB phase | |
| |
| |
| |
| Some ideas about the full phase diagram | |
| |
| |
| |
| An exercise: Colouring random graphs | |
| |
| |
| Notes | |
| |
| |
| |
| Glassy states in coding theory | |
| |
| |
| |
| Local search algorithms and metastable states | |
| |
| |
| |
| The binary erasure channel | |
| |
| |
| |
| General binary memoryless symmetric channels | |
| |
| |
| |
| Metastable states and near-codewords | |
| |
| |
| Notes | |
| |
| |
| |
| An ongoing story | |
| |
| |
| |
| Gibbs measures and long-range correlations | |
| |
| |
| |
| Higher levels of replica symmetry breaking | |
| |
| |
| |
| Phase structure and the behaviour of algorithms | |
| |
| |
| Notes | |
| |
| |
| |
| Symbols and notation | |
| |
| |
| |
| Equivalence relations | |
| |
| |
| |
| Orders of growth | |
| |
| |
| |
| Combinatorics and probability | |
| |
| |
| |
| Summary of mathematical notation | |
| |
| |
| |
| Information theory | |
| |
| |
| |
| Factor graphs | |
| |
| |
| |
| Cavity and message-passing methods | |
| |
| |
| References | |
| |
| |
| Index | |