
The Library
A better algorithm for random k-SAT
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 ISSN 0097-5397.
|
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, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > 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 | ||||
Date of first compliant deposit: | 3 December 2015 | ||||
Date of first compliant Open Access: | 3 December 2015 | ||||
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