Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
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 ...
More
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. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common 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 derive phase diagrams and study phase transitions.Less
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. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common 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 derive phase diagrams and study phase transitions.
Hidetoshi Nishimori
- Published in print:
- 2001
- Published Online:
- January 2010
- ISBN:
- 9780198509417
- eISBN:
- 9780191709081
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198509417.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Spin glasses are magnetic materials with strong disorder. Statistical mechanics has been a powerful tool to theoretically analyse various unique properties of spin glasses. A number of new analytical ...
More
Spin glasses are magnetic materials with strong disorder. Statistical mechanics has been a powerful tool to theoretically analyse various unique properties of spin glasses. A number of new analytical techniques have been developed to establish a theory of spin glasses. Surprisingly, these techniques have offered new tools and viewpoints for the understanding of information processing problems, including neural networks, error-correcting codes, image restoration, and optimization problems. A vast, interdisciplinary field has consequently been developing between physics and information, or more specifically, between the statistical physics of spin glasses and several important aspects of information processing tasks. This book provides a broad overview of this new field. It also contains detailed descriptions of the theory of spin glasses.Less
Spin glasses are magnetic materials with strong disorder. Statistical mechanics has been a powerful tool to theoretically analyse various unique properties of spin glasses. A number of new analytical techniques have been developed to establish a theory of spin glasses. Surprisingly, these techniques have offered new tools and viewpoints for the understanding of information processing problems, including neural networks, error-correcting codes, image restoration, and optimization problems. A vast, interdisciplinary field has consequently been developing between physics and information, or more specifically, between the statistical physics of spin glasses and several important aspects of information processing tasks. This book provides a broad overview of this new field. It also contains detailed descriptions of the theory of spin glasses.
Hidetoshi Nishimori
- Published in print:
- 2001
- Published Online:
- January 2010
- ISBN:
- 9780198509417
- eISBN:
- 9780191709081
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198509417.003.0005
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Reliable transmission of information through noisy channels plays a vital role in modern society. Some aspects of this problem have close formal similarities to the theory of spin glasses. Noise in ...
More
Reliable transmission of information through noisy channels plays a vital role in modern society. Some aspects of this problem have close formal similarities to the theory of spin glasses. Noise in the transmission channel can be related to random interactions in spin glasses and the bit sequence representing information corresponds to the Ising spin configuration. The replica method serves as a powerful tool of analysis, and TAP-like equations can be used as a practical implementation of the algorithm to infer the original message. The gauge theory also provides an interesting point of view. This chapter introduces these problems.Less
Reliable transmission of information through noisy channels plays a vital role in modern society. Some aspects of this problem have close formal similarities to the theory of spin glasses. Noise in the transmission channel can be related to random interactions in spin glasses and the bit sequence representing information corresponds to the Ising spin configuration. The replica method serves as a powerful tool of analysis, and TAP-like equations can be used as a practical implementation of the algorithm to infer the original message. The gauge theory also provides an interesting point of view. This chapter introduces these problems.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting ...
More
This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting performances, and offers a constructive proof of the ‘direct’ part of the channel coding theorem: it is possible to communicate with vanishing error probability as long as the communication rate is smaller than the channel capacity. It is also very closely related to the Random Energy Model.Less
This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting performances, and offers a constructive proof of the ‘direct’ part of the channel coding theorem: it is possible to communicate with vanishing error probability as long as the communication rate is smaller than the channel capacity. It is also very closely related to the Random Energy Model.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0011
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Low-density parity-check (LDPC) codes are among the most efficient error correcting codes in use. This chapter introduces an important family of LDPC ensembles, based on random factor graphs, and ...
More
Low-density parity-check (LDPC) codes are among the most efficient error correcting codes in use. This chapter introduces an important family of LDPC ensembles, based on random factor graphs, and studies some of their basic properties. It focuses on performances under optimal decoding, when no constraint is imposed on the computational complexity of the decoding procedure. Bounds in their performances are derived through an analysis of the geometric properties of their codebook. In particular, it shows that appropriately chosen LDPC ensembles allow for communication reliably at rates close to Shannon's capacity.Less
Low-density parity-check (LDPC) codes are among the most efficient error correcting codes in use. This chapter introduces an important family of LDPC ensembles, based on random factor graphs, and studies some of their basic properties. It focuses on performances under optimal decoding, when no constraint is imposed on the computational complexity of the decoding procedure. Bounds in their performances are derived through an analysis of the geometric properties of their codebook. In particular, it shows that appropriately chosen LDPC ensembles allow for communication reliably at rates close to Shannon's capacity.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter introduces some of the basic concepts of information theory, as well as the definitions and notations of probability theory that are used throughout the book. It defines the fundamental ...
More
This chapter introduces some of the basic concepts of information theory, as well as the definitions and notations of probability theory that are used throughout the book. It defines the fundamental notions of entropy, relative entropy, and mutual information. It also presents the main questions of information theory: data compression and data transmission. Finally, it offers a brief introduction to error correcting codes and Shannon's theory.Less
This chapter introduces some of the basic concepts of information theory, as well as the definitions and notations of probability theory that are used throughout the book. It defines the fundamental notions of entropy, relative entropy, and mutual information. It also presents the main questions of information theory: data compression and data transmission. Finally, it offers a brief introduction to error correcting codes and Shannon's theory.
Jennifer Beineke and Jason Rosenhouse (eds)
- Published in print:
- 2015
- Published Online:
- October 2017
- ISBN:
- 9780691164038
- eISBN:
- 9781400881338
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691164038.001.0001
- Subject:
- Mathematics, History of Mathematics
The history of mathematics is filled with major breakthroughs resulting from solutions to recreational problems. Problems of interest to gamblers led to the modern theory of probability, for example, ...
More
The history of mathematics is filled with major breakthroughs resulting from solutions to recreational problems. Problems of interest to gamblers led to the modern theory of probability, for example, and surreal numbers were inspired by the game of Go. Yet even with such groundbreaking findings and a wealth of popular-level books exploring puzzles and brainteasers, research in recreational mathematics has often been neglected. This book brings together authors from a variety of specialties to present fascinating problems and solutions in recreational mathematics. The chapters show how sophisticated mathematics can help construct mazes that look like famous people, how the analysis of crossword puzzles has much in common with understanding epidemics, and how the theory of electrical circuits is useful in understanding the classic Towers of Hanoi puzzle. The card game SET® is related to the theory of error-correcting codes, and simple tic-tac-toe takes on a new life when played on an affine plane. Inspirations for the book's wealth of problems include board games, card tricks, fake coins, flexagons, pencil puzzles, poker, and so much more. Looking at a plethora of eclectic games and puzzles, this book is sure to entertain, challenge, and inspire academic mathematicians and avid math enthusiasts alike.Less
The history of mathematics is filled with major breakthroughs resulting from solutions to recreational problems. Problems of interest to gamblers led to the modern theory of probability, for example, and surreal numbers were inspired by the game of Go. Yet even with such groundbreaking findings and a wealth of popular-level books exploring puzzles and brainteasers, research in recreational mathematics has often been neglected. This book brings together authors from a variety of specialties to present fascinating problems and solutions in recreational mathematics. The chapters show how sophisticated mathematics can help construct mazes that look like famous people, how the analysis of crossword puzzles has much in common with understanding epidemics, and how the theory of electrical circuits is useful in understanding the classic Towers of Hanoi puzzle. The card game SET® is related to the theory of error-correcting codes, and simple tic-tac-toe takes on a new life when played on an affine plane. Inspirations for the book's wealth of problems include board games, card tricks, fake coins, flexagons, pencil puzzles, poker, and so much more. Looking at a plethora of eclectic games and puzzles, this book is sure to entertain, challenge, and inspire academic mathematicians and avid math enthusiasts alike.
Christopher J. Gilmore, Kenneth Shankland, and Wei Dong
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199205530
- eISBN:
- 9780191718076
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199205530.003.0014
- Subject:
- Physics, Condensed Matter Physics / Materials
This chapter describes a combined maximum entropy/log-likelihood gain approach to crystal structure determination from powder diffraction data. The approach is described step-by-step, with a ...
More
This chapter describes a combined maximum entropy/log-likelihood gain approach to crystal structure determination from powder diffraction data. The approach is described step-by-step, with a particular emphasis on the optimal selection of basis set reflections and the calculation of the log likelihood. The active use of likelihood to partition the intensities of overlapping reflections is described in some detail and is illustrated with an example of phasing a framework structure. The use of error correcting codes as a means of controlling the rapid increase in the number of phase sets that arises from full factorial permutation is addressed.Less
This chapter describes a combined maximum entropy/log-likelihood gain approach to crystal structure determination from powder diffraction data. The approach is described step-by-step, with a particular emphasis on the optimal selection of basis set reflections and the calculation of the log likelihood. The active use of likelihood to partition the intensities of overlapping reflections is described in some detail and is illustrated with an example of phasing a framework structure. The use of error correcting codes as a means of controlling the rapid increase in the number of phase sets that arises from full factorial permutation is addressed.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0015
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and ...
More
This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.Less
This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.
