37 citations · 114 across the 19 of their papers we have counts for
Showing math.PRShow all
2 papers · 1 filter
math.PR2009
On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
Uriel Feige, Abraham D. Flaxman, Dan Vilenchik
It is known that random k-CNF formulas have a so-called satisfiability threshold at a density (namely, clause-variable ratio) of roughly 2^k\ln 2: at densities slightly below this…
math.PR2008
Complete convergence of message passing algorithms for some satisfiability problems
Uriel Feige, Elchanan Mossel, Dan Vilenchik
In this paper we analyze the performance of Warning Propagation, a popular message passing algorithm. We show that for 3CNF formulas drawn from a certain distribution over random s…