#

### Volume 2018

#### Article 2.

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

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

Matthew B. Hastings

Station Q

Microsoft Research

Santa Barbara CA

`mahastin AT microsoft DOT com `

*June 19, 2018*
#### 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.

Volume 2018, Article 1
Article 3

Volume 2018
Published articles