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.0008
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
In the past twenty-five years, the replica method has evolved into a rather sophisticated tool for attacking theoretical problems as diverse as spin glasses, protein folding, vortices in ...
More
In the past twenty-five years, the replica method has evolved into a rather sophisticated tool for attacking theoretical problems as diverse as spin glasses, protein folding, vortices in superconductors, combinatorial optimization, etc. Although it is not be the main tool of this book, it is nevertheless instructive to have some knowledge of replicas: the replica method is a non-trivial construction which is surprisingly powerful. Several of its most important predictions have been confirmed rigorously through alternative approaches. This chapter gives a compact account of the replica method. It describes the close connection between replica symmetry breaking and the Poisson–Dirichlet process, and it emphasizes the role played by ‘overlaps’ between replicas.Less
In the past twenty-five years, the replica method has evolved into a rather sophisticated tool for attacking theoretical problems as diverse as spin glasses, protein folding, vortices in superconductors, combinatorial optimization, etc. Although it is not be the main tool of this book, it is nevertheless instructive to have some knowledge of replicas: the replica method is a non-trivial construction which is surprisingly powerful. Several of its most important predictions have been confirmed rigorously through alternative approaches. This chapter gives a compact account of the replica method. It describes the close connection between replica symmetry breaking and the Poisson–Dirichlet process, and it emphasizes the role played by ‘overlaps’ between replicas.
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.
Alasdair Urquhart
- Published in print:
- 2008
- Published Online:
- February 2010
- ISBN:
- 9780199296453
- eISBN:
- 9780191711961
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199296453.003.0017
- Subject:
- Philosophy, Logic/Philosophy of Mathematics
The main topic of this chapter is the problem posed to the mathematical community by the non-rigorous methods used by physicists in investigating mathematical problems. These methods are often highly ...
More
The main topic of this chapter is the problem posed to the mathematical community by the non-rigorous methods used by physicists in investigating mathematical problems. These methods are often highly successful in finding concrete results, but cannot be justified by standard methods. The chapter illustrates methods used by mathematicians in assimilating such non-rigorous techniques by reference to areas such as the umbral calculus of Blissard, Dirac's delta function, and the use of infinitesimals in calculus. It concludes with an example of an area where assimilation is currently incomplete, the replica method in statistical physics.Less
The main topic of this chapter is the problem posed to the mathematical community by the non-rigorous methods used by physicists in investigating mathematical problems. These methods are often highly successful in finding concrete results, but cannot be justified by standard methods. The chapter illustrates methods used by mathematicians in assimilating such non-rigorous techniques by reference to areas such as the umbral calculus of Blissard, Dirac's delta function, and the use of infinitesimals in calculus. It concludes with an example of an area where assimilation is currently incomplete, the replica method in statistical physics.
Hidetoshi Nishimori and Gerardo Ortiz
- Published in print:
- 2010
- Published Online:
- January 2011
- ISBN:
- 9780199577224
- eISBN:
- 9780191722943
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199577224.003.0008
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Real materials always contain randomness or disorder that cannot be expressed by idealized simple model systems. The present chapter studies the effects of randomness on phase transitions and ...
More
Real materials always contain randomness or disorder that cannot be expressed by idealized simple model systems. The present chapter studies the effects of randomness on phase transitions and critical phenomena. Although randomness may seem to obscure singular behaviour such as divergence of physical quantities at the critical temperature, it is established that well-defined phase transitions exist as long as randomness is not too strong, but the critical behaviour may get modified with respect to the pure sample. After the introduction of basic concepts and methods such as self-averaging and replica method, it is elucidated what type of phase transitions exist in the random-field Ising model and the SK model of spin glasses. Also explained are the percolation transitions using the fractal structure and the Potts model.Less
Real materials always contain randomness or disorder that cannot be expressed by idealized simple model systems. The present chapter studies the effects of randomness on phase transitions and critical phenomena. Although randomness may seem to obscure singular behaviour such as divergence of physical quantities at the critical temperature, it is established that well-defined phase transitions exist as long as randomness is not too strong, but the critical behaviour may get modified with respect to the pure sample. After the introduction of basic concepts and methods such as self-averaging and replica method, it is elucidated what type of phase transitions exist in the random-field Ising model and the SK model of spin glasses. Also explained are the percolation transitions using the fractal structure and the Potts model.
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.0002
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter discusses the problem of spin glasses. If the interactions between spins are not uniform in space, the analysis of the previous chapter does not apply. In particular, when the ...
More
This chapter discusses the problem of spin glasses. If the interactions between spins are not uniform in space, the analysis of the previous chapter does not apply. In particular, when the interactions are ferromagnetic for some bonds and antiferromagnetic for others, the spin orientation cannot be uniform in space, unlike the ferromagnetic system. Under such a circumstance it sometimes happens that spins become randomly frozen — random in space but frozen in time. This is the intuitive picture of the spin glass phase. The chapter investigates the condition for the existence of the spin glass phase as an extension of the mean-field theory. In particular, the properties of the so-called replica-symmetric solution are explained in detail for the Sherrington–Kirkpatrick (SK) model.Less
This chapter discusses the problem of spin glasses. If the interactions between spins are not uniform in space, the analysis of the previous chapter does not apply. In particular, when the interactions are ferromagnetic for some bonds and antiferromagnetic for others, the spin orientation cannot be uniform in space, unlike the ferromagnetic system. Under such a circumstance it sometimes happens that spins become randomly frozen — random in space but frozen in time. This is the intuitive picture of the spin glass phase. The chapter investigates the condition for the existence of the spin glass phase as an extension of the mean-field theory. In particular, the properties of the so-called replica-symmetric solution are explained in detail for the Sherrington–Kirkpatrick (SK) model.
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.
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.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics ...
More
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.Less
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.
Giorgio Parisi
- Published in print:
- 2015
- Published Online:
- March 2016
- ISBN:
- 9780198743736
- eISBN:
- 9780191803802
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198743736.003.0003
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter starts with an introduction to the replica method, a standard method in statistical physics, along with a concrete application to the computation of the eigenvalue distribution of random ...
More
This chapter starts with an introduction to the replica method, a standard method in statistical physics, along with a concrete application to the computation of the eigenvalue distribution of random matrices in the Gaussian orthogonal ensemble. The solution of the Sherrington–Kirkpatrick (SK) disordered spin-glass model is then derived, along with the phenomenon of replica symmetry breaking (RSB). The physical meaning of the RSB is explained. The ultrametricity of the space of pure states emerges as a consequence of the hierarchical RSB scheme. Moreover, it is shown how some low-temperature properties of physical observables can be derived by invoking the stochastic stability principle. Some rigorous results on the SK model are described: the existence of the thermodynamic limit, and the proof of the exactness of the hierarchical RSB solution.Less
This chapter starts with an introduction to the replica method, a standard method in statistical physics, along with a concrete application to the computation of the eigenvalue distribution of random matrices in the Gaussian orthogonal ensemble. The solution of the Sherrington–Kirkpatrick (SK) disordered spin-glass model is then derived, along with the phenomenon of replica symmetry breaking (RSB). The physical meaning of the RSB is explained. The ultrametricity of the space of pure states emerges as a consequence of the hierarchical RSB scheme. Moreover, it is shown how some low-temperature properties of physical observables can be derived by invoking the stochastic stability principle. Some rigorous results on the SK model are described: the existence of the thermodynamic limit, and the proof of the exactness of the hierarchical RSB solution.
František Slanina
- Published in print:
- 2013
- Published Online:
- January 2014
- ISBN:
- 9780199299683
- eISBN:
- 9780191747038
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199299683.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
In this chapter we present the minority game, which is one of the keystone models of econophysics. It is the mathematic implementation of the idea of inductive, rather than deductive, thinking. ...
More
In this chapter we present the minority game, which is one of the keystone models of econophysics. It is the mathematic implementation of the idea of inductive, rather than deductive, thinking. First, we explain how the agents adapt to each other, and how the efficiency of the system as a whole is increased by such an adaptation. Then the properties of the phase transition from efficient but non-ergodic to inefficient ergodic phase is discussed. In the following the replica formalism is introduced, and the full replica solution of the thermal batch minority game is shown. Finally, it is shown what modifications make the minority game useful as a model for stock-market fluctuations.Less
In this chapter we present the minority game, which is one of the keystone models of econophysics. It is the mathematic implementation of the idea of inductive, rather than deductive, thinking. First, we explain how the agents adapt to each other, and how the efficiency of the system as a whole is increased by such an adaptation. Then the properties of the phase transition from efficient but non-ergodic to inefficient ergodic phase is discussed. In the following the replica formalism is introduced, and the full replica solution of the thermal batch minority game is shown. Finally, it is shown what modifications make the minority game useful as a model for stock-market fluctuations.
Marc Mézard
- Published in print:
- 2015
- Published Online:
- March 2016
- ISBN:
- 9780198743736
- eISBN:
- 9780191803802
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198743736.003.0004
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica ...
More
The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.Less
The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.
Florent Krzakala, Federico Ricci-Tersenghi, Lenka Zdeborova, Riccardo Zecchina, Eric W. Tramel, and Leticia F. Cugliandolo (eds)
- Published in print:
- 2015
- Published Online:
- March 2016
- ISBN:
- 9780198743736
- eISBN:
- 9780191803802
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198743736.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book contains a collection of the presentations that were given in October 2013 at the Les Houches Autumn School on statistical physics, optimization, inference, and message-passing algorithms. ...
More
This book contains a collection of the presentations that were given in October 2013 at the Les Houches Autumn School on statistical physics, optimization, inference, and message-passing algorithms. In the last decade, there has been increasing convergence of interest and methods between theoretical physics and fields as diverse as probability, machine learning, optimization, and inference problems. In particular, much theoretical and applied work in statistical physics and computer science has relied on the use of message-passing algorithms and their connection to the statistical physics of glasses and spin glasses. For example, both the replica and cavity methods have led to recent advances in compressed sensing, sparse estimation, and random constraint satisfaction, to name a few. This book’s detailed pedagogical lectures on statistical inference, computational complexity, the replica and cavity methods, and belief propagation are aimed particularly at PhD students, post-docs, and young researchers desiring the foundational material necessary for entering this rapidly developing field. In these lectures the reader can find detailed applications of theory to problems in community detection and clustering, signal denoising, identification of hidden cliques, error correcting codes, and constraint satisfaction.Less
This book contains a collection of the presentations that were given in October 2013 at the Les Houches Autumn School on statistical physics, optimization, inference, and message-passing algorithms. In the last decade, there has been increasing convergence of interest and methods between theoretical physics and fields as diverse as probability, machine learning, optimization, and inference problems. In particular, much theoretical and applied work in statistical physics and computer science has relied on the use of message-passing algorithms and their connection to the statistical physics of glasses and spin glasses. For example, both the replica and cavity methods have led to recent advances in compressed sensing, sparse estimation, and random constraint satisfaction, to name a few. This book’s detailed pedagogical lectures on statistical inference, computational complexity, the replica and cavity methods, and belief propagation are aimed particularly at PhD students, post-docs, and young researchers desiring the foundational material necessary for entering this rapidly developing field. In these lectures the reader can find detailed applications of theory to problems in community detection and clustering, signal denoising, identification of hidden cliques, error correcting codes, and constraint satisfaction.
Lefteris M. Kirousis and Lefteris M. Stamatiou
- Published in print:
- 2005
- Published Online:
- November 2020
- ISBN:
- 9780195177374
- eISBN:
- 9780197562260
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780195177374.003.0015
- Subject:
- Computer Science, Mathematical Theory of Computation
One of the most challenging problems in probability and complexity theory is to establish and determine the satisfiability threshold, or phase transition, for random 3-SAT instances: Boolean ...
More
One of the most challenging problems in probability and complexity theory is to establish and determine the satisfiability threshold, or phase transition, for random 3-SAT instances: Boolean formulas consisting of clauses with exactly k literals. As the previous part of the volume has explored, empirical observations suggest that there exists a critical ratio of the number of clauses to the number of variables, such that almost all randomly generated formulas with a higher ratio are unsatisfiable while almost all randomly generated formulas with a lower ratio are satisfiable. The statement that such a crossover point really exists is called the satisfiability threshold conjecture. Experiments hint at such a direction, but as far as theoretical work is concerned, progress has been difficult. In an important advance, Friedgut [177] showed that the phase transition is a sharp one, though without proving that it takes place at a “fixed” ratio for large formulas. Otherwise, rigorous proofs have focused on providing successively better upper and lower bounds for the value of the (conjectured) threshold. In this chapter, our goal is to review the series of improvements of upper bounds for 3-SAT and the techniques leading to these. We give only a passing reference to the improvements of the lower bounds as they rely on significantly different techniques, one of which is discussed in the next chapter. Let ϕ be a random k-SAT formula constructed by selecting, uniformly and with replacement, ra clauses from the set of all possible clauses with k literals (no variable repetitions allowed within a clause) over n variables. It has been experimentally observed that as the numbers m, n of variables and clauses tend to infinity while the ratio or clause density m/n is fixed to a constant a, the property of satisfiability exhibits a phase transition. For the case of 3-SAT, when a is greater than a number that has been experimentally determined to be approximately α < 4.27, then almost all random 3-SAT formulas are unsatisfiable; that is, the fraction of unsatisfiable formulas tends to 1.
Less
One of the most challenging problems in probability and complexity theory is to establish and determine the satisfiability threshold, or phase transition, for random 3-SAT instances: Boolean formulas consisting of clauses with exactly k literals. As the previous part of the volume has explored, empirical observations suggest that there exists a critical ratio of the number of clauses to the number of variables, such that almost all randomly generated formulas with a higher ratio are unsatisfiable while almost all randomly generated formulas with a lower ratio are satisfiable. The statement that such a crossover point really exists is called the satisfiability threshold conjecture. Experiments hint at such a direction, but as far as theoretical work is concerned, progress has been difficult. In an important advance, Friedgut [177] showed that the phase transition is a sharp one, though without proving that it takes place at a “fixed” ratio for large formulas. Otherwise, rigorous proofs have focused on providing successively better upper and lower bounds for the value of the (conjectured) threshold. In this chapter, our goal is to review the series of improvements of upper bounds for 3-SAT and the techniques leading to these. We give only a passing reference to the improvements of the lower bounds as they rely on significantly different techniques, one of which is discussed in the next chapter. Let ϕ be a random k-SAT formula constructed by selecting, uniformly and with replacement, ra clauses from the set of all possible clauses with k literals (no variable repetitions allowed within a clause) over n variables. It has been experimentally observed that as the numbers m, n of variables and clauses tend to infinity while the ratio or clause density m/n is fixed to a constant a, the property of satisfiability exhibits a phase transition. For the case of 3-SAT, when a is greater than a number that has been experimentally determined to be approximately α < 4.27, then almost all random 3-SAT formulas are unsatisfiable; that is, the fraction of unsatisfiable formulas tends to 1.