Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems
<|reference_start|>Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems: We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy. We give a sufficient condition for the existence of a sharp threshold that leads (for boolean constraints) to a necessary and sufficient for the existence of a sharp threshold in the case where constraint templates are applied with equal probability, solving thus an open problem of Creignou and Daude.<|reference_end|>
@article{istrate2005coarse,
    title={Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems},
    author={Gabriel Istrate},
    journal={arXiv preprint arXiv:cs/0503083},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0503083},
    primaryClass={cs.DM cs.CC}
}