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…