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, Volume 39 (Number 7). pp. 2823-2864. doi:10.1137/09076516X
|
PDF
WRAP_Coja-Oghlan_ksat.pdf - Published Version - Requires a PDF viewer. Download (647Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/09076516X
Abstract
Let Φ 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 Φ with high probability for constraint densities m/n < (1 − εk)2k ln(k)/k, where εk → 0. Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond m/n = 1.817 · 2k/k [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312–355].
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Computer Science Faculty of Science > Mathematics |
||||
| Library of Congress Subject Headings (LCSH): | Algebra, Boolean, Computer science -- Mathematics | ||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||
| ISSN: | 0097-5397 | ||||
| Official Date: | 5 May 2010 | ||||
| Dates: |
|
||||
| Volume: | Volume 39 | ||||
| Number: | Number 7 | ||||
| Number of Pages: | 42 | ||||
| Page Range: | pp. 2823-2864 | ||||
| DOI: | 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) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
