Presently, both our best algorithm for random instances of the
satisfiability problem - namely survey propagation - and our most
sophisticated guess for the location of the satisfiability threshold are
obtained from the theory of spin glasses in statistical physics.
However, converting this theory into rigorous statements is a major
challenge for modern mathematics.

I will describe a combinatorial approach for interpreting the physical
picture of random SAT. There is a distribution on partial assignments
such that applying the well-known belief propagation algorithm to it
results in an algorithm identical to survey propagation. This
distribution captures some connectivity properties of the space of
solutions of typical satisfiability formulas. The structure of the space
of solutions is also studied in the context of general Boolean
constraint satisfaction problems.