Cavity Method
   HOME

TheInfoList



OR:

The cavity method is a mathematical method presented by Marc Mézard,
Giorgio Parisi Giorgio Parisi (born 4 August 1948) is an Italian theoretical physicist, whose research has focused on quantum field theory, statistical mechanics and complex systems. His best known contributions are the QCD evolution equations for parton den ...
and Miguel Angel Virasoro in 1987 to solve some mean field type models in
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxi ...
, specially adapted to disordered systems. The method has been used to compute properties of ground states in many
condensed matter Condensed matter physics is the field of physics that deals with the macroscopic and microscopic physical properties of matter, especially the solid and liquid phases which arise from electromagnetic forces between atoms. More generally, the sub ...
and
optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...
s. Initially invented to deal with the Sherrington–Kirkpatrick model of
spin glass In condensed matter physics, a spin glass is a magnetic state characterized by randomness, besides cooperative behavior in freezing of spins at a temperature called 'freezing temperature' ''Tf''. In ferromagnetic solids, component atoms' magn ...
es, the cavity method has shown wider applicability. It can be regarded as a generalization of the BethePeierls iterative method in tree-like graphs, to the case of a graph with loops that are not too short. The different approximations that can be done with the cavity method are usually named after their equivalent with the different steps of the replica method which is mathematically more subtle and less intuitive than the cavity approach. The cavity method has proved useful in the solution of
optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...
s such as k-satisfiability and
graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
. It has yielded not only ground states energy predictions in the average case, but also has inspired algorithmic methods.


See also

The cavity method originated in the context of
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxi ...
, but is also closely related to methods from other areas such as
belief propagation A belief is an attitude that something is the case, or that some proposition is true. In epistemology, philosophers use the term "belief" to refer to attitudes about the world which can be either true or false. To believe something is to take i ...
.


References


Further reading

* * * * * Condensed matter physics {{CMP-stub