2 papers
math.CO2008
On the random satisfiable process
Michael Krivelevich, Benny Sudakov, Dan Vilenchik
In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas -- randomly permute all 2^k\binom{n}{k} possible clauses over the va…
math.CO2007★ 1 cited
Message passing for the coloring problem: Gallager meets Alon and Kahale
Sonny Ben-Shimon, Dan Vilenchik
Message passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that {\em survey propagation} (a certain message passing…