Clustering of solutions in the random satisfiability problem
<|reference_start|>Clustering of solutions in the random satisfiability problem: Using elementary rigorous methods we prove the existence of a clustered phase in the random $K$-SAT problem, for $K\geq 8$. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.<|reference_end|>
@article{mezard2005clustering,
    title={Clustering of solutions in the random satisfiability problem},
    author={M. Mezard, T. Mora, R. Zecchina},
    journal={Phys. Rev. Lett. 94, 197205 (2005)},
    year={2005},
    doi={10.1103/PhysRevLett.94.197205},
    archivePrefix={arXiv},
    eprint={cond-mat/0504070},
    primaryClass={cond-mat.dis-nn cs.CC}
}