Belief and Survey Propagation

At the turn of the millennium new message passing algorithms called Belief and Survey Propagation stirred excitement in the SAT community because these algorithms appeared to excel at solving large random k-SAT instances. In this talk I will give an overview of where we stand as far as a mathematical understanding of these message passing algorithms goes. In addition, I will discuss th physics intuition that underpins Belief and Survey Propagation.