Information, physics, and computation / Marc Mezard, Andrea Montanari.

Format:

Book

Author/Creator:

Mezard, Marc.

Contributor:

Montanari, Andrea.

Series:

Oxford graduate texts.

Oxford graduate texts

Language:

English

Subjects (All):

Coding theory.

Computer science.

Statistical physics.

Physical Description:

1 online resource (584 p.)

Place of Publication:

Oxford ; New York : Oxford University Press, c2009.

Language Note:

English

Summary:

A very active field of research is emerging at the frontier of statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. This book sets up a common language and pool of concepts, accessible to students and researchers from each of these fields.

Contents:

Preface; Contents; PART I: BACKGROUND; 1 Introduction to information theory; 1.1 Random variables; 1.2 Entropy; 1.3 Sequences of random variables and their entropy rate; 1.4 Correlated variables and mutual information; 1.5 Data compression; 1.6 Data transmission; Notes; 2 Statistical physics and probability theory; 2.1 The Boltzmann distribution; 2.2 Thermodynamic potentials; 2.3 The fluctuation-dissipation relations; 2.4 The thermodynamic limit; 2.5 Ferromagnets and Ising models; 2.6 The Ising spin glass; Notes; 3 Introduction to combinatorial optimization

3.1 A first example: The minimum spanning tree3.2 General definitions; 3.3 More examples; 3.4 Elements of the theory of computational complexity; 3.5 Optimization and statistical physics; 3.6 Optimization and coding; Notes; 4 A probabilistic toolbox; 4.1 Many random variables: A qualitative preview; 4.2 Large deviations for independent variables; 4.3 Correlated variables; 4.4 The Gibbs free energy; 4.5 The Monte Carlo method; 4.6 Simulated annealing; 4.7 Appendix: A physicist's approach to Sanov's theorem; Notes; PART II: INDEPENDENCE; 5 The random energy model; 5.1 Definition of the model

5.2 Thermodynamics of the REM5.3 The condensation phenomenon; 5.4 A comment on quenched and annealed averages; 5.5 The random subcube model; Notes; 6 The random code ensemble; 6.1 Code ensembles; 6.2 The geometry of the random code ensemble; 6.3 Communicating over a binary symmetric channel; 6.4 Error-free communication with random codes; 6.5 Geometry again: Sphere packing; 6.6 Other random codes; 6.7 A remark on coding theory and disordered systems; 6.8 Appendix: Proof of Lemma 6.2; Notes; 7 Number partitioning; 7.1 A fair distribution into two groups?; 7.2 Algorithmic issues

7.3 Partition of a random list: Experiments7.4 The random cost model; 7.5 Partition of a random list: Rigorous results; Notes; 8 Introduction to replica theory; 8.1 Replica solution of the random energy model; 8.2 The fully connected p-spin glass model; 8.3 Extreme value statistics and the REM; 8.4 Appendix: Stability of the RS saddle point; Notes; PART III: MODELS ON GRAPHS; 9 Factor graphs and graph ensembles; 9.1 Factor graphs; 9.2 Ensembles of factor graphs: Definitions; 9.3 Random factor graphs: Basic properties; 9.4 Random factor graphs: The giant component

9.5 The locally tree-like structure of random graphsNotes; 10 Satisfiability; 10.1 The satisfiability problem; 10.2 Algorithms; 10.3 Random K-satisfiability ensembles; 10.4 Random 2-SAT; 10.5 The phase transition in random K(> 3)-SAT; Notes; 11 Low-density parity-check codes; 11.1 Definitions; 11.2 The geometry of the codebook; 11.3 LDPC codes for the binary symmetric channel; 11.4 A simple decoder: Bit flipping; Notes; 12 Spin glasses; 12.1 Spin glasses and factor graphs; 12.2 Spin glasses: Constraints and frustration; 12.3 What is a glass phase?

12.4 An example: The phase diagram of the SK model

Notes:

Description based upon print version of record.

Includes bibliographical references (p. [547]-564) and index.

Description based on print version record.

Description based on publisher supplied metadata and other sources.

ISBN:

0-19-154719-0

9786612076381

1-282-07638-8

OCLC:

363648024