LCS Publication Details
Publication Title: The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
Publication Author: Hajiaghayi, MohammadTaghi
Additional Authors: Gregory B. Sorkin
LCS Document Number: MIT-LCS-TR-929
Publication Date: 11-20-2003
LCS Group: Theory of Computation
Additional URL:
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.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.