We consider applications of belief propagation algorithms to Boolean constraint satisfaction problems (CSPs), such as 3-SAT , when the instances are chosen from a natural distribution---the uniform distribution over formulas with prescribed ratio of the number of clauses to the number of variables. In particular, we show that survey propagation, which is the most effective heuristic for random 3-SAT problems with density of clauses close to the conjectured satisfiability threshold, is in fact a belief propagation algorithm. We define a parameterized distribution on partial assignments, and show that applying belief propagation to this distribution recovers a known family of algorithms ranging from survey propagation to standard belief propagation on the uniform distribution over satisfying assignments. We investigate the resulting lattice structure on partial assignments, and show how the new distributions can be viewed as a "smoothed" version of the uniform distribution over satisfying assignments, which is a first step towards explaining the superior performance of survey propagation over the naive application of belief propagation. Furthermore, we use this lattice structure to obtain a conditional improvement on the upper bound for the satisfiability threshold.; The design of survey propagation is associated with the structure of the solution space of random 3-SAT problems. In order to shed light on the structure of this space for the case of general Boolean CSPs we study it in Schaefer's framework. Schaefer's dichotomy theorem splits Boolean CSPs into polynomial time solvable and NP-complete problems. We show that with respect to some structural properties such as the diameter of the solutions space and the hardness of deciding its connectivity, there are two kinds of Boolean CSPs, but the boundary of the new dichotomy differs significantly from Schaefer's.; Finally, we present an application of a method developed in this thesis to the source-coding problem. We use the dual of good low-density parity check codes. For the compression step we define an appropriate distribution on partial assignments and apply belief propagation to it, using the same technique that was developed to derive survey propagation as a belief propagation algorithm. We give experimental evidence that this method yields performance very close to the rate distortion limit.
展开▼
