On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas

Elitza Maneva, Alistair Sinclair

We study the structure of satisfying assignments of a random 3-SAT formula. In particular, we show that a random formula of density 4.453 or higher almost surely has no non-trivial…