| 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: |
|
| Abstract: |
| 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.
|