Lifted message passing for satisfiability

Unifying logical and probabilistic reasoning is a longstanding goal of AI. While recent work in lifted belief propagation, handling whole sets of indistinguishable objects together, are promising steps towards achieving this goal that even scale to realistic domains, they are not tailored towards solving combinatorial problems such as determining the satisfiability of Boolean formulas. Recent results, however, show that certain other message passing algorithms, namely, survey propagation, are remarkably successful at solving such problems. In this paper, we propose the first lifted variants of survey propagation and its simpler version warning propagation. Our initial experimental results indicate that they are faster than using lifted belief propagation to determine the satisfiability of Boolean formulas.