The Library
A better algorithm for random kSAT
Tools
CojaOghlan, Amin. (2010) A better algorithm for random kSAT. SIAM Journal on Computing, Volume 39 (Number 7). pp. 28232864. ISSN 00975397

PDF
WRAP_CojaOghlan_ksat.pdf  Published Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (647Kb)  Preview 
Official URL: http://dx.doi.org/10.1137/09076516X
Abstract
Let Φ be a uniformly distributed random kSAT formula with n variables and m clauses. We present a polynomial time algorithm that ﬁnds a satisfying assignment of Φ with high probability for constraint densities m/n < (1 − εk)2k ln(k)/k, where εk → 0. Previously no eﬃcient algorithm was known to ﬁnd 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:  00975397  
Official Date:  5 May 2010  
Dates: 


Volume:  Volume 39  
Number:  Number 7  
Number of Pages:  42  
Page Range:  pp. 28232864  
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)  
References:  [1] D. Achlioptas, P. Beame, and M. Molloy, Exponential bounds for DPLL below the satisﬁability 

URI:  http://wrap.warwick.ac.uk/id/eprint/5351 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 