Information, Physics, and Computation

Cover Page......Page 1
Title Page......Page 4
ISBN 978–0198570837......Page 5
Preface......Page 6
4 A probabilistic toolbox......Page 10
10 Satisfiability......Page 11
16 The assignment problem......Page 12
22 An ongoing story......Page 13
References, Index......Page 14
Part I Background......Page 16
1.1 Random variables......Page 18
1.2 Entropy......Page 20
1.3 Sequences of random variables and their entropy rate......Page 23
1.4 Correlated variables and mutual information......Page 25
1.5 Data compression......Page 27
1.6 Data transmission......Page 31
Notes......Page 36
2 Statistical physics and probability theory......Page 38
2.1 The Boltzmann distribution......Page 39
2.2 Thermodynamic potentials......Page 43
2.3 The fluctuation–dissipation relations......Page 47
2.4 The thermodynamic limit......Page 48
2.5 Ferromagnets and Ising models......Page 50
2.6 The Ising spin glass......Page 59
Notes......Page 61
3 Introduction to combinatorial optimization......Page 62
3.1 A first example: The minimum spanning tree......Page 63
3.3 More examples......Page 66
3.4 Elements of the theory of computational complexity......Page 69
3.5 Optimization and statistical physics......Page 75
3.6 Optimization and coding......Page 76
Notes......Page 77
4.1 Many random variables: A qualitative preview......Page 80
4.2 Large deviations for independent variables......Page 81
4.3 Correlated variables......Page 87
4.4 The Gibbs free energy......Page 92
4.5 The Monte Carlo method......Page 95
4.6 Simulated annealing......Page 101
4.7 Appendix: A physicist’s approach to Sanov’s theorem......Page 102
Notes......Page 104
Part II Independence......Page 106
5.1 Definition of the model......Page 108
5.2 Thermodynamics of the REM......Page 109
5.3 The condensation phenomenon......Page 115
5.4 A comment on quenched and annealed averages......Page 116
5.5 The random subcube model......Page 118
Notes......Page 120
6.1 Code ensembles......Page 122
6.2 The geometry of the random code ensemble......Page 125
6.3 Communicating over a binary symmetric channel......Page 127
6.4 Error-free communication with random codes......Page 135
6.5 Geometry again: Sphere packing......Page 138
6.6 Other random codes......Page 141
6.7 A remark on coding theory and disordered systems......Page 142
Notes......Page 143
7.1 A fair distribution into two groups?......Page 146
7.2 Algorithmic issues......Page 147
7.3 Partition of a random list: Experiments......Page 148
7.4 The random cost model......Page 151
7.5 Partition of a random list: Rigorous results......Page 155
Notes......Page 158
8.1 Replica solution of the random energy model......Page 160
8.2 The fully connected p-spin glass model......Page 170
8.3 Extreme value statistics and the REM......Page 178
8.4 Appendix: Stability of the RS saddle point......Page 181
Notes......Page 184
Part III Models on graphs......Page 186
9.1 Factor graphs......Page 188
9.2 Ensembles of factor graphs: Definitions......Page 195
9.3 Random factor graphs: Basic properties......Page 197
9.4 Random factor graphs: The giant component......Page 202
9.5 The locally tree-like structure of random graphs......Page 206
Notes......Page 209
10.1 The satisfiability problem......Page 212
10.2 Algorithms......Page 214
10.3 Random K-satisfiability ensembles......Page 221
10.5 The phase transition in random K(>= 3)-SAT......Page 224
Notes......Page 232
11 Low-density parity-check codes......Page 234
11.1 Definitions......Page 235
11.2 The geometry of the codebook......Page 237
11.3 LDPC codes for the binary symmetric channel......Page 246
11.4 A simple decoder: Bit flipping......Page 251
Notes......Page 254
12.1 Spin glasses and factor graphs......Page 256
12.2 Spin glasses: Constraints and frustration......Page 260
12.3 What is a glass phase?......Page 265
12.4 An example: The phase diagram of the SK model......Page 277
Notes......Page 280
13 Bridges: Inference and the Monte Carlo method......Page 282
13.1 Statistical inference......Page 283
13.2 The Monte Carlo method: Inference via sampling......Page 287
13.3 Free-energy barriers......Page 296
Notes......Page 302
Part IV Short-range correlations......Page 304
14 Belief propagation......Page 306
14.1 Two examples......Page 307
14.2 Belief propagation on tree graphs......Page 311
14.3 Optimization: Max-product and min-sum......Page 320
14.4 Loopy BP......Page 325
14.5 General message-passing algorithms......Page 331
14.6 Probabilistic analysis......Page 332
Notes......Page 340
15.1 BP decoding: The algorithm......Page 342
15.2 Analysis: Density evolution......Page 344
15.3 BP decoding for an erasure channel......Page 357
15.4 The Bethe free energy and MAP decoding......Page 362
Notes......Page 367
16 The assignment problem......Page 370
16.1 The assignment problem and random assignment ensembles......Page 371
16.2 Message passing and its probabilistic analysis......Page 372
16.3 A polynomial message-passing algorithm......Page 381
16.4 Combinatorial results......Page 386
16.5 An exercise: Multi-index assignment......Page 391
Notes......Page 393
17.1 The BP equations for Ising spins......Page 396
17.2 RS cavity analysis......Page 399
17.3 Ferromagnetic model......Page 401
17.4 Spin glass models......Page 406
Notes......Page 414
Part V Long-range correlations......Page 416
18 Linear equations with Boolean variables......Page 418
18.1 Definitions and general remarks......Page 419
18.2 Belief propagation......Page 424
18.3 Core percolation and BP......Page 427
18.4 The SAT–UNSAT threshold in random XORSAT......Page 430
18.5 The Hard-SAT phase: Clusters of solutions......Page 436
18.6 An alternative approach: The cavity method......Page 437
Notes......Page 442
19 The 1RSB cavity method......Page 444
19.1 Beyond BP: Many states......Page 445
19.2 The 1RSB cavity equations......Page 449
19.3 A first application: XORSAT......Page 459
19.4 The special value x =1......Page 464
19.5 Survey propagation......Page 468
19.6 The nature of 1RSB phases......Page 474
19.7 Appendix: The SP(y) equations for XORSAT......Page 478
Notes......Page 480
20 Random K-satisfiability......Page 482
20.1 Belief propagation and the replica-symmetric analysis......Page 483
20.2 Survey propagation and the 1RSB phase......Page 489
20.3 Some ideas about the full phase diagram......Page 500
20.4 An exercise: Colouring random graphs......Page 503
Notes......Page 506
21.1 Local search algorithms and metastable states......Page 508
21.2 The binary erasure channel......Page 515
21.3 General binary memoryless symmetric channels......Page 521
21.4 Metastable states and near-codewords......Page 528
Notes......Page 530
22 An ongoing story......Page 532
22.1 Gibbs measures and long-range correlations......Page 533
22.2 Higher levels of replica symmetry breaking......Page 539
22.3 Phase structure and the behaviour of algorithms......Page 550
Notes......Page 553
A.1 Equivalence relations......Page 556
A.2 Orders of growth......Page 557
A.3 Combinatorics and probability......Page 558
A.4 Summary of mathematical notation......Page 559
A.7 Cavity and message-passing methods......Page 560
References......Page 562
Index......Page 580