The Satisfiability Threshold of Random 3-SAT Is at Least 352
<|reference_start|>The Satisfiability Threshold of Random 3-SAT Is at Least 352: We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and sets) a variable depending on its degree and that of its complement.<|reference_end|>
@article{hajiaghayi2003the,
    title={The Satisfiability Threshold of Random 3-SAT Is at Least 3.52},
    author={MohammadTaghi Hajiaghayi and Gregory B. Sorkin},
    journal={arXiv preprint arXiv:math/0310193},
    year={2003},
    archivePrefix={arXiv},
    eprint={math/0310193},
    primaryClass={math.CO cs.DM math.PR}
}