Typical random 3-SAT formulae and the satisfiability threshold
<|reference_start|>Typical random 3-SAT formulae and the satisfiability threshold: We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.<|reference_end|>
@article{dubois2002typical,
    title={Typical random 3-SAT formulae and the satisfiability threshold},
    author={Olivier Dubois, Yacine Boufkhad, Jacques Mandler},
    journal={arXiv preprint arXiv:cs/0211036},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0211036},
    primaryClass={cs.DM cs.CC}
}