On Generalized Survey Propagation: Normal Realization and Sum-Product Interpretation

A celebrated algorithmic discovery in solving constraint satisfaction problems, survey propagation (SP) and its generalization have recently demonstrated their power in areas of communications and data compression. It is known that under certain Markov random field (MRF) formalism of k-SAT problems, SP may be interpreted as an instance of belief propagation (BP). In this paper, we borrow the notion of generalized states from system theory and coding theory, and introduce a new MRF formalism - normal realization - for k-SAT problems. We show that when BP applies to this MRF, generalized SP is resulted. This new MRF formalism appears to be simpler than the existing one and the interpretation of SP as BP in this framework also appears more transparent