Independence | |
The random energy model | p. 93 |
Definition of the model | p. 93 |
Thermodynamics of the REM | p. 94 |
The condensation phenomenon | p. 100 |
A comment on quenched and annealed averages | p. 101 |
The random subcube model | p. 103 |
Notes | p. 105 |
The random code ensemble | p. 107 |
Code ensembles | p. 107 |
The geometry of the random code ensemble | p. 110 |
Communicating over a binary symmetric channel | p. 112 |
Error-free communication with random codes | p. 120 |
Geometry again: Sphere packing | p. 123 |
Other random codes | p. 126 |
A remark on coding theory and disordered systems | p. 127 |
Appendix: Proof of Lemma 6.2 | p. 128 |
Notes | p. 128 |
Number partitioning | p. 131 |
A fair distribution into two groups? | p. 131 |
Algorithmic issues | p. 132 |
Partition of a random list: Experiments | p. 133 |
The random cost model | p. 136 |
Partition of a random list: Rigorous results | p. 140 |
Notes | p. 143 |
Introduction to replica theory | p. 145 |
Replica solution of the random energy model | p. 145 |
The fully connected p-spin glass model | p. 155 |
Extreme value statistics and the REM | p. 163 |
Appendix: Stability of the RS saddle point | p. 166 |
Notes | p. 169 |
Models on Graphs | |
Factor graphs and graph ensembles | p. 173 |
Factor graphs | p. 173 |
Ensembles of factor graphs: Definitions | p. 180 |
Random factor graphs: Basic properties | p. 182 |
Random factor graphs: The giant component | p. 187 |
The locally tree-like structure of random graphs | p. 191 |
Notes | p. 194 |
Satisfiability | p. 197 |
The satisfiability problem | p. 197 |
Algorithms | p. 199 |
Random K-satisfiability ensembles | p. 206 |
Random 2-SAT | p. 209 |
The phase transition in random K(>q; 3)-SAT | p. 209 |
Notes | p. 217 |
Low-density parity-check codes | p. 219 |
Definitions | p. 220 |
The geometry of the codebook | p. 222 |
LDPC codes for the binary symmetric channel | p. 231 |
A simple decoder: Bit flipping | p. 236 |
Notes | p. 239 |
Spin glasses | p. 241 |
Spin glasses and factor graphs | p. 241 |
Spin glasses: Constraints and frustration | p. 245 |
What is a glass phase? | p. 250 |
An example: The phase diagram of the SK model | p. 262 |
Notes | p. 265 |
Bridges: Inference and the Monte Carlo method | p. 267 |
Statistical inference | p. 268 |
The Monte Carlo method: Inference via sampling | p. 272 |
Free-energy barriers | p. 281 |
Notes | p. 287 |
Short-Range Correlations | |
Belief propagation | p. 291 |
Two examples | p. 292 |
Belief propagation on tree graphs | p. 296 |
Optimization: Max-product and min-sum | p. 305 |
Loopy BP | p. 310 |
General message-passing algorithms | p. 316 |
Probabilistic analysis | p. 317 |
Notes | p. 325 |
Decoding with belief propagation | p. 327 |
BP decoding: The algorithm | p. 327 |
Analysis: Density evoluation | p. 329 |
BP decoding for an erasure channel | p. 342 |
The Bethe free energy and MAP decoding | p. 347 |
Notes | p. 352 |
The assignment problem | p. 355 |
The assignment problem and random assignment ensembles | p. 356 |
Message passing and its probabilistic analysis | p. 357 |
A polynomial message-passing algorithm | p. 366 |
Combinatorial results | p. 371 |
An exercise: Multi-index assignment | p. 376 |
Notes | p. 378 |
Ising models on random graphs | p. 381 |
The BP equations for Ising spins | p. 381 |
RS cavity analysis | p. 384 |
Ferromagnetic model | p. 386 |
Spin glass models | p. 391 |
Notes | p. 399 |
Long-Range Correlations | |
Linear equations with Boolean variables | p. 403 |
Definitions and general remarks | p. 404 |
Belief propagation | p. 409 |
Core percolation and BP | p. 412 |
The Sat-Unsat threshold in random Xorsat | p. 415 |
The Hard-Sat phase: Clusters of solutions | p. 421 |
An alternative approach: The cavity method | p. 422 |
Notes | p. 427 |
The 1RSB cavity method | p. 429 |
Beyond BP: Many states | p. 430 |
The 1RSB cavity equations | p. 434 |
A first application: Xorsat | p. 444 |
The special value x=1 | p. 449 |
Survey propagation | p. 453 |
The nature of 1RSB phases | p. 459 |
Appendix: The SP(y) equations for Xorsat | p. 463 |
Notes | p. 465 |
Random K-satisfiability | p. 467 |
Belief propagation and the replica-symmetric analysis | p. 468 |
Survey propagation and the 1RSB phase | p. 474 |
Some ideas about the full phase diagram | p. 485 |
An exercise: Colouring random graphs | p. 488 |
Notes | p. 491 |
Glassy states in coding theory | p. 493 |
Local search algorithms and metastable states | p. 493 |
The binary erasure channel | p. 500 |
General binary memoryless symmetric channels | p. 506 |
Metastable states and near-codewords | p. 513 |
Notes | p. 515 |
An ongoing story | p. 517 |
Gibbs measures and long-range correlations | p. 518 |
Higher levels of replica symmetry breaking | p. 524 |
Phase structure and the behaviour of algorithms | p. 535 |
Notes | p. 538 |
Symbols and notation | p. 541 |
Equivalence relations | p. 541 |
Orders of growth | p. 542 |
Combinatorics and probability | p. 543 |
Summary of mathematical notation | p. 544 |
Information theory | p. 545 |
Factor graphs | p. 545 |
Cavity and message-passing methods | p. 545 |
References | p. 547 |
Index | p. 565 |
Table of Contents provided by Ingram. All Rights Reserved. |
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.