Information, Physics, and Computation

Information, Physics, and Computation

by Marc Mezard, Andrea Montanari
     
 

ISBN-10: 019857083X

ISBN-13: 9780198570837

Pub. Date: 03/27/2009

Publisher: Oxford University Press, USA

This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. It is accessible to graduate students and researchers without a specific training in any of these fields. The selected topics include spin glasses, error

Overview

This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. It is accessible to graduate students and researchers without a specific training in any of these fields. The selected topics include spin glasses, error correcting codes, satisfiability, and are central to each field. The approach focuses on large random instances, adopting a common probabilistic formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to study phase transitions.

Product Details

ISBN-13:
9780198570837
Publisher:
Oxford University Press, USA
Publication date:
03/27/2009
Series:
Oxford Graduate Texts Series
Edition description:
New Edition
Pages:
584
Product dimensions:
7.00(w) x 9.60(h) x 4.30(d)

Table of Contents

Part II Independence

5 The random energy model 93

5.1 Definition of the model 93

5.2 Thermodynamics of the REM 94

5.3 The condensation phenomenon 100

5.4 A comment on quenched and annealed averages 101

5.5 The random subcube model 103

Notes 105

6 The random code ensemble 107

6.1 Code ensembles 107

6.2 The geometry of the random code ensemble 110

6.3 Communicating over a binary symmetric channel 112

6.4 Error-free communication with random codes 120

6.5 Geometry again: Sphere packing 123

6.6 Other random codes 126

6.7 A remark on coding theory and disordered systems 127

6.8 Appendix: Proof of Lemma 6.2 128

Notes 128

7 Number partitioning 131

7.1 A fair distribution into two groups? 131

7.2 Algorithmic issues 132

7.3 Partition of a random list: Experiments 133

7.4 The random cost model 136

7.5 Partition of a random list: Rigorous results 140

Notes 143

8 Introduction to replica theory 145

8.1 Replica solution of the random energy model 145

8.2 The fully connected p-spin glass model 155

8.3 Extreme value statistics and the REM 163

8.4 Appendix: Stability of the RS saddle point 166

Notes 169

Part III Models on Graphs

9 Factor graphs and graph ensembles 173

9.1 Factor graphs 173

9.2 Ensembles of factor graphs: Definitions 180

9.3 Random factor graphs: Basic properties 182

9.4 Random factor graphs: The giant component 187

9.5 The locally tree-like structure of random graphs 191

Notes 194

10 Satisfiability 197

10.1 The satisfiability problem 197

10.2 Algorithms 199

10.3 Random K-satisfiability ensembles 206

10.4 Random 2-SAT 209

10.5 The phase transition in random K(>q; 3)-SAT209

Notes 217

11 Low-density parity-check codes 219

11.1 Definitions 220

11.2 The geometry of the codebook 222

11.3 LDPC codes for the binary symmetric channel 231

11.4 A simple decoder: Bit flipping 236

Notes 239

12 Spin glasses 241

12.1 Spin glasses and factor graphs 241

12.2 Spin glasses: Constraints and frustration 245

12.3 What is a glass phase? 250

12.4 An example: The phase diagram of the SK model 262

Notes 265

13 Bridges: Inference and the Monte Carlo method 267

13.1 Statistical inference 268

13.2 The Monte Carlo method: Inference via sampling 272

13.3 Free-energy barriers 281

Notes 287

Part IV Short-Range Correlations

14 Belief propagation 291

14.1 Two examples 292

14.2 Belief propagation on tree graphs 296

14.3 Optimization: Max-product and min-sum 305

14.4 Loopy BP 310

14.5 General message-passing algorithms 316

14.6 Probabilistic analysis 317

Notes 325

15 Decoding with belief propagation 327

15.1 BP decoding: The algorithm 327

15.2 Analysis: Density evoluation 329

15.3 BP decoding for an erasure channel 342

15.4 The Bethe free energy and MAP decoding 347

Notes 352

16 The assignment problem 355

16.1 The assignment problem and random assignment ensembles 356

16.2 Message passing and its probabilistic analysis 357

16.3 A polynomial message-passing algorithm 366

16.4 Combinatorial results 371

16.5 An exercise: Multi-index assignment 376

Notes 378

17 Ising models on random graphs 381

17.1 The BP equations for Ising spins 381

17.2 RS cavity analysis 384

17.3 Ferromagnetic model 386

17.4 Spin glass models 391

Notes 399

Part V Long-Range Correlations

18 Linear equations with Boolean variables 403

18.1 Definitions and general remarks 404

18.2 Belief propagation 409

18.3 Core percolation and BP 412

18.4 The Sat-Unsat threshold in random Xorsat 415

18.5 The Hard-Sat phase: Clusters of solutions 421

18.6 An alternative approach: The cavity method 422

Notes 427

19 The 1RSB cavity method 429

19.1 Beyond BP: Many states 430

19.2 The 1RSB cavity equations 434

19.3 A first application: Xorsat 444

19.4 The special value x=1 449

19.5 Survey propagation 453

19.6 The nature of 1RSB phases 459

19.7 Appendix: The SP(y) equations for Xorsat 463

Notes 465

20 Random K-satisfiability 467

20.1 Belief propagation and the replica-symmetric analysis 468

20.2 Survey propagation and the 1RSB phase 474

20.3 Some ideas about the full phase diagram 485

20.4 An exercise: Colouring random graphs 488

Notes 491

21 Glassy states in coding theory 493

21.1 Local search algorithms and metastable states 493

21.2 The binary erasure channel 500

21.3 General binary memoryless symmetric channels 506

21.4 Metastable states and near-codewords 513

Notes 515

22 An ongoing story 517

22.1 Gibbs measures and long-range correlations 518

22.2 Higher levels of replica symmetry breaking 524

22.3 Phase structure and the behaviour of algorithms 535

Notes 538

Appendix A Symbols and notation 541

A.1 Equivalence relations 541

A.2 Orders of growth 542

A.3 Combinatorics and probability 543

A.4 Summary of mathematical notation 544

A.5 Information theory 545

A.6 Factor graphs 545

A.7 Cavity and message-passing methods 545

References 547

Index 565

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >