The Library
On smoothed k-CNF formulas and the Walksat algorithm
Tools
Tools
Tools
Coja-Oghlan, Amin, Feige, Uriel, Frieze, Alan, Krivelevich, Michael and Vilenchik, Dan (2009) On smoothed k-CNF formulas and the Walksat algorithm. In: SODA08 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 20-22 Jan 2008. Published in: SODA '09 Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 451-460.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
In this paper we study the model of ε-smoothed k-CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ε-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ε. Keeping ε and k fixed, and letting the density d = m/n grow, it is rather easy to see that for d ≥ ε-k ln 2, F becomes whp unsatisfiable after smoothing.
We show that a lower density that behaves roughly like ε-k+1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k-CNF formulas F of slightly lower density that whp remain satisfiable after smoothing.
One consequence of our proof is a new lower bound of Ω(2k/k2) on the density up to which Walksat solves random k-CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Alternative Title: | |||||
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | SODA '09 Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Publisher: | SIAM | ||||
| Official Date: | 2009 | ||||
| Dates: |
|
||||
| Page Range: | pp. 451-460 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | SODA08 19th ACM-SIAM Symposium on Discrete Algorithms | ||||
| Type of Event: | Conference | ||||
| Location of Event: | San Francisco, CA, USA | ||||
| Date(s) of Event: | 20-22 Jan 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
