OPTIMIZATION ALGORITHMS IN PHYSICS
1 Statistical inference with probabilistic graphical models 1 11 Introduction to graphical models 3 12 Inference algorithms: elimination, junction tree, and belief propagation 10 13 Understanding belief propagation 17 14 Learning graphical models 22 References 27 2 Computational complexity, phase transitions, and message-passing for community detection 29 21 Computational complexity 31 22 Hardness: P, NP, or EXP? 35 23 Random graphs 38 24 Random k-SAT 43 25 Community detection 49 26 Appendix 59 References 60 3 Replica theory and spin glasses 61 31 Introduction to the replica method: the Wigner law 63 32 The Sherrington–Kirkpatrick model 69 33 Pure states, ultrametricity, and stochastic stability in the RSB phase of the SK model 80 34 Thermodynamic limit in the SK model and exactness of the hierarchical RSB solution: rigorous results 86 References 93 4 Cavity method: message-passing from a physics perspective 95 41 Replica solution without replicas 97 42 Cavity method for diluted graph models 103 43 An example: random K-SAT problem 113 References 124 5 Statistical estimation: from denoising to sparse regression and hidden cliques 127 51 Statistical estimation and linear models 129 52 Nonlinear denoising and sparsity 141 53 Denoising with thresholding 150 54 Sparse regression 156 55 Random designs and approximate message passing 164 56 The hidden clique problem 171 References 182 6 Error correcting codes and spatial coupling 187 61 Polar codes 189 62 Applications 198 63 Low-density parity-check codes 199 64 Spatially coupled codes 210 65 Density evolution for coupled codes 214 66 Threshold saturation 217 References 228 7 Constraint satisfaction: random regular k-SAT 231 71 A first approach 233 72 Beyond the condensation threshold 244 73 Notes and references 250 References 250 8 Local algorithms for graphs 253 81 Introduction 255 82 Power of the local algorithms 256 83 Incursion in a loopy land 259 84 The monomer–dimer entropy 260 85 Limits of local algorithms 260 9 Expectation propagation 263 91 Introduction 265 92 Approximate variational inference 265 93 Expectation propagation 267 94 Adaptive TAP 270 95 The Gibbs free energy 275 96 Improving and quantifying the accuracy of EP 277 97 Some advanced topics and applications 287 98 Conclusion: open problems with EP 290 References 291