48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) Refuting Smoothed 3CNF Formulas Providence, Rhode Island October 21-October 23 ISBN: 0-7695-3010-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.16
We introduce the following model for generating semirandom 3CNF formulas. First, an adversary is allowed to pick an arbitrary formula with n variables and m clauses. Then, the formula is slightly perturbed at random. Namely, the smoothing operation leaves the variables of the formula unchanged, but flips the polarity of every variable occurrence in the formula independently with probability \varepsilon . If the density m/n of a 3CNF formula exceeds a certain threshold value (say, 5 \in ^{ - 3} then the smoothing operation almost surely results in a non-satisfiable formula. We present a randomized polynomial time refutation algorithm that for every sufficiently dense 3CNF formula manages to refute most of its smoothed instantiations. The density requirement for our refutation algorithm is roughly \in ^{ - 2} \sqrt {n\log \log n}, which almost matches the density \Omega (\sqrt n ) required by known algorithms for refuting 3CNF formulas that are completely random.
Citation:
Uriel Feige, "Refuting Smoothed 3CNF Formulas," focs, pp.407-417, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||