A new look at survey propagation and its generalizations
A new look at survey propagation and its generalizations
This article provides a new conceptual perspective on survey propagation , which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k -SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be …