Convex geometries in k-SAT problems
Federico Ardila, Elitza Maneva · 2007
In analyzing the survey propagation algorithm, Maneva, Mossel, and Wainwright discovered a polynomial identity that holds for a Boolean formula F and a satisfying assignment a. We show that F and a give rise to a convex geometry, and that convex geometries are precisely the combinatorial objects satisfying (the multivariate analog of) that polynomial identity. 1