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.

Preview

PDF WRAP_Coja-Oghlan_ksat.pdf - Published Version - Requires a PDF viewer. Download (647Kb) | Preview

Request Changes to record.

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:	Date Event 5 May 2010 Published
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