Published by the Department of Computer Science, The University of Chicago.

Abstract

Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima that an instance of MAX-2-SAT can have. We give upper bounds in both the sparse and nonsparse case, where the sparse case means that there is a bound d on the average number of clauses involving any given variable. The bounds in the nonsparse case are tight up to polylogarithmic factors, while in the sparse case the bounds are tight up to a multiplicative factor in d for large d. Additionally, we generalize to the question of assignments which are maxima up to changing k > 1 variables simultaneously; in this case, we give explicit constructions with large (in a sense explained below) numbers of such maxima in the sparse case. The basic idea of the upper bound proof is to consider a random assignment to some subset of the variables and determine the probability that some fraction of the remaining variables can be fixed without considering interactions between them. The bounded results hold in the case of weighted MAX-2-SAT as well. Using this technique and combining with ideas from [Golovnev and Kutzkov], we find an algorithm for weighted MAX-2-SAT which is faster for large d than previous algorithms which use polynomial space; this algorithm does require additional bounds on maximum weights and degree.

• The article: PDF (257 KB)
• Source material: ZIP (90 KB)
• BibTeX entry for this article (275 bytes)

Submitted March 8, 2017, revised April 28, 2017, published June 19, 2018.

© 2018 Matthew B. Hastings
Licensed under a Creative Commons Attribution License

Volume 2018, Article 1

Article 3

Volume 2018

Published articles