Susceptibility Propagation for Constraint Satisfaction Problems

Abstract

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.

17 pages, 5 figures

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard

Cited by in corpus (4)

• Mechanisms of dimensionality reduction and decorrelation in deep neural networks
• Counting solutions from finite samplings
• Message passing algorithms for the Hopfield network reconstruction: threshold behavior and limitation
• Satisfiability Thresholds for Regular Occupation Problems