%0 Journal Article
%T Susceptibility Propagation for Constraint Satisfaction Problems
%A Saburo Higuchi
%A Marc M¨¦zard
%J Mathematics
%D 2009
%I arXiv
%R 10.1088/1742-6596/233/1/012003
%X We study the susceptibility propagation, a message-passing algorithm to compute correlation functions. It is applied to constraint satisfaction problems and its accuracy is examined. As a heuristic method to find a satisfying assignment, we propose susceptibility-guided decimation where correlations among the variables play an important role. We apply this novel decimation to locked occupation problems, a class of hard constraint satisfaction problems exhibited recently. It is shown that the present method performs better than the standard belief-guided decimation.
%U http://arxiv.org/abs/0903.1621v1