Survey Propagation Inspired Algorithms for Satisfiability

In this note we develop generalized Survey Propagation (SP) equations from the cavity method. We quantize the message space of the messages to develop a message passing rule. We investigate a framework of greedy algorithms for finding out satisfying assignment inspired by the new SP rule. We show that the recent Hajiaghayi-Sorkin algorithm for satisfiability is a special case in this framework of algorithms and the lower bound on the conjectured threshold given by the Hajiaghayi-Sorkin algorithm can be improved. This improvement is shown by experiments.