Coja-Oghlan, Amin and Pachon-Pinzon, Angelica Y. (2011) The decimation process in random k-SAT. Lecture Notes in Computer Science, Vol.6755 (Automata, Languages and Programming) . pp. 305-316. doi:10.1007/978-3-642-22006-7_26 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 k be an even integer. We investigate the applicability of approximation techniques to the problem of deciding whether a random k-SAT formula is satisfiable. Let n be the number of propositional variables under consideration. First we show that if the number m of clauses satisfies m≥ Cn k/2 for a certain constant C, then unsatisfiability can be certified efficiently using (known) approximation algorithms for MAX CUT or MIN BISECTION. In addition, we present an algorithm based on the Lovász ϑ function that within polynomial expected time decides whether the input formula is satisfiable, provided m≥ Cn k/2. These results improve previous work by Goerdt and Krivelevich [14]. Finally, we present an algorithm that approximates random MAX 2-SAT within expected polynomial time.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISSN:	0302-9743
Book Title:	Automata, Languages and Programming
Official Date:	2011
Dates:	Date Event 2011 Published
Volume:	Vol.6755 (Automata, Languages and Programming)
Number of Pages:	12
Page Range:	pp. 305-316
DOI:	10.1007/978-3-642-22006-7_26
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item