Skip to content

Information, Physics, and Computation

Best in textbook rentals since 2012!

ISBN-10: 019857083X

ISBN-13: 9780198570837

Edition: 2009

Authors: Marc M�zard, Andrea Montanari

List price: $96.00
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

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 andadopts 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…    
Customers also bought

Book details

List price: $96.00
Copyright year: 2009
Publisher: Oxford University Press, Incorporated
Publication date: 3/27/2009
Binding: Hardcover
Pages: 584
Size: 6.97" wide x 10.00" long x 1.32" tall
Weight: 2.838
Language: English

Independence
The random energy model
Definition of the model
Thermodynamics of the REM
The condensation phenomenon
A comment on quenched and annealed averages
The random subcube model
Notes
The random code ensemble
Code ensembles
The geometry of the random code ensemble
Communicating over a binary symmetric channel
Error-free communication with random codes
Geometry again: Sphere packing
Other random codes
A remark on coding theory and disordered systems
Appendix: Proof of Lemma 6.2
Notes
Number partitioning
A fair distribution into two groups?
Algorithmic issues
Partition of a random list: Experiments
The random cost model
Partition of a random list: Rigorous results
Notes
Introduction to replica theory
Replica solution of the random energy model
The fully connected p-spin glass model
Extreme value statistics and the REM
Appendix: Stability of the RS saddle point
Notes
Models on Graphs
Factor graphs and graph ensembles
Factor graphs
Ensembles of factor graphs: Definitions
Random factor graphs: Basic properties
Random factor graphs: The giant component
The locally tree-like structure of random graphs
Notes
Satisfiability
The satisfiability problem
Algorithms
Random K-satisfiability ensembles
Random 2-SAT
The phase transition in random K(&gtq; 3)-SAT
Notes
Low-density parity-check codes
Definitions
The geometry of the codebook
LDPC codes for the binary symmetric channel
A simple decoder: Bit flipping
Notes
Spin glasses
Spin glasses and factor graphs
Spin glasses: Constraints and frustration
What is a glass phase?
An example: The phase diagram of the SK model
Notes
Bridges: Inference and the Monte Carlo method
Statistical inference
The Monte Carlo method: Inference via sampling
Free-energy barriers
Notes
Short-Range Correlations
Belief propagation
Two examples
Belief propagation on tree graphs
Optimization: Max-product and min-sum
Loopy BP
General message-passing algorithms
Probabilistic analysis
Notes
Decoding with belief propagation
BP decoding: The algorithm
Analysis: Density evoluation
BP decoding for an erasure channel
The Bethe free energy and MAP decoding
Notes
The assignment problem
The assignment problem and random assignment ensembles
Message passing and its probabilistic analysis
A polynomial message-passing algorithm
Combinatorial results
An exercise: Multi-index assignment
Notes
Ising models on random graphs
The BP equations for Ising spins
RS cavity analysis
Ferromagnetic model
Spin glass models
Notes
Long-Range Correlations
Linear equations with Boolean variables
Definitions and general remarks
Belief propagation
Core percolation and BP
The Sat-Unsat threshold in random Xorsat
The Hard-Sat phase: Clusters of solutions
An alternative approach: The cavity method
Notes
The 1RSB cavity method
Beyond BP: Many states
The 1RSB cavity equations
A first application: Xorsat
The special value x=1
Survey propagation
The nature of 1RSB phases
Appendix: The SP(y) equations for Xorsat
Notes
Random K-satisfiability
Belief propagation and the replica-symmetric analysis
Survey propagation and the 1RSB phase
Some ideas about the full phase diagram
An exercise: Colouring random graphs
Notes
Glassy states in coding theory
Local search algorithms and metastable states
The binary erasure channel
General binary memoryless symmetric channels
Metastable states and near-codewords
Notes
An ongoing story
Gibbs measures and long-range correlations
Higher levels of replica symmetry breaking
Phase structure and the behaviour of algorithms
Notes
Symbols and notation
Equivalence relations
Orders of growth
Combinatorics and probability
Summary of mathematical notation
Information theory
Factor graphs
Cavity and message-passing methods
References
Index