Cavity method

The cavity method is a mathematical method presented by <a href="/facts/Marc_M%25C3%25A9zard/PBt3qwva">Marc Mézard</a>, <a href="/facts/Giorgio_Parisi/TnJWYAbe">Giorgio Parisi</a> and <a href="/facts/Miguel_%25C3%2581ngel_Virasoro_(physicist)/zhmWnqLo">Miguel Angel Virasoro</a> in 1987 to derive and solve some <a href="/facts/Mean_field/tJrwSURE">mean field</a>-type models in <a href="/facts/Statistical_physics/SnlJE78a">statistical physics</a>, specially adapted to disordered systems. The method has been used to compute properties of <a href="/facts/Ground_state/ML7cfCug">ground states</a> in many <a href="/facts/Condensed_matter/EBVI5nmL">condensed matter</a> and <a href="/facts/Optimization_problem/QzwJfFEE">optimization problems</a>.
Initially invented to deal with the <a href="/facts/Sherrington%25E2%2580%2593Kirkpatrick_model/v2Cxng9Y">Sherrington–Kirkpatrick model</a> of <a href="/facts/Spin_glass/v2Cxng9Y">spin glasses</a>, the cavity method has shown wider applicability. It can be regarded as a generalization of the <a href="/facts/Hans_Bethe/X6bkxRRI">Bethe</a>–<a href="/facts/Rudolf_Peierls/La4r1ISU">Peierls</a> iterative method in tree-like graphs, to the case of a graph with loops that are not too short. The cavity method can solve many problems also solvable using the <a href="/facts/Replica_trick/Mb25QdlA">replica trick</a> but has the advantage of being more intuitive and less mathematically subtle than replica-based methods.
The cavity method proceeds by perturbing a large system with the addition of a non-thermodynamic number of additional constituents and approximating the response of the entire system <a href="/facts/Perturbation_theory/JWrNgbVm">perturbatively</a>. The application of the resulting approximation, along with an assumption that certain observables are <a href="/facts/Self-averaging/RpTdKvTR">self-averaging</a>, yields a self-consistency equation for the statistics of the added constituents. The added constituents are then considered to be the mean-field variables.
The cavity method has proved useful in solving <a href="/facts/Optimization_problem/QzwJfFEE">optimization problems</a> such as <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">k-satisfiability</a> and <a href="/facts/Graph_coloring/J6HoBfP0">graph coloring</a>. It has yielded not only ground states energy predictions in the average case but has also inspired algorithmic methods.

Cavity method open-in-new

Cavity method