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.

Video Recording