The Library
A better algorithm for random k-SAT
Tools
Tools
Tools
Coja-Oghlan, Amin. (2010) A better algorithm for random k-SAT. SIAM Journal on Computing, Vol.39 (No.7). pp. 2823-2864. ISSN 0097-5397
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/09076516X
Abstract
Let Phi be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of Phi with high probability for constraint densities m/n < (1 - epsilon(k))2(k) ln(k)/k, where epsilon(k) -> 0. Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond m/n = 1.817 . 2(k)/k [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312-355].
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Computer Science Faculty of Science > Mathematics |
| Journal or Publication Title: | SIAM Journal on Computing |
| Publisher: | Society for Industrial and Applied Mathematics |
| ISSN: | 0097-5397 |
| Date: | 2010 |
| Volume: | Vol.39 |
| Number: | No.7 |
| Number of Pages: | 42 |
| Page Range: | pp. 2823-2864 |
| Identification Number: | 10.1137/09076516X |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Funder: | Engineering and Physical Sciences Research Council (EPSRC) |
| Grant number: | EP/G039070/1 (EPSRC) |
| URI: | http://wrap.warwick.ac.uk/id/eprint/5351 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
