Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-163 | 25th October 2016 02:26

Local Maxima and Improved Exact Algorithm for MAX-2-SAT


Authors: Matthew Hastings
Publication: 28th October 2016 13:08
Downloads: 1099


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 hat 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 imultaneously; 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 Ref. 6, 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 an additional bounds on maximum weights and degree.

ISSN 1433-8092 | Imprint