658 citations · 2.2k across the 187 of their papers we have counts for
3 papers · 2 filters
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…
Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window
Nayantara Bhatnagar, Nick Crawford, Elchanan Mossel +1
We study the structure of a uniformly randomly chosen partial order of width 2 on n elements. We show that under the appropriate scaling, the number of incomparable elements conver…
Branching Process approach for 2-SAT thresholds
Elchanan Mossel, Arnab Sen
It is well known that, as tends to infinity, the probability of satisfiability for a random 2-SAT formula on variables, where each clause occurs independently with probabil…