Coja-Oghlan, Amin (2009) A better algorithm for random k-SAT. In: 36th International Colloquium, ICALP 2009, Rhodes, Greece, 5-12 Jul 2009. Published in: Automata, Languages and Programming, Vol.5555 pp. 292-303. ISBN 9783642029264. doi:10.1007/978-3-642-02927-1_25 ISSN 0302-9743.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

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 mn(1−k)2kln(k)k , where ε k →0. Previously no efficient algorithm was known to find solutions with non-vanishing probability beyond m/n = 1.817·2 k /k [Frieze and Suen, Journal of Algorithms 1996].

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Series Name:	Lecture Notes in Computer Science
Journal or Publication Title:	Automata, Languages and Programming
Publisher:	Springer
Place of Publication:	Berlin : Heidelberg
ISBN:	9783642029264
ISSN:	0302-9743
Book Title:	Automata, Languages and Programming
Official Date:	2009
Dates:	Date Event 2009 Published
Volume:	Vol.5555
Page Range:	pp. 292-303
DOI:	10.1007/978-3-642-02927-1_25
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	36th International Colloquium, ICALP 2009
Type of Event:	Conference
Location of Event:	Rhodes, Greece
Date(s) of Event:	5-12 Jul 2009

Request changes or add full text files to a record

Repository staff actions (login required)

View Item