Authors Venkatesan Guruswami, Yuan Zhou,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267
www.theoryofcomputing.org
Tight Bounds on the Approximability of
Almost-Satisfiable Horn SAT and Exact
Hitting Set ∗
Venkatesan Guruswami† Yuan Zhou
Received: February 21, 2011; published: June 10, 2012.
Abstract: We study the approximability of two natural Boolean constraint satisfaction
problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we
prove the following optimal inapproximability and approximability results for finding an
assignment satisfying as many constraints as possible given a near-satisfiable instance.
1. Given an instance of Max Horn-3SAT that admits an assignment satisfying (1 − ε) of
its constraints for some small constant ε > 0, it is hard to find an assignment satisfying
more than 1 − 1/O(log(1/ε)) of the constraints. This matches a linear programming
based algorithm due to Zwick (STOC 1998), resolving the natural open question raised
in that work concerning the optimality of the approximation bound.
Given a (1 − ε)-satisfiable instance of Max Horn-2SAT for some constant ε > 0, it
is possible to find a (1 − 2ε)-satisfying assignment efficiently. This improves the
algorithm given in Khanna et al. (2000) which finds a (1 − 3ε)-satisfying assignment,
∗ A conference version of this paper was earlier published at the 22nd Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 2011).
† Supported in part by a Packard Fellowship, NSF CCF 0953155, and US-Israel BSF grant 2008293.
ACM Classification: G.1.6
AMS Classification: 90C59
Key words and phrases: approximation algorithms, hardness of approximation, Unique Games Conjec-
ture, Horn-SAT, exact hitting set
2012 Venkatesan Guruswami and Yuan Zhou
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2010.v008a011
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
and also matches the (1 − cε) hardness for any c < 2 derived from vertex cover (under
UGC).
2. An instance of Max 1-in-k-HS consists of a universe U and a collection C of subsets of
U of size at most k, and the goal is to find a subset of U that intersects the maximum
number of sets in C at a unique element. We prove that Max 1-in-k-HS is hard to
approximate within a factor of O(1/ log k) for every fixed integer k. This matches (up
to constant factors) an easy factor Ω(1/ log k) approximation algorithm for the problem,
and resolves a question posed in Guruswami and Trevisan (APPROX 2005).
It is crucial for the above hardness that sets of size up to k are allowed; indeed, when
all sets have size k, there is a simple factor 1/e-approximation algorithm.
Our hardness results are proved by constructing integrality gap instances for a semidefi-
nite programming relaxation for the problems, and using Raghavendra’s result (STOC 2008)
to conclude that no algorithm can do better than the SDP assuming the UGC. In contrast to
previous such constructions where the instances had a good SDP solution by design and the
main task was bounding the integral optimum, the challenge in our case is the construction of
appropriate SDP vectors and the integral optimum is easy to bound. Our algorithmic results
are based on rounding appropriate linear programming relaxations.
1 Introduction
Schaefer proved long ago that there are only three non-trivial classes of Boolean constraint satisfaction
problems (CSPs) for which satisfiability is polynomial time decidable [18]. These are LIN-mod-2 (linear
equations modulo 2), 2-SAT, and Horn-SAT. The maximization versions of these problems (where
the goal is to find an assignment satisfying the maximum number of constraints) are NP-hard, and in
fact APX-hard, i. e., NP-hard to approximate within some constant factor bounded away from 1. An
interesting special case of the maximization version is the following problem of “finding almost-satisfying
assignments”: Given an instance which is (1 − ε)-satisfiable (i. e., only ε fraction of constraints need
to be removed to make it satisfiable for some small constant ε), can one efficiently find an assignment
satisfying most (say, 1 − f (ε) − o(1) where f (ε) → 0 as ε → 0) of the constraints? 1
The problem of finding almost-satisfying assignments was first suggested and studied in a beautiful
paper by Zwick [19]. This problem seems well-motivated, as even if a Max CSP is APX-hard in general,
in certain practical situations instances might be close to being satisfiable (for example, a small fraction
of constraints might have been corrupted by noise). An algorithm that is able to satisfy most of the
constraints of such an instance could be very useful.
As pointed out in [12], Schaefer’s reductions together with the PCP theorem imply that the previous
goal is NP-hard to achieve for any Boolean CSP for which the satisfiability problem is NP-complete.
Indeed, all but the above three tractable cases of Boolean CSPs have a “gap at location 1,” which means
1 Throughout the paper, constraints could have weights, and by a “fraction α of constraints” we mean any subset of
constraints whose total weight is a fraction α of the sum of the weights of all constraints. For CSPs with no unary constraints,
the approximability of the weighted and unweighted versions are known to be the same [5].
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 240
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
that given a satisfiable instance it is NP-hard to find an assignment satisfying α fraction of the constraints
for some constant α < 1. This result has been extended to CSPs over arbitrary domains recently [11].
The natural question therefore is whether for the three tractable Boolean CSPs, LIN-mod-2, 2-SAT,
and Horn-SAT, one can find almost-satisfying assignments in polynomial time. Effectively, the question is
whether there are “robust” satisfiability checking algorithms that can handle a small number of inconsistent
constraints and still produce a near-satisfying assignment.
With respect to the feasibility of finding almost-satisfying assignments, LIN-mod-2, 2-SAT, and
Horn-SAT behave rather differently from each other. For LIN-mod-2, Håstad in his breakthrough paper [9]
showed that for any ε, δ > 0, finding a solution satisfying 1/2 + δ of the equations of a (1 − ε)-satisfiable
instance is NP-hard. In fact, this result holds even when each equation depends on only 3 variables. Since
just picking a random assignment satisfies 1/2 the constraints in expectation, this shows, in a very strong
sense, that there is no robust satisfiability algorithm for LIN-mod-2.
In sharp contrast to this extreme hardness for linear equations, Zwick [19] proved that for 2-SAT and
Horn-SAT one can find almost-satisfying assignments in polynomial time. For Max 2SAT, Zwick gave a
semidefinite programming (SDP) based algorithm that finds a (1 − O(ε 1/3 ))-satisfying assignment (i. e.,
an assignment satisfying a fraction (1 − O(ε 1/3 )) of the constraints) given √ as input a (1 − ε)-satisfiable
instance. This algorithm was later improved to one that √ finds a (1 − O( ε))-satisfying assignment by
Charikar, Makarychev, and Makarychev [4]. The 1 − O( ε) bound is known to be best possible under
the Unique Games conjecture (UGC) [13, 14]. In fact, this hardness result for Max 2SAT was the first
application of the UGC and one of the main initial motivations for its formulation by Khot [13].
For Max Horn-SAT, Zwick gave a linear programming (LP) based algorithm to find an assignment
satisfying 1 − O(log log(1/ε)/ log(1/ε)) of constraints of a (1 − ε)-satisfiable instance. Recall that an
instance of Horn-SAT is a CNF formula where each clause consists of at most one unnegated literal.2
Equivalently, each clause is of the form xi , xi , or xi ∧ x2 ∧ . . . ∧ xk → xk+1 for variables xi . For Max Horn-
3SAT, where each clause involves at most three variables, the algorithm finds a (1 − O(1/ log(1/ε)))-
satisfying assignment. Note that the fraction of unsatisfied constraints is exponentially worse for Max
Horn-SAT compared to Max 2SAT.
Horn-SAT is a fundamental problem in logic and artificial intelligence. Zwick’s robust Horn satisfia-
bility algorithm shows the feasibility of solving instances where a small number of constraints are faulty
and raises the following natural question, which was also explicitly raised in [19]. Is this 1/ log(1/ε)
deficit inherent? Or could a more sophisticated algorithm, say based on an SDP relaxation instead of
the LP relaxation used in [19], improve the deficit to something smaller (such as ε b for some constant b
as in the case of the SDP based algorithm for Max 2SAT)? It is known that for some absolute constant
c < 1, it is NP-hard to find a (1 − ε c )-satisfying assignment given a (1 − ε)-satisfiable instance of Max
Horn-SAT [12].
In this work, we address the above question and resolve it (conditioned on the UGC), showing the
1/ log(1/ε) deficit to be inherent. We also investigate another problem, the “exact hitting set” problem
for set sizes bounded by k, which has a very peculiar approximation behavior [8]. It admits a much better
approximation algorithm on satisfiable instances, as well as when sets all have size exactly (or close to) k.
We prove that these restrictions are inherent, and relaxing these rules out a constant factor approximation
2 The dual variant dual-Horn-SAT is an instance of SAT where each clause has at most one negated literal and it is also
polynomial time solvable.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 241
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
algorithm (again, under the UGC). We describe our results in more detail below in Section 2.
Remark 1.1. For (1 − ε)-satisfiable instances of Max 2-SAT, even the hardness of finding a (1 − ωε (1)ε)-
satisfying
√ assignment is not known without assuming the UGC (and the UGC implies the optimal
1 − Ω( ε) hardness bound). For Max Horn-SAT, as mentioned above, we know the NP-hardness of
finding a (1 − ε c )-satisfying assignment for some absolute constant c < 1. Under the UGC, we are able
to pin down the exact asymptotic dependence on ε.
2 Our results and previous work
2.1 Horn-SAT
We prove the following hardness result concerning finding almost-satisfying assignments for Max Horn-
SAT (in fact for the arity 3 case where all clauses involve at most 3 variables). In the sequel, we use the
terminology “UG-hard” to mean at least as hard as refuting the Unique Games conjecture.
Theorem 2.1. For some absolute constant C > 0, for every ε > 0, given a (1 − ε)-satisfiable instance of
Max Horn-3SAT, it is UG-hard to find an assignment satisfying more than a fraction 1 −C/log(1/ε) of
the constraints.
Zwick gave a polynomial time algorithm that finds a (1 − O(log(k)/ log(1/ε)))-satisfying assign-
ment on input a (1 − ε)-satisfiable instance of Max Horn-kSAT. Our inapproximability bound is there-
fore optimal up to the constant C, and resolves Zwick’s question on whether his algorithm can be
improved in the negative. (For arbitrary arity Horn-SAT, Zwick’s algorithm has the slightly worse
1 − O(log log(1/ε)/ log(1/ε)) performance ratio; we do not show this to be tight.)
Theorem 2.1 shows that Max Horn-SAT has a very different quantitative behavior compared to
Max 2SAT with respect to approximating near-satisfiable√ instances: the fraction of unsatisfied clauses
Ω(1/ log(1/ε)) is exponentially worse than the O( ε) fraction that can be achieved for Max 2SAT.
A strong hardness result for Min Horn Deletion, the minimization version for Horn-SAT, was shown
in [12]. It follows from their reduction that for some absolute constant c < 1, it is NP-hard to find a
(1−ε c )-satisfying assignment given a (1−ε)-satisfiable instance of Max Horn-SAT. The constant c would
be extremely close to 1 in this result as it is related to the soundness in Raz’s parallel repetition theorem.
While our inapproximability bound is stronger and optimal, we are only able to show UG-hardness and
not NP-hardness.
In light of our strong hardness result for Max Horn-3SAT, we also consider the approximability
of the arity two case. For Max Horn-2SAT, given a (1 − ε)-satisfiable instance, an approximation
preserving reduction from vertex cover shows that it is UG-hard to find a (1 − cε)-satisfying assignment
for c < 2. It is also shown in [12] that one can find a (1 − 3ε)-satisfying assignment efficiently. We
improve the algorithmic bound (to the matching UG-hardness) by proving the following theorem, based
on half-integrality of an LP relaxation for the problem.
Theorem 2.2. Given a (1 − ε)-satisfiable instance for Max Horn-2SAT, it is possible to find a (1 − 2ε)-
satisfying assignment in polynomial time.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 242
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
2.2 Exact hitting set
We consider the “exact hitting set” problem where the goal is to find a subset that intersects a maximum
number of sets from an input family at exactly one element. Formally,
Definition 2.3. Let k ⩾ 2 be a fixed integer. An instance of Max 1-in-k-HS consists of a universe
U = {x1 , x2 , . . . , xn } and a collection C of subsets of U each of size at most k. The objective is to find a
subset S ⊆ U that maximizes the number of sets T ∈ C for which |S ∩ T | = 1. When all sets in C have
size equal to k, we refer to the problem as Max 1-in-Ek-HS.
In addition to being a natural CSP, the exact hitting set problem arises in many contexts where one has
to make unique choices from certain specified subsets. The complexity of this problem was investigated
in [8] and [7], where applications of the problem to pricing, computing ad-hoc selective families for radio
broadcasting, etc. are also discussed.
Our interest in this problem stems in part from the following peculiar approximability behavior
of Max 1-in-k-HS, as pointed out in [8]. The Max 1-in-k-HS problem appears to be much easier to
approximate on “satisfiable instances” (where a hitting set intersecting all subsets exactly once exists)
or when all sets have size exactly equal to k (instead of at most k). In both these cases, there is a factor
1/e-approximation algorithm, and obtaining a (1/e + ε)-approximation is NP-hard even when both
restrictions hold simultaneously [8].
For Max 1-in-k-HS itself, the best approximation factor known to be possible in polynomial time
is Ω(1/ log k). This is based on partitioning the collection C into O(log k) parts based on geometric
intervals [2i , 2i+1 ) of set sizes, and running a simple randomized algorithm (that handles the case where
all sets have sizes within a factor of two) on the sub-collection which has the most sets. Despite the
simplicity and seeming naiveness of this algorithm, no factor ω(1/ log k) algorithm is known for the
problem. No hardness factor better than the 1/e bound (which holds even for Max 1-in-Ek-HS) is known
either. Improving the gap in our understanding of the approximability of Max 1-in-k-HS was posed as an
open question in [8].
For the case when k is not fixed but can also grow with the universe size n, a factor (log n)−Ω(1)
γ
hardness was shown in [7], under the assumption NP 6⊆ TIME(2n ) for some γ > 0. However, their
method does not seem to be applicable to the case of bounded set size.
In this work, we prove the following tight result, establishing the difficulty of improving the simple
Ω(1/ log k)-approximation algorithm. This shows that it is hard to simultaneously do well on many
different “scales” of set sizes. (If all set sizes are almost the same, then there is a constant factor
approximation algorithm.)
Theorem 2.4. For some absolute constant C0 > 0, for every α > 0, given a (1 − 1/k1−α )-satisfiable
instance of Max 1-in-k-HS, it is UG-hard to find a subset intersecting more than a fraction C0 /(α log k)
of the sets exactly once.
The gap in the above hardness result is also located at the “correct” satisfiability threshold, as we
show the following complementary algorithmic result. Our algorithm in fact works for the more general
Max 1-in-k-SAT problem where negated literals are allowed and the goal is to find an assignment for
which a maximum number of clauses have exactly one literal set to true. For satisfiable instances of Max
1-in-k-SAT, a factor 1/e approximation algorithm was given in [8].
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 243
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
Theorem 2.5. For every constant B > 1, the following holds. There is a polynomial time algorithm
that, given a (1 − 1/(Bk))-satisfiable instance of Max 1-in-k-SAT, finds a truth-assignment
√ on variables
satisfying exactly one literal in a fraction λ of the clauses, where λ = (1 − 1/ B)2 /e.
3 Proof method
We construct integrality gap instances for a certain semidefinite programming relaxation (described in
Section 3.1), and then use Raghavendra’s theorem [17] to conclude that assuming the Unique Games
conjecture, no algorithm can achieve an approximation ratio better than the SDP integrality gap.
In contrast to previous such integrality gap constructions (e. g., for Max Cut) where the instances had
a good SDP solution “by design” and the technical core was bounding the integral optimum, in our case
bounding the integral optimum is the easy part and the challenge is in the construction of appropriate
SDP vectors. See Section 3.2 for an overview of our gap instances. It is also interesting that our SDP
gaps match corresponding LP gaps. In general it seems like an intriguing question for which CSPs this is
the case and therefore LPs suffice to get the optimal approximation ratio.
For our algorithmic results (see Section 3.3), we use a natural linear programming relaxation. For
Max 1-in-k-SAT we show that randomized rounding gives a good approximation. The algorithm for Max
Horn-2SAT proceeds by showing half-integrality of the LP.
3.1 The canonical SDP for Boolean CSPs and UG-Hardness
For Boolean CSP instances, we write C as the set of constraints over variables x1 , x2 , . . . , xn ∈ {0, 1}.
The SDP relaxation from [17], which we call the canonical SDP, sets up for each constraint C ∈ C a
local distribution πC on all the truth-assignments {σ : XC → {0, 1}}, where XC is the set of variables
involved in the constraint C. This is implemented via scalar variables πC (σ ) which are required to be
non-negative and satisfy ∑σ :XC →{0,1} πC (σ ) = 1. For each variable x, two orthogonal vectors v (x,0) and
v (x,1) , corresponding to the events x = 0 and x = 1, are set up. The SDP requires for each variable x,
v (x,0) · v (x,1) = 0 and v (x,0) + v (x,1) = I where I is a global unit vector. (In the integral solution, one of the
vectors v (x,1) , v (x,0) —based on the x’s Boolean value—is intended to be I and the other one to be 0 .)
Then, as constraint (3.5), the SDP does a consistency check: for two variables x, y (that need not be
distinct) involved in the same constraint C, and for every b1 , b2 ∈ {0, 1}, the SDP insists that the inner
product v (x,b1 ) · v (y,b2 ) equals Prσ ∈πC [(σ (x) = b1 ) ∧ (σ (y) = b2 )].
Maximize EC∈C [Prσ ∈πC [C(σ ) = 1]] (3.1)
subject to v (xi ,0) · v (xi ,1) = 0 ∀i ∈ [n] , (3.2)
v (xi ,0) + v (xi ,1) = I ∀i ∈ [n] , (3.3)
2
kII k = 1 , (3.4)
Prσ ∈πC [σ (xi ) = b1 ∧ σ (x j ) = b2 ] = v (xi ,b1 ) · v (x j ,b2 ) ∀C ∈ C, xi , x j ∈ C, b1 , b2 ∈ {0, 1} .
(3.5)
Note that if we discard all the vectors by removing constraints (3.2)∼(3.4), and changing constraints (3.5)
to Prσ ∈πS [σ (xi ) = b1 ∧ σ (x j ) = b2 ] = X(xi ,b1 ),(x j ,b2 ) , the SDP becomes a lifted LP in a Sherali-Adams
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 244
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
system. We call this LP scheme the lifted LP in this paper.
The following striking theorem (Theorem 1.1 in [17]) states that once we have an integrality gap for
the canonical SDP, we also get a matching UG-hardness. Below and elsewhere in the paper, a c vs. s gap
instance is an instance with SDP optimum at least c and integral optimum at most s.
Theorem 3.1. Let 1 > c > s > 0. If a constraint satisfaction problem Λ admits a c vs. s integrality gap
instance for the above canonical SDP, then for every constant η > 0, given an instance of Λ that admits
an assignment satisfying (c − η) of constraints, it is UG-Hard to find an assignment satisfying more than
(s + η) of constraints.
To make our construction of integrality gaps easier, we notice the following simplification of the
above SDP. Suppose we are given the global unit vector I and a vector v x for each variable x in the CSP
instance, subject to the following constraints:
(II − v x ) · v x = 0 ∀ variables x , (3.6)
Prσ ∈πC [σ (xi ) = 1 ∧ σ (x j ) = 1] = v xi · v x j ∀C ∈ C, xi , x j ∈ C . (3.7)
Defining v (x,1) = v x and v (x,0) = I − v x , it is easy to check that all constraints of the above SDP are
satisfied. For instance, for variables x, y belonging to a constraint C,
v (x,0) · v (y,1) = (II − v (x,1) ) · v (y,1) = kvv(y,1) k2 − v (x,1) · v (y,1)
= Prσ ∈πC [σ (y) = 1] − Prσ ∈πC [(σ (x) = 1) ∧ (σ (y) = 1)]
= Prσ ∈πC [(σ (x) = 0) ∧ (σ (y) = 1)] ,
and other constraints of (3.5) follow similarly.
Henceforth in this paper, we will work with this streamlined canonical SDP with vector variables I ,
{vvx }, scalar variables corresponding to the local distributions πC , constraints (3.6) and (3.7), and objective
function (3.1).
3.2 Overview of construction of SDP gaps
Horn-3SAT In the concluding section of [19], Zwick remarks that there is an integrality gap for the
LP he uses that matches his approximation ratio. Indeed such a LP gap is not hard to construct and we
start by describing one such instance. The instance begins with clause x1 , and in the intermediate (k − 1)
clauses, the i-th clause x1 ∧ . . . ∧ xi → xi+1 makes xi+1 true if all the previous clauses are satisfied. Then
the last clause xk generates a contradiction. Thus the optimal integral solution is at most (1 − 1/k). On the
other hand, one possible fractional solution starts with x1 = (1 − ε) for some ε > 0. Then for 1 ⩽ i < k,
by letting (1 − xi+1 ) = ∑ij=1 (1 − x j ), all the intermediate (k − 1) clauses are perfectly “satisfied” by the
LP, while the gap (1 − xi+1 ) = 2i−1 ε increases exponentially. Thus by letting ε = 1/2k−2 , we get xk = 0
and the LP solution is at least (1 − 1/2Ω(k) ). The instance gives a (1 − 2−Ω(k) ) vs. (1 − 1/k) LP integrality
gap.
Now we convert this LP gap instance into an SDP gap instance in two steps. First, since we are going
to give a gap instance for Max Horn-3SAT, we reduce the arity of the instance from k to 3. Then, we find
a set of vectors for the LP solution to make it an SDP solution.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 245
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
For the first step, to get an instance of Max Horn-3SAT, we introduce yi which is intended to be
x1 ∧ . . . ∧ xi−1 . For 1 ⩽ i < k, we replace the intermediate clauses by xi ∧ yi → xi+1 , and add xi ∧ yi → yi+1
to meet the intended definition of yi . We call each of these two clauses as comprising one step . It is
easy to show that for this instance there is a solution of value (1 − 1/2Ω(k) ) even for the lifted LP. (The
difference between the lifted LP and Zwick’s LP is that the lift LP introduces local distributions over
clauses which are consistent in the first and second moments, while Zwick’s LP only has variables for
singletons.)
Finding vectors for the SDP turns out to be more challenging. Note that if we want to perfectly satisfy
all the intermediate clauses in SDP, we need to obey v xi · v yi ⩽ kvvxi+1 k2 and v xi · v yi ⩽ kvvyi+1 k2 for 1 ⩽ i < k.
Thus to make the norms kvvxi+1 k2 and kvvyi+1 k2 decrease fast (since we want kvvxk k2 = kvvyk k2 = 0), we
need to make the inner product v xi · v yi decrease fast as well. But technically it is hard to make both kinds
of quantities decrease at a high rate for all intermediate clauses. Our solution is to decrease the norms
and inner products alternately. More specifically, we divide the intermediate clauses into blocks, each of
which contains two consecutive steps. In the first step of each block, we need that the inner product is
much smaller than the norms so that we can decrease the norms quickly, but we preserve the value of
inner product. Thus we cannot do this step repeatedly, and we need the second step, where we decrease
the inner product (while preserving the norms) in preparation to start the first step of the next block.
1-in-k Hitting Set We use a simple symmetric instance as our gap instance. Ideally, the instance includes
all subsets of the universe with size at most k and we put uniform weights on sets of geometrically varying
sizes (see Section 5.1 for our real gap instance which is slightly different). We first show that every subset
intersects at most a (weighted) fraction O(1/ log k) of the sets exactly once. Then, to prove a much better
SDP solution, in contrast to Max Horn-3SAT, the main effort is in finding a good solution for lifted LP.
Once we get a good solution for lifted LP, because of symmetry, the norms for all variables are defined to
be the same value, and the pairwise inner products are also defined to be the same value. Then we only
need to find vectors for a highly symmetric inner-product matrix, a step which is much easier than the
counterpart of Max Horn-3SAT.
For the lifted LP, for each set in the instance, we place overwhelming weight on singleton subsets (only
one variable is selected to be true) in all local distributions. This guarantees a good fractional solution. If
we put all the weight on singletons though, the consistency check fails even for single-variable marginal
distributions, whereas we need to ensure consistency of all pairwise-variable marginal distributions.
Thus, for a feasible LP solution, we need to place some small weight on other subsets in order to obtain
consistent marginal distributions. Indeed, we manage to generate a valid solution by giving an appropriate
probability mass to the full set and all subsets of half the size in each local distribution.
3.3 Overview of algorithmic results
Our algorithmic results for Max Horn-2SAT and Max 1-in-k-SAT (Theorems 2.2 and 2.5 respectively)
are obtained by rounding fractional solutions of appropriate linear programming (LP) relaxations.
The algorithm for Max Horn-2SAT is indeed a 2-approximation algorithm for Min Horn-2SAT
Deletion problem (refer to Section 4.2 for the definition of Min Horn-2SAT Deletion). We prove a
half-integrality property of the optimal solution to the natural LP relaxation of the problem, which can
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 246
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
be viewed as a generalization of half-integrality property of (the natural LP for) Vertex Cover. We
take the optimal solution of the natural LP relaxation, iteratively make every variable move towards
half-integral values (0, 1, and 1/2), while never increasing the value of the solution. This yields an
optimal half-integral solution which can then be trivially rounded to obtain an integral solution that gives
a factor 2 approximation.
For almost-satisfiable instances of Max 1-in-k-SAT, we prove that randomized rounding (according
to the fractional value of any optimal LP solution) gives a constant factor approximation. This gives a
robust version of the algorithm in [8] which achieved a factor 1/e-approximation for (perfectly) satisfiable
instances.
4 Approximability of Max Horn-3SAT
4.1 SDP gap and UG hardness for Max Horn-3SAT
4.1.1 Instance
We consider the following Max Horn-3SAT instance IHorn k parameterized by k ⩾ 1. (This construction is
essentially the same as the one described in Section 3.2.)
Start point: x0 , y0
Block i (0 ⩽ i ⩽ k − 1) Step i.1 : x2i ∧ y2i → x2i+1 , x2i ∧ y2i → y2i+1
Step i.2 : x2i+1 ∧ y2i+1 → x2i+2 , x2i+1 ∧ y2i+1 → y2i+2
End point: x2k ∧ y2k → x2k+1 , x2k ∧ y2k → y2k+1
x2k+1 , y2k+1
It is easy to see this instance contains (4k + 6) clauses, and cannot be completely satisfied. Thus we have:
Lemma 4.1. Every Boolean assignment satisfies at most a fraction 1 − 1/(4k + 6) of the clauses of IHorn
k .
4.1.2 Construction of a good SDP solution
We will work with the SDP in simplified form described at the end of Section 3.1. Recall that the SDP
requires a local distribution for each clause, and uses vectors to check the consistency on every pair
of variables that belong to the clause. To construct a good solution for the SDP, we want to first find
a good solution in the scalar part (i. e., local distributions), and then construct vectors which meet the
consistency requirement. But it is difficult to construct a lot of vectors which meet all the requirements
simultaneously. Thus, we break down the whole construction task into small pieces, each of which is easy
to deal with. As long as there are solutions to these small pieces, and the solutions agree with each other
on some interfaces, we can coalesce the small solutions together and come up with a global solution. The
following definition and claim formally help us bring down the difficulty, and focus on one local block of
variables at a time.
Definition 4.2 (partial solution). Let C0 ⊆ C be a subset of clauses.
f = {πC = πC ( f ), v x = v x ( f ), I = I ( f ) | ∀C ∈ C0 , x ∈ C}
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 247
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
is said to be a partial solution on C0 , if all constraints of the SDP restricted to the subset of variables
defined in f are satisfied.
Claim 4.3. Let C1 , C2 ⊆ C be two disjoint set of clauses. Let f and g be partial solutions on C1 , C2
respectively. If for all v 1 , v 2 (not necessarily distinct) defined in both f and g, v 1 ( f ) · v 2 ( f ) = v 1 (g) · v 2 (g),
then there exists a partial solution, namely h, for C1 ∪ C2 , such that ∀C1 ∈ C1 ,C2 ∈ C2 , πC1 (h) =
πC1 ( f ), πC2 (h) = πC2 (g).
Proof. Let X be the set of variables x for which v x ( f ) and v x (g) are both defined. Denote
V f = {vvx ( f ) | x ∈ X} ∪ {II ( f )} and Vg = {vvx (g) | x ∈ X} ∪ {II (g)} .
Since the dot products of every pair of vectors in V f exactly equals the dot product between the corre-
sponding pair in Vg , there is a rotation (orthogonal transformation) T such that I ( f ) = T I (g) and for all
x ∈ X, v x ( f ) = T v x (g).
Now define the partial solution g0 as πC (g0 ) = πC (g) for all C ∈ C2 and v x (g0 ) = T v x (g), I (g0 ) = T I (g)
for all x ∈ C ∈ C2 . Obviously f and g0 agree on all the scalar and vector variables that are defined in both
f and g0 . Letting
v x ( f ) x ∈ C ∈ C1 πC ( f ) C ∈ C1
v x (h) = , πC (h) = ,
vx (g0 ) x ∈ C ∈ C2 πC (g0 ) C ∈ C2
it is easy to see h is a partial solution on C1 ∪ C2 .
By the above lemma, if we establish the following lemma which constructs a good partial solution on
each block (the proof of which is deferred to Section 4.1.3), it is then easy to get a good global solution.
Lemma 4.4. For each block i (0 ⩽ i ⩽ k − 1), each 0 < c ⩽ 0.2, let rc = 1.5(1 + c)/(1.5 + c) > 1, and
for each 0 < p ⩽ 1/((1 + c)rc ), there is a partial solution f which completely satisfies all the clauses in
block i (by local distributions), and with following properties,
kvvx2i ( f )k2 = kvvy2i ( f )k2 = 1 − p ,
v x2i ( f ) · v y2i ( f ) = 1 − (1 + c)p ,
kvvx2i+2 ( f )k = kvvy2i+2 ( f )k2 = 1 − rc p ,
2
v x2i+2 ( f ) · v y2i+2 ( f ) = 1 − (1 + c)rc p .
As explained in Section 3.2, in the first step (the step to decrease norms), to make kvvx2i+2 ( f )k2 and
kvvy2i+2 ( f )k2 much smaller than kvvx2i ( f )k2 and kvvy2i ( f )k2 , we need the inner product v x2i ( f ) · v y2i ( f ) to
be small. This is why we introduce c, and require that v x2i ( f ) · v y2i ( f ) = 1 − (1 + c)p. The larger c is, the
faster the norms decrease. But due to technical reasons, in the second step (the step to decrease the inner
product), we are not able to decrease the inner product fast when it is much smaller than the norms. So
we put a upper bound c ⩽ 0.2 in the lemma.
Using Lemma 4.4 together with Claim 4.3, we immediately get the following corollary.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 248
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
Corollary 4.5. For the union of block 0 to block k0 (0 ⩽ k0 ⩽ k − 1), given parameters
1
0 < c ⩽ 0.2 and 0 < p ⩽ 0 ,
(1 + c)rck +1
there is a partial solution g which completely satisfies all the clauses, and with following properties,
kvvx0 (g)k2 = kvvy0 (g)k2 = 1 − p ,
v x0 (g) · v y0 (g) = 1 − (1 + c)p ,
0
kvvx2k0 +2 (g)k2 = kvvy2k0 +2 (g)k2 = 1 − rck +1 p ,
0
v x2k0 +2 (g) · v y2k0 +2 (g) = 1 − (1 + c)rck +1 p .
Proof. Apply induction on k0 . The basis case k0 = 0 is exactly Lemma 4.4. For k0 > 0, by induction
hypothesis there is a partial solution g0 satisfying all the clauses of the union of blocks 0 to k0 − 1 with the
same parameter c, p. By Lemma 4.4, there is a partial solution f satisfying all the clauses of block k0
0
with parameter c, rck p. Since g0 and f agree on pairwise inner-products over the definition of {vvx2k0 , v y2k0 },
by Claim 4.3, there is a partial solution g on the union of blocks 0 to k0 completely satisfying all the
clauses.
With the above pieces in place, we now come to the final SDP solution.
Lemma 4.6. The optimal SDP solution for the instance IHorn
k has value at least
1
1− .
(2k + 3)1.05k
Proof. By Corollary 4.5, for any 0 < c ⩽ 0.2, by setting p = 1/((1 + c)rck ), there is a partial solution g
completely satisfying all the clauses of all the blocks, with
1
kvvx0 (g)k2 = kvvy0 (g)k2 = 1 − ,
(1 + c)rck
kvvx2k (g)k2 = kvvy2k (g)k2 = c/(1 + c) ,
v x2k (g) · v y2k (g) = 0 .
Based on g, we define a local distribution on two “Start point” clauses by making x0 (or y0 ) equal 1 with
probability 1 − p. At “End point,” we define the local distribution on clause x2k ∧ y2k → x2k+1 as
Prπ [x2k = 1 ∧ y2k = 0 ∧ x2k+1 = 0] = c/(1 + c) ,
Prπ [x2k = 0 ∧ y2k = 1 ∧ x2k+1 = 0] = c/(1 + c) ,
Prπ [x2k = 0 ∧ y2k = 0 ∧ x2k+1 = 0] = (1 − c)/(1 + c) .
And a similar distribution for the clause x2k ∧ y2k → y2k+1 can be defined (by replacing x2k+1 by y2k+1 in
the equations above). The distribution on clauses x2k+1 and y2k+1 never picks the corresponding variable
to be 1. By defining v x2k+1 and v y2k+1 to be zero vectors, we note that the distributions are consistent with
vectors. Thus the solution we construct is valid.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 249
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
On the other hand, note that all the distributions locally satisfy the clauses, except for the distributions
at “Start point” satisfy the corresponding clause with probability 1 − 1/((1 + c)rck ). Thus the SDP solution
has value
2 1
1− = 1 ⩾ 1− .
(4k + 6)(1 + c)rck (2k + 3)rck
By setting c = 0.2, we get rc ⩾ 1.05. Thus the best SDP solution has value at least 1 − 1/((2k + 3)1.05k ).
Combining Lemma 4.1 and Lemma 4.6, we get the following theorem.
Theorem 4.7. IHorn
k is a (1 − ε) vs. (1 − Ω(1/ log(1/ε))) gap instance of Max Horn-3SAT for the
canonical SDP relaxation.
Together with Theorem 3.1, Theorem 4.7 implies our main result, Theorem 2.1, on Max Horn-SAT.
4.1.3 Proof of the key Lemma 4.4
For block i, denote the clauses in Step i.1 by C1x and C1y , and the clauses in Step i.2 by C2x and C2y . We
first construct partial solutions on Step i.1 and Step i.2 separately, as follows.
Partial solution on Step i.1 We first define a local distribution on satisfying assignments for C1x as
follows, and C1y in a similar way (by replacing x2i+1 by y2i+1 in following equations).
PrπC1x [x2i = 1 ∧ y2i = 1 ∧ x2i+1 = 1] = 1 − (1 + c)p ,
PrπC1x [x2i = 1 ∧ y2i = 0 ∧ x2i+1 = 0] = cp ,
PrπC1x [x2i = 0 ∧ y2i = 1 ∧ x2i+1 = 0] = cp ,
(1 + c)c
PrπC1x [x2i = 0 ∧ y2i = 0 ∧ x2i+1 = 1] = (1 + c − rc )p = · p,
1.5 + c
1.5 − 1.5c − 2c2
PrπC1x [x2i = 0 ∧ y2i = 0 ∧ x2i+1 = 0] = (rc − 2c)p = · p.
1.5 + c
Recall rc = 1.5(1 + c)/(1.5 + c). Note that all the probabilities are defined to be non-negative values by
the range of c and p, and they sum up to 1.
We observe the following inner-product matrix A over I , v x2i , v y2i , v x2i+1 , v y2i+1 is consistent with the
local distributions on satisfying assignments for C1x and C1y .
1 1− p 1− p 1 − rc p 1 − rc p
1− p 1− p 1 − (1 + c)p 1 − (1 + c)p 1 − (1 + c)p
A = 1 − p 1 − (1 + c)p
1− p 1 − (1 + c)p 1 − (1 + c)p
.
1 − rc p 1 − (1 + c)p 1 − (1 + c)p 1 − rc p 1 − (1 + c)p
1 − rc p 1 − (1 + c)p 1 − (1 + c)p 1 − (1 + c)p 1 − rc p
By Claim 4.8 (at the end of this section) we know that A is positive semidefinite, and therefore there is a
set of vectors consistent with our local distributions, i. e., we get a partial solution on Step i.1.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 250
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
Partial solution on Step i.2 We define the local distribution on satisfying assignments for C2x as
follows. The distribution for C2y is defined in a similar way (by replacing x2i+2 with y2i+2 in the following
equations). Let q = rc p and ε = c/1.5.
PrπC2x [x2i+1 = 1 ∧ y2i+1 = 1 ∧ x2i+2 = 1] = 1 − (1 + ε)q ,
PrπC2x [x2i+1 = 1 ∧ y2i+1 = 0 ∧ x2i+2 = 0] = εq ,
PrπC2x [x2i+1 = 0 ∧ y2i+1 = 1 ∧ x2i+2 = 0] = εq ,
PrπC2x [x2i+1 = 0 ∧ y2i+1 = 0 ∧ x2i+2 = 1] = εq ,
PrπC2x [x2i+1 = 0 ∧ y2i+1 = 0 ∧ x2i+2 = 0] = (1 − 2ε)q .
Note that all the probabilities are defined to be non-negative values by the range of c and p, and they
sum up to 1.
Then note that the following inner-product matrix B over I , v x2i+1 , v y2i+1 , v x2i+2 , v y2i+2 is consistent with
the local distribution.
1 1−q 1−q 1−q 1−q
1−q 1−q 1 − (1 + ε)q 1 − (1 + ε)q 1 − (1 + ε)q
B = 1 − q 1 − (1 + ε)q
1−q 1 − (1 + ε)q 1 − (1 + ε)q .
1 − q 1 − (1 + ε)q 1 − (1 + ε)q 1−q 1 − (1 + 1.5ε)q
1 − q 1 − (1 + ε)q 1 − (1 + ε)q 1 − (1 + 1.5ε)p 1−q
Again by Claim 4.8, B is positive semidefinite, and therefore there is a set of vectors consistent with local
distributions—we have constructed a partial solution on Step i.2.
Combining the two partial solutions We first check that under our parameter setting, partial solutions
on Step i.1 and Step i.2 agree on pairwise inner-products between their shared vectors I , v x2i+1 , v y2i+1 .
• For hII , I i, we have 1 = 1.
• For hII , v x2i+1 i, we have 1 − rc p = 1 − q.
• For hII , v y2i+1 i, we have 1 − rc p = 1 − q.
• For hvvx2i+1 , v x2i+1 i, we have 1 − rc p = 1 − q.
• For hvvx2i+1 , v y2i+1 i, we have 1 − (1 + c)p = 1 − (1 + c/1.5)rc p = 1 − (1 + ε)q.
• For hvvy2i+1 , v y2i+1 i, we have 1 − rc p = 1 − q.
Thus, there is a partial solution on block i, with
kvvx2i ( f )k2 = kvvy2i ( f )k2 = 1 − p ,
v x2i ( f ) · v y2i ( f ) = 1 − (1 + c)p ,
kvvx2i+2 ( f )k = kvvy2i+2 ( f )k2 = 1 − q = 1 − rc p ,
2
v x2i+2 ( f ) · v y2i+2 ( f ) = 1 − (1 + 1.5ε)q = 1 − (1 + c)rc p .
Finally, we establish the two positive semidefinite matrices used in the proof above.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 251
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
Claim 4.8. Given 0 < c ⩽ 0.2, 0 < p ⩽ rc /(1 + c), q = rc p, ε = c/1.5, the following two matrices are
positive semidefinite:
1 1− p 1− p 1 − rc p 1 − rc p
1− p 1− p 1 − (1 + c)p 1 − (1 + c)p 1 − (1 + c)p
A = 1 − p 1 − (1 + c)p
1− p 1 − (1 + c)p 1 − (1 + c)p ,
1 − rc p 1 − (1 + c)p 1 − (1 + c)p 1 − rc p 1 − (1 + c)p
1 − rc p 1 − (1 + c)p 1 − (1 + c)p 1 − (1 + c)p 1 − rc p
1 1−q 1−q 1−q 1−q
1−q 1−q 1 − (1 + ε)q 1 − (1 + ε)q 1 − (1 + ε)q
B = 1 − q 1 − (1 + ε)q
1−q 1 − (1 + ε)q 1 − (1 + ε)q .
1 − q 1 − (1 + ε)q 1 − (1 + ε)q 1−q 1 − (1 + 1.5ε)q
1 − q 1 − (1 + ε)q 1 − (1 + ε)q 1 − (1 + 1.5ε)p 1−q
Proof. Let J be the all 1 matrix, E1 be the matrix with 1 in entry (1, 1) as the only one non-zero entry.
We also define Ei, j , Fi, j and Gi, j as matrices with only four non-zero entries located in the intersections of
Column i, j and Row i, j. The sub-matrices of Ei, j , Fi, j and Gi, j on Column i, j and Row i, j are defined as
1 1 2 1 1 −1
(for Ei, j ) , (for Fi, j ) and (for Gi, j ) .
1 1 1 0.5 −1 1
Clearly, all of J, E1 , Ei, j , Fi, j and Gi, j are positive semidefinite matrices.
Then we can write A as
A = (1 − (1 + c)p)J + cp(E1,2 + E1,3 ) + (1 + c − rc )p(E1,4 + E1,5 ) + (2rc − 1 − 3c)pE1
(1 + c)c 1.5 − 2.5c − 3c2
= (1 − (1 + c)p)J + cp(E1,2 + E1,3 ) + · p(E1,4 + E1,5 ) + · pE1 .
1.5 + c 1.5 + c
Note that all the coefficients before matrices are non-negative within the range of c. Since A can be
written as the sum of several positive semidefinite matrices, A is positive semidefinite.
For matrix B, note that
B = (1 − (1 + ε)q)J + εq(E1,2 + E1,3 + F1,4 + F1,5 ) + 0.5εqG4,5 + (1 − 5ε)qE1 .
Clearly, as long as 5ε = 5c/1.5 < 1, B can be expressed as sum of positive semidefinite matrices, and
hence B is positive semidefinite.
4.2 Algorithm for Min Horn-2SAT Deletion and Max Horn-2SAT
In the Min Horn-2SAT Deletion problem, we are given a Horn-2SAT instance, and the goal is to
find a subset of clauses of minimum total weight whose deletion makes the instance satisfiable. A
factor 3 approximation algorithm for Min Horn-2SAT Deletion is given in [12]. Here we improve the
approximation ratio to 2. Note that following reduction from vertex cover is approximation preserving:
given a graph with n vertices, for each edge (i, j), introduce a clause x̄i ∨ x¯j of weight n; for each vertex i,
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 252
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
introduce a clause xi of weight 1. Therefore, by the inapproximability result for vertex cover [15], our
approximation algorithm for Min Horn-2SAT Deletion is optimal under the UGC.
Our motivation to study Min Horn-2SAT Deletion in the context of this paper is to pin down the
fraction of clauses one can satisfy in a (1 − ε)-satisfiable instance of Horn-2SAT: we can satisfy a fraction
(1 − 2ε) of clauses (even in the weighted case), and satisfying a (1 − cε) fraction is hard for c < 2
assuming that vertex cover does not admit a c-approximation for any constant c < 2.
In this section, we prove the following theorem by showing half-integrality of a natural LP relaxation
for the problem.
Theorem 4.9. There is a polynomial-time 2-approximation algorithm for Min Horn-2SAT Deletion
problem.
Theorem 2.2 (on approximating near-satisfiable instances of Max Horn-2SAT) is a direct corollary of
Theorem 4.9.
4.2.1 LP formulation
We find it slightly more convenient to present the algorithm for dual Horn-2SAT where each clause has
at most one negated literal. (So the clauses are of the form x, x̄, x ∨ y, or x → y, for variables x, y.) Let
(D)
wi j > 0 be the weight imposed on the disjunction constraint xi ∨ x j (for each pair of i, j such that i < j),
(I)
and wi j > 0 be the weight imposed on the implication constraint xi → x j (for each pair of i, j such that
(T ) (F)
i 6= j). For each variable xi , let wi be the weight on xi being true (i. e., xi = 1), and wi be the weight
on xi being false (i. e., xi = 0). Then we write the following LP relaxation, where each real variable yi
corresponds to the integer variable xi :
(T ) (F) (D) (D) (I) (I)
Minimize ∑ wi (1 − yi ) + ∑ wi yi + ∑ wi j zi j + ∑ wi j zi j
i∈V i∈V i< j i6= j
(D)
subject to zi j ⩾ 1 − yi − y j ∀i < j ,
(I)
zi j ⩾ yi − y j ∀i 6= j ,
(D)
zi j ⩾0 ∀i < j ,
(I)
zi j ⩾0 ∀i 6= j ,
yi ∈ [0, 1] ∀i ∈ V .
Let OPT be the optimal value of the integral solution, and OPTLP be the optimal value of the LP
solution. We have OPTLP ⩽ OPT.
4.2.2 Half-integrality and rounding
(D) (I) (D) (I)
Given a LP solution f = {zi j , zi j , yi }, we can assume zi j = max{1 − yi − y j , 0} and zi j = max{yi −
y j , 0} to minimize Val( f ). Thus, we only need f = {yi } to characterize a solution, and we have
(T ) (F) (D) (I)
Val( f ) = ∑ wi (1 − yi ) + ∑ wi yi + ∑ wi j max{1 − yi − y j , 0} + ∑ wi j max{yi − y j , 0} .
i∈V i∈V i< j i6= j
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 253
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
Lemma 4.10. There is a polynomial-time algorithm that, given a solution f = {yi } to the above LP,
converts f into another solution f ∗ = {y∗i } such that each y∗i is half-integral, i. e., y∗i ∈ {0, 1, 1/2}, and
Val( f ∗ ) ⩽ Val( f ).
Proof. We run Algorithm 1 whose input is the LP formulation and one of the solutions f = {yi }, and
whose output is the desired f ∗ . At a high level, the algorithm iteratively moves the LP variables that are
not half integral to half integral values (according to some strategy), and we need to prove that at each
step of the iteration, the algorithm creates a new valid LP solution whose objective value is no greater
than the previous one.
Algorithm 1 Round any LP solution f = {yi } to a half-integral solution f ∗ , with Val( f ∗ ) ⩽ Val( f )
1: while ∃i ∈ V : yi 6∈ {0, 1, 1/2} do
2: choose k ∈ V , such that yk 6∈ {0, 1, 1/2} (arbitrarily)
3: if yk < 1/2 then
4: p ← yk
5: else
6: p ← 1 − yk
7: end if
8: S ← {i : yi = p}, S0 ← {i : yi = 1 − p}
9: a ← max{yi : yi < p, 1 − yi : yi > 1 − p, 0}, b ← min{yi : yi > p, 1 − yi : yi < 1 − p, 1/2}
(a) (a) (a)
10: f (a) ← {yi = a}i∈S ∪ {yi = 1 − a}i∈S0 ∪ {yi = yi }i∈V \(S∪S0 )
(b) (b) (b)
11: f (b) ← {yi = b}i∈S ∪ {yi = 1 − b}i∈S0 ∪ {yi = yi }i∈V \(S∪S0 )
12: if Val( f (a) ) ⩽ Val( f (b) ) then
13: f ← f (a)
14: else
15: f ← f (b)
16: end if
17: end while
18: return f (as f ∗ )
It’s easy to see that Algorithm 1 always maintains a valid solution f to the LP (i. e., all variables
yi ’s are within the [0, 1] range). Then we only need to prove the following two things to show the
correctness of Algorithm 1: (1) the while loop terminates (in a linear number of steps), (2) in each loop,
min{Val( f (a) ), Val( f (b) )} ⩽ Val( f ), so that Val( f ) never increases in the whole algorithm.
To prove the first point, we consider the set
W f = {0 < y < 1/2 : ∃i ∈ V, s.t. y = yi ∨ y = 1 − yi } .
In each loop, the algorithm picks a p from W f . At the end of the loop, we see that p is wiped from
W f while no new elements are added. Thus, after linear steps of the loop, W f becomes 0/ and the loop
terminates.
For the second point, we define
(t) (t) (t)
f (t) = {yi = t}i∈S ∪ {yi = 1 − t}i∈S0 ∪ {yi = yi }i∈V \(S∪S0 )
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 254
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
for t ∈ [a, b] at Line 9 in the algorithm. Then if we can show Val( f (t) ) is a linear function within t ∈ [a, b],
together with the fact p ∈ [a, b], we shall conclude that min{Val( f (a) ), Val( f (b) )} ⩽ Val( f (p) ) = Val( f ).
To prove the linearity of Val( f (t) ), we only need to show that
(t) (t) (t) (t)
g1 (t) = max{1 − yi − y j , 0} and g2 (t) = max{yi − y j , 0}
are linear with the respect to t ∈ [a, b], for any possible i, j. Thus we discuss the following five cases.
• i, j ∈ V \ (S ∪ S0 ). In this case, g1 and g2 are constant functions.
• i ∈ V \ (S ∪ S0 ), j ∈ S ∪ S0 . In this case, the only “non-linear point” is at t = 1 − yi for g1 and t = yi
for g2 . But these two points are away from [a, b].
• i ∈ S ∪ S0 , j ∈ V \ (S ∪ S0 ). Similar argument works as the previous case.
(t) (t)
• i ∈ S, j ∈ S0 (or i ∈ S0 , j ∈ S). In this case, 1 − yi − y j = 0 always holds for t ∈ [a, b] and therefore
(t) (t) (t) (t)
g1 is constant function. On the other hand, since yi ⩽ y j (or yi ⩾ y j ) , we also have g2 (t) = 0
(t) (t)
(or g2 (t) = yi − y j = 1 − 2t) being linear.
(t) (t)
• i, j ∈ S (or i, j ∈ S0 ). In this case, yi = y j always holds for t ∈ [a, b] and therefore g2 is constant
(t) (t) (t) (t) (t)
function. On the other hand, since yi + y j ⩽ 1 (or yi + y j ⩾ 1), we also have g1 (t) = 1 − yi −
(t)
y j = 1 − 2t (or g1 (t) = 0) being linear.
A direct corollary of Lemma 4.10 is the following.
Corollary 4.11. There is a polynomial-time algorithm to get a solution f such that Val( f ) = OPTLP and
the variables in f are half-integral (i. e., being one of 0, 1, and 1/2).
Now we are ready for the proof of Theorem 4.9.
Proof of Theorem 4.9. Apply Corollary 4.11 to get an optimal LP solution f = {yi } which has half-
integral values. Then define fint = {xi } as follows. For each i ∈ V , let xi = 1 when yi ⩾ 1/2, and xi = 0
when yi = 0. We observe that
• xi ⩽ 2yi and 1 − xi ⩽ 1 − yi for each i ∈ V .
• For each i < j, we have max{1 − xi − x j , 0} ⩽ max{1 − yi − y j , 0} since xi ⩾ yi and x j ⩾ y j .
• For each i 6= j, we see that when max{yi − y j , 0} = 0 (in which case we have yi ⩽ y j ), we
always have xi ⩽ x j , therefore max{xi − x j , 0} = 0. On the other hand, when max{yi − y j , 0} (in
which case by half-integrality we havemax{yi − y j , 0} ⩾ 1/2), we have max{xi − x j , 0} ⩽ 1 ⩽
2 max{yi − y j , 0}.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 255
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
Altogether, we have
(T ) (F) (D) (I)
Val( fint ) = ∑ wi (1 − xi ) + ∑ wi xi + ∑ wi j max{1 − xi − x j , 0} + ∑ wi j max{xi − x j , 0}
i∈V i∈V i< j i6= j
(T ) (F) (D) (I)
⩽ ∑ wi (1 − yi ) + ∑ wi 2yi + ∑ wi j max{1 − yi − y j , 0} + ∑ wi j 2 max{yi − y j , 0}
i∈V i∈V i< j i6= j
⩽ 2Val( f ) = 2OPTLP ⩽ 2OPT .
5 Inapproximability and approximation algorithm for Max 1-in-k-HS
5.1 SDP gap and UG-hardness for Max 1-in-k-HS
In this section, we construct an SDP gap for Max 1-in-k-HS. Recall that the problem is to find a subset
that intersects a maximum number of sets (of size at most k) from an input family at exactly one element.
We are going to prove Theorem 2.4, which is restated as follows.
Theorem 2.4 (restated). For some absolute constant C0 > 0, for every α > 0, given a (1 − 1/k1−α )-
satisfiable instance of Max 1-in-k-HS, it is UG-hard to find a subset intersecting more than a fraction
C0 /(α log k) of the sets exactly once.
We start by constructing the gap instance. Roughly speaking, the instance includes all subsets of the
universe with size at most k and we put uniform weights on sets of geometrically varying sizes. Here is
the construction in details.
Instance We define the (weighted) instance of Max 1-in-k-HS, denoted IEHS (m, n, ε), parameter 0 <
ε < 1, m ⩾ 2 and n ⩾ εm · 22dm(1+ε)e as follows:
• The universe U = [n] = {1, 2, . . . , n}.
• Let the weight of a set S ∈ C be the probability under the following measure: choose t ∈
m + 1, m + 2, . . . , dm(1 + ε)e uniformly at random, and output a uniformly random subset of U of
size 2t .
Note that in such an instance, the size of Si is at most k = 2dm(1+ε)e .
5.1.1 Upper bound of optimal integral solution
In this section, we prove the following lemma showing that the above instance does not have a good exact
hitting set.
Lemma 5.1. There is a constant C1 such that for all 0 < ε < 1, m ⩾ 2 and n ⩾ εm · 22dm(1+ε)e , the optimal
solution to IEHS (m, n, ε) has value at most C1 /(ε log k).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 256
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
We begin with the following two statements that will be useful in bounding the value of any integral
solution to IEHS (m, n, ε).
Lemma 5.2. Suppose the hitting set V ⊆ U is of size `. Then the probability that a size-z (2 ⩽ z ⩽ `/2)
set is hit exactly once by V , is at most (2z/n) · ` · (1/e)z`/4n .
Proof.
` n−`
z−1
PrS∈C [|S ∩V | = 1 | |S| = z] = n
z
(n − `)!(n − z)!z!
= `·
(n − ` − z + 1)!(z − 1)!n!
(n − `)! (n − z)!
= z` · ·
(n − ` − z + 1)! n!
(n − `)z−1
⩽ z` ·
(n − z)z
z ` − z z−1
= ·`· 1−
n−z n−z
z 1 (z−1)(`−z)/(n−z)
⩽ ·`·
n−z e
z 1 z`/4(n−z)
⩽ ·`· (2 ⩽ z ⩽ `/2)
n−z e
2z 1 z`/4n
⩽ ·`· (z ⩽ `/2 ⩽ n/2) .
n e
Claim 5.3. For all x > 0 and m ∈ N+ , we have
m
i
∑ 2i xe−2 x ⩽ 2/ ln 2.
i=1
Proof.
m +∞
i i
∑ 2i xe−2 x ⩽ ∑ 2i xe−2 x
i=1 i=−∞
[log2 1/x] +∞
i i
= ∑ 2i xe−2 x + ∑ 2i xe−2 x
i=−∞ i=[log2 1/x]+1
Z [log 1/x]+1 Z +∞
2 y y
⩽ 2y xe−2 x dy + 2y xe−2 x dy (monotonicity)
−∞ [log2 1/x]
Z +∞
y
⩽ 2 2y xe−2 x dy
−∞
2
= .
ln 2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 257
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
We can now prove Lemma 5.1.
Proof of Lemma 5.1. Set C1 = max{32/ ln 2, 12}. Given a solution V , let ` = |V |. If ` ⩾ 2 · 2dm(1+ε)e ,
then ` ⩾ 2|S|, ∀S ∈ C. In this case, the probability that S ∈ C is hit exactly once, is
dm(1+ε)e
PrS∈C [|S ∩V | = 1] = ∑ PrS∈C [|S| = 2t ] · PrS∈C [|S ∩V | = 1 |S| = 2t ]
t=m+1
1 dm(1+ε)e
= ∑ PrS∈C [|S ∩V | = 1 |S| = 2t ]
εm t=m+1
1 dm(1+ε)e 2 · 2t 1 2t `/4n
⩽ ∑ n · ` · (by Lemma 5.2)
εm t=m+1 e
1 16
⩽ · (by Claim 5.3)
εm ln 2
⩽ C1 /(ε log k).
On the other hand, if ` < 2 · 2dm(1+ε)e , then
PrS∈C [|S ∩V | = 1]
⩽ PrS∈C [|S ∩V | ⩾ 1]
h i
⩽ PrS∈C |S ∩V | ⩾ 1 |S| = 2dm(1+ε)e (since the sets in C have size at most 2dm(1+ε)e )
.
n−` n
= 1 − dm(1+ε)e
2 2dm(1+ε)e
(n − `)! (n − 2dm(1+ε)e )!
= 1− ·
(n − ` − 2dm(1+ε)e )! n!
n − ` − 2dm(1+ε)e `
⩽ 1−
n
n − 3 · 2dm(1+ε)e 2·2dm(1+ε)e
⩽ 1− (` < 2 · 2dm(1+ε)e )
n
6 · 22dm(1+ε)e
⩽ (∀0 ⩽ x ⩽ 1, y ⩾ 0, (1 − x)y ⩾ 1 − xy)
n
⩽ 6/εm (n ⩾ εm · 22dm(1+ε)e )
⩽ C1 /(ε log k) .
And this proves the lemma.
5.1.2 Construction of good SDP solution
We prove that the canonical SDP has a solution with value close to 1.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 258
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
Lemma 5.4. For the Max 1-in-k-HS instance IEHS (m, n, ε), the optimal solution to the canonical SDP
has value at least 1 − 4/2m ⩾ 1 − 4/k1−ε .
To prove Lemma 5.4, recall the canonical SDP for Max 1-in-k-HS as follows:
Maximize ES∈C [Prσ ∈πS [|σ −1 (1)| = 1]]
subject to vi · I = kvvi k2 ∀i, j ∈ U ,
kII k2 =1 ∀i ∈ U ,
Prσ ∈πS [σ (i) = 1] = kvvi k2 ∀S ∈ C, i ∈ S ,
Prσ ∈πS [σ (i) = 1 ∧ σ ( j) = 1] = vi · v j ∀S ∈ C, i 6= j ∈ S .
Here are some high level ideas about the our construction of the SDP solution. To make the consistency
between local distributions, we need to find local distributions where every element has the same marginal
probability p and every pair of elements has the same marginal probability q. This is relatively simple
because of the symmetry of the sets in C. We can define the local distribution in a symmetric way, where
all the assignments choosing the same number of elements have the same probability mass. The goal is
to find the local distributions that have a lot of mass on singletons (the assignments choosing exactly 1
element). Ideally we want to put all the mass on singletons, but this would violate the consistency check
and positive semidefiniteness. We can resolve this issue by assigning a small fraction of probability mass
to the assignments choosing all the elements or choosing half of the elements, and giving more flexibility
to our construction.
Now, we exhibit an SDP solution for the instance IEHS (m, n, ε) that has value close to 1. We first
construct the scalars, and then the vectors.
Constructing the solution—scalars Let M = 2m , p = 2/M, q = 1/M. We would like to define local
probability distributions so that p is the marginal probability for a singleton being chosen, and q is the
marginal probability for a pair of distinct elements being chosen. For each S ∈ C, and each σ : S → {0, 1},
define the local distribution πS as follows:
|S| |S| 3|S|−2 |S|
·
|S|−2 |S|−1 − |S|−1 · p + 2q 1 if |σ −1 (1)| = 1,
if |σ −1 (1)| = |S|
4
|S|
|S|−2 · (|S| − 1)(p − q) − (1 − p) 2 ,
|S|/2
πS (σ ) = 1 − |S| πS (σ )||σ |=1 − |S| πS (σ )||σ −1 (1)|=|S|/2
1 |S|/2
|S|
= 1
− · p + 2q if |σ −1 (1)| = |S|,
|S|−1 |S|−1
0 otherwise.
Given M < |S| for all S ∈ C, it is easy to check πS is always non-negative. And it can be checked that
∑σ ⊆S πS (σ ) = 1. Thus, πS is a valid probability distribution.
Then we calculate the following values which are related to the SDP.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 259
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
• For all i ∈ S ∈ C,
|S| − 1 |S| |S| 3|S| − 2
Prσ ∈πS [σ (i) = 1] = 1 − · · − · p + 2q
|S| |S| − 2 |S| − 1 |S| − 1
1 4
− · · (|S| − 1)(p − q) − (1 − p)
2 |S| − 2
= p.
• For all i 6= j ∈ S ∈ C,
1 |S|
Prσ ∈πS [σ (i) = 1 ∧ σ ( j) = 1] = − · p + 2q
|S| − 1 |S| − 1
|S|/2 − 1 4
+ · · (|S| − 1)(p − q) − (1 − p)
2(|S| − 1) |S| − 2
= q.
Constructing the solution—vectors Now we need to show there exists a set of vectors passing the
consistency check on local distributions we defined above. In fact, we show there exists set of vectors
satisfying even stricter requirements, where the inner-product between every pair of vectors is defined, as
follows:
kvvi k2 = p ∀i ∈ U ,
vi · v j = q ∀i 6= j ∈ U ,
2
v i · I = kvvi k ∀i ∈ U ,
kII k2 = 1 .
Thus we only need to show the corresponding inner-product matrix is positive semidefinite. The matrix is
in the form of
pbbT
1
A=
pbb (p − q)I + qJ
where b is n × 1 all-one vector, J is the n × n all-one matrix, and I is the identity matrix.
Given x = (x0 , x1 , . . . , xn ) ∈ Rn ,
pbbT
T 1
x Axx = (x0 , x1 , . . . , xn ) (x0 , x1 , . . . , xn )T
pbb (p − q)I + qJ
n n n
= x02 + 2px0 ( ∑ xi ) + q( ∑ xi )2 + (p − q) ∑ xi2 .
i=1 i=1 i=1
Note that this quadratic form is always non-negative when p ⩾ q and 4p2 − 4q ⩽ 0 (which is equivalent
to q ⩾ p2 ). Our p = 2/M and q = 1/M satisfies these conditions. Therefore the inner-product matrix is
positive semidefinite and the vectors exist.
Now we can prove Lemma 5.4, which says the optimal SDP solution has value close to 1.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 260
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
Proof of Lemma 5.4. The value of the solution we exhibited above is
h i
ES∈C [Prσ ∈πS [|σ −1 (1)| = 1]] = ES∈C ∑ πS (σ )
σ :S→{0,1},|σ |−1 (1)=1
h |S| |S| 3|S| − 2 i
= ES∈C · − · p + 2q
|S| − 2 |S| − 1 |S| − 1
h |S| 3|S| − 2 i
⩾ ES∈C − · p + 2q
|S| − 1 |S| − 1
= ES∈C [1 − 3p + 2q + (1 − p)/(|S| − 1)]
⩾ ES∈C [1 − 3p + 2q]
= 1 − 3p + 2q = 1 − 4/M .
Together with Theorem 3.1, Lemmas 5.1 and 5.4 imply Theorem 2.4.
5.2 A robust algorithm for almost-satisfiable Max 1-in-k-SAT
In this section, we prove Theorem 2.5.
Theorem 2.5 (restated). For every constant B > 1, the following holds. There is a polynomial time
algorithm that given a (1 − 1/(Bk))-satisfiable instance of Max 1-in-k-SAT, finds a truth-assignment
√ on
variables satisfying exactly one term for a fraction λ of the clauses, where λ = (1 − 1/ B)2 /e.
The algorithm is based on rounding an LP relaxation for the problem, and gives a robust version of
the algorithm in [8] which achieved a factor 1/e-approximation for (perfectly) satisfiable instances.
Given a truth-assignment σ and a clause C, we denote σ ∩ C by the set of terms in C satisfied by
σ . Our algorithm first solves the following LP relaxation of the problem. (The relaxation is a linear
programming since we can expand the expectation and probability operators into linear combinations of
entries of πC .)
Maximize EC∈C [Prσ ∈πC [|σ ∩C| = 1]]
subject to Prσ ∈πC [σ (i) = 1] = xi ∀C ∈ C, i ∈ C .
Given a solution {πC } and {xi } to the LP, we generate an assignment τ by for each i ∈ U letting
τ(xi ) = 1 with probability xi . Then we prove the following lemma which directly implies Theorem 2.5.
Lemma 5.5. For every constant B > 1, when OPTLP > 1 − 1/(Bk), we have
√
(1 − 1/ B)2
Eτ [PrC∈C [|τ ∩C| = 1]] ⩾ .
e
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 261
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
Proof. Given√EC∈C [Prσ ∈πC [|σ ∩C| = 1]] > 1 − 1/(Bk), by an averaging argument, we know that for at
least (1 − 1/ B) fraction of C ∈ C are “good,” i. e., for these C clauses, we have
1
Prσ ∈πC [|σ ∩C| = 1] > 1 − √ .
Bk
For each good C ∈ C, and for each term t ∈ C, let p(t) = xi if t = xi , or p(t) = 1 − xi if t = xi , i. e.,
p(t) is the probability that t is satisfied by τ. Then we know that
1
∑ p(t) = Eσ ∈π [|σ ∩C|] ⩾ Prσ ∈π [|σ ∩C| = 1] ⩾ 1 − √Bk .
C C
t∈C
On the other hand,
√
∑ p(t) = Eσ ∈π [|σ ∩C|] ⩽ Prσ ∈π [|σ ∩C| = 1] + (1 − Prσ ∈π [|σ ∩C| = 1])|C| ⩽ 1 + 1/ B . (5.1)
C C C
t∈C
We now lower bound the probability that τ satisfies C, using the Lemma 5.6 proved at the end of the
section. We discuss the following two cases to establish the lower bound.
Case 1. If all the terms in C depend on distinct variables, then
Prτ [|τ ∩C| = 1] = ∑ p(t) ∏ (1 − p(t 0 )) . (5.2)
t∈C t 0 ∈C,t6=t 0
√ √ √ √
For good C we know that ∑t∈C p(t) ∈ [1 − 1/( Bk), 1 + 1/ B] ⊆ √ [1 − 1/ B, 1 + 1/ B]. By
Lemma 5.6 given right after this proof, we know that (5.2) ⩾ (1 − 1/ B)/e.
Case 2. If some terms in C√depend on the same variable, i. e., ∃i : xi , xi ∈ C, then by (5.1) we know that
∑t∈C\{xi ,xi } p(t) ⩽ 1/ B < 1. Thus terms in C \ {xi , xi } depend on distinct variables, we have
√
Prτ [|τ ∩C| = 1] = 1 · ∏ (1 − p(t)) ⩾ 1 − ∑ p(t) ⩾ 1 − 1/ B .
t∈C\{xi ,xi } t∈C\{xi ,xi }
Combining the two cases above, we get
Eτ [PrC∈C [|τ ∩C| = 1]] = EC∈C [Prτ [|τ ∩C| = 1]]
√
⩾ (1 − 1/ B)EC∈C [Prτ [|τ ∩C| = 1] | C is good]
√
(1 − 1/ B)2
⩾ .
e
It remains to prove the following inequality which was used in the above proof.
Lemma 5.6. Given x1 , x2 , . . . , xn ∈ [0, 1], and 1 − ε ⩽ ∑i xi ⩽ 1 + ε where ε < 1 then
1−ε
∑ xi ∏(1 − x j ) ⩾ e
.
i j6=i
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 262
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
Proof. We use the following claim to prove this lemma.
Claim 5.7. For n ⩾ 2, given a set of n numbers {xi } as described in the lemma, the objective function
∑i xi ∏ j6=i (1 − x j ) is minimized when
• all the xi ’s are the same, or
• ∃i : xi = 0 or ∃i : xi = 1.
Proof. Suppose the first condition doesn’t hold, we prove the second one holds. Without loss of generality
assume that x1 6= x2 . Then rewrite the objective function as
x
∑ ∏i (1 − x j ) = (1 − x1 )(1 − x2 ) x
∑ ∏
i (1 − x j ) + x1 (1 − x 2 ) + x 2 (1 − x 1 ) ∏(1 − x j ) .
i j6=i i⩾3 j6=i, j⩾3 j⩾3
Let C1 = ∑i⩾3 xi ∏ j6=i, j⩾3 (1 − x j ) and C2 = ∏ j⩾3 (1 − x j ), we have
∑ xi ∏(1 − x j ) = C1 + (C2 −C1 )(x1 + x2 ) + (C1 − 2C2 )x1 x2 .
i j6=i
Note that when fixing the sum x1 + x2 , we can change individual values of x1 and x2 within [0, 1] while still
{xi } still being a valid solution. By the perturbation, only the term (C1 −2C2 )x1 x2 in the objective function
might have value changed. Since x1 6= x2 , we know that C1 − 2C2 > 0 or making x10 = x20 = (x1 + x2 )/2
gets no larger objective function value. When C1 − 2C2 > 0, x1 and x2 should be “apart from” each other,
thus one of x1 and x2 must touch their bound, i. e., 0 or 1.
Now we use this claim and induction on n to prove the lemma. The lemma trivially holds in the base
case when n = 1. When n = k > 1, supposing the lemma holds for all n < k, we discuss the three cases
proposed by Claim 5.7 (splitting the second case in the claim into two).
• When all xi ’s are the same, we know that xi = S/n where S = ∑i xi . Then
S n−1
∑ xi ∏(1 − x j ) = S 1 − n ⩾ Se−S ⩾ min{(1 − ε)eε , (1 + ε)e−ε }/e ,
i j6=i
where the last inequality is because that S ∈ [1 − ε, 1 + ε] and that Se−S is monotonically increasing
when S ∈ [1 − ε, 1] and monotonically decreasing when S ∈ [1, 1 + ε].
We have (1 − ε)eε ⩾ 1 − ε. By e−ε ⩾ 1 − ε, we know that (1 + ε)e−ε ⩾ 1 − ε 2 ⩾ 1 − ε. In all, we
have ∑i xi ∏ j6=i (1 − x j ) ⩾ (1 − ε)/e.
• When ∃i : xi = 0, with out loss of generality, suppose x1 = 0. Then this reduces to the same problem
with (n − 1) variables and the induction hypothesis gives us a (1 − ε)/e lower bound.
• When ∃i : xi = 1, again with out loss of generality, suppose x1 = 1. Now the objective function
becomes ∏i⩾2 (1 − xi ) while ∑i⩾2 xi is at most ε. It is easy to see the product is lower bounded by
(1 − ε). (All but one of xi are 0.)
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 263
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
6 Concluding remarks on finding almost-satisfying assignments for CSPs
In the world of “CSP dichotomy” (see [10] for a recent survey), the tractability of LIN-mod-2, 2-SAT, and
Horn-SAT is explained by the existence of non-trivial polymorphisms which combine many satisfying
assignments to produce a new satisfying assignment. The Boolean functions which are polymorphisms
for LIN-mod-2, 2-SAT, and Horn-SAT are xor (of odd size), majority, and minimum respectively. The
existence of algorithms to find almost-satisfying assignments to 2-SAT and Horn-SAT can be attributed
to the “noise stability” of the majority and minimum functions. The xor function of many variables, on
the other hand, is highly sensitive to noise. This distinction seems to underly the difficulty of solving
near-satisfiable instances of LIN-mod-2 and Håstad’s tight hardness result for the problem.
For Boolean CSPs, we understand the complexity of finding almost-satisfying assignments for all the
cases where deciding satisfiability is tractable: it is possible in polynomial time for 2-SAT and Horn-SAT,
and NP-hard for LIN-mod-2. Further, under the UGC, the exact approximation threshold as a function of
the gap ε to perfect satisfiability is also pinned down for both 2-SAT and Horn-SAT. What about CSPs
over larger domains? For any CSP Π that can “express linear equations” (this notion is formalized in the
CSP dichotomy literature, but we can work with the intuitive meaning for this discussion), Håstad’s strong
inapproximability result for near-satisfiable linear equations over abelian groups [9] implies hardness of
finding an almost satisfying assignment for (1 − ε)-satisfiable instances of Π. A recent breakthrough [1]
established that every other tractable CSP (i. e., a polynomial time decidable CSP that cannot express
linear equations) must be of so-called “bounded width,” which means that a natural local propagation
algorithm correctly decides satisfiability of every instance of that CSP.
We end this paper with the appealing conjecture that every bounded width CSP admits a robust
satisfiability algorithm that can find a (1 − g(ε))-satisfying assignment given a (1 − ε)-satisfiable instance
for some function g() such that g(ε) → 0 as ε → 0. (We should clarify that in this context we always
treat the domain size k of the CSP as fixed and let ε → 0, so g(ε) can have an arbitrary dependence
on k. Note that Unique Games itself, which is a bounded width CSP, admits a robust satisfiability
√
algorithm that satisfies a fraction 1 − O( ε log k) of constraints in a (1 − ε)-satisfiable instance [3].) By
the preceding discussion, this conjecture would imply that bounded width characterizes the existence of
robust satisfiability algorithms for CSPs.
6.1 Subsequent work on our conjecture
There are several subsequent works regarding the conjecture proposed above, after the publication of
the conference version of this paper. A partial answer to the conjecture for width-1 problems was
independently given by [16] and [6], and the full conjecture was later confirmed by [2].
Acknowledgments
We thank Andrei Krokhin for a useful discussion on the relationship between the Unique Games conjecture
and our “bounded width implies robust satisfiability” conjecture.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 264
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
References
[1] L IBOR BARTO AND M ARCIN KOZIK: Constraint satisfaction problems of bounded width. In Proc.
50th FOCS, pp. 595–603. IEEE Comp. Soc. Press, October 2009. [doi:10.1109/FOCS.2009.32] 264
[2] L IBOR BARTO AND M ARCIN KOZIK: Robust satisfiability of constraint satisfaction problems. In
Proc. 44th STOC, pp. 931–940. ACM Press, 2012. [doi:10.1145/2213977.2214061] 264
[3] M OSES C HARIKAR , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: Near-optimal
algorithms for unique games. In Proc. 38th STOC, pp. 205–214. ACM Press, 2006.
[doi:10.1145/1132516.1132547] 264
[4] M OSES C HARIKAR , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: Near-optimal
algorithms for maximum constraints satisfaction problems. ACM Trans. Algorithms, 5(3), 2009.
Preliminary version in SODA’07. [doi:10.1145/1541885.1541893] 241
[5] P IERLUIGI C RESCENZI , R ICCARDO S ILVESTRI , AND L UCA T REVISAN: On weighted vs un-
weighted versions of combinatorial optimization problems. Inform. and Comput., 167(1):10–26,
2001. Preliminary version in ISTCS’96. [doi:10.1006/inco.2000.3011] 240
[6] V ICTOR DALMAU AND A NDREI K ROKHIN: Robust satisfiability for CSPs: Algorithmic and
hardness results, 2011. In preparation. 264
[7] E RIK D. D EMAINE , U RIEL F EIGE , M OHAMMAD TAGHI H AJIAGHAYI , AND M OHAMMAD R.
S ALAVATIPOUR: Combination can be hard: Approximability of the unique coverage problem. SIAM
J. Comput., 38(4):1464–1483, 2008. Preliminary version in SODA’06. [doi:10.1137/060656048]
243
[8] V ENKATESAN G URUSWAMI AND L UCA T REVISAN: The complexity of making unique choices:
Approximating 1-in-k sat. In Proc. 8th Internat. Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX’05), pp. 99–110, 2005. [doi:10.1007/11538462_9]
241, 243, 247, 261
[9] J OHAN H ÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Prelimi-
nary version in STOC’97. [doi:10.1145/502090.502098] 241, 264
[10] PAVOL H ELL AND JAROSLAV N EŠET ŘIL: Colouring, constraint satisfaction, and complexity. Comp.
Sci. Rev., 2(3):143–163, 2008. [doi:10.1016/j.cosrev.2008.10.003] 264
[11] P ETER J ONSSON , A NDREI K ROKHIN , AND F REDRIK K UIVINEN: Hard constraint satisfaction
problems have hard gaps at location 1. Theoret. Comput. Sci., 410(38-40):3856–3874, 2009.
[doi:j.tcs.2009.05.022] 241
[12] S ANJEEV K HANNA , M ADHU S UDAN , L UCA T REVISAN , AND DAVID P. W ILLIAMSON: The
approximability of constraint satisfaction problems. SIAM J. Comput., 30(6):1863–1920, 2001.
[doi:10.1137/S0097539799349948] 240, 241, 242, 252
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 265
V ENKATESAN G URUSWAMI AND Y UAN Z HOU
[13] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. [doi:10.1145/509907.510017] 241
[14] S UBHASH K HOT, G UY K INDLER , E LCHANAN M OSSEL , AND RYAN O’D ONNELL: Optimal
inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–
357, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447372] 241
[15] S UBHASH K HOT AND O DED R EGEV: Vertex cover might be hard to approximate to
within 2-ε. J. Comput. System Sci., 74(3):335–349, 2008. Preliminary version in CCC’03.
[doi:10.1016/j.jcss.2007.06.019] 253
[16] G ÁBOR K UN , RYAN O’D ONNELL , S UGURU TAMAKI , Y UICHI YOSHIDA , AND Y UAN Z HOU:
Linear programming, width-1 CSPs, and robust satisfaction. In Proc. 3rd Innovations in Theoret-
ical Computer Science Conf. (ITCS’12), pp. 484–495, New York, NY, USA, 2012. ACM Press.
[doi:10.1145/2090236.2090274] 264
[17] P RASAD R AGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In
Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414] 244, 245
[18] T HOMAS J. S CHAEFER: The complexity of satisfiability problems. In Proc. 10th STOC, pp.
216–226. ACM Press, 1978. [doi:10.1145/800133.804350] 240
[19] U RI Z WICK: Finding almost-satisfying assignments. In Proc. 30th STOC, pp. 551–560. ACM Press,
1998. [doi:10.1145/276698.276869] 240, 241, 245
AUTHORS
Venkatesan Guruswami
Associate professor
Carnegie Mellon University, Pittsburgh, PA
guruswami cmu edu
http://www.cs.cmu.edu/~venkatg/
Yuan Zhou
Ph. D. student
Carnegie Mellon University, Pittsburgh, PA
yuanzhou cs cmu edu
http://www.cs.cmu.edu/~yuanzhou/
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 266
T HE A PPROXIMABILITY OF A LMOST-S ATISFIABLE H ORN SAT AND E XACT H ITTING S ET
ABOUT THE AUTHORS
V ENKATESAN G URUSWAMI , or Venkat, as his friends and colleagues call him, received
his Bachelor’s degree from the Indian Institute of Technology at Madras in 1997. He is
grateful to his undergraduate research advisor, C. Pandu Rangan, for initiating him to the
joys of theoretical computer science. Venkat received his Ph. D. from the Massachusetts
Institute of Technology in 2001 under the excellent advisorship of Madhu Sudan.
Venkat is currently an Associate Professor in the Computer Science Department at
Carnegie Mellon University. Earlier, during 2002-09, he was a faculty member at the
University of Washington. Venkat was a Miller Research Fellow at UC Berkeley during
2001-02, and was a member of the School of Mathematics, Institute for Advanced Study
during 2007-08.
Venkat’s research interests span several topics including the theory of error-correcting
codes, approximability of fundamental optimization problems, pseudorandomness, proba-
bilistically checkable proofs, computational complexity theory, and algebraic algorithms.
Venkat currently serves on the editorial boards of the SIAM Journal on Computing, the
IEEE Transactions on Information Theory, and the ACM Transactions on Computation
Theory, and is program committee chair for the 2012 Computational Complexity confer-
ence. Venkat is a recipient of the Presburger award, the Packard Fellowship, the Sloan
Fellowship, the NSF CAREER award, the ACM Doctoral Dissertation Award, and the
IEEE Information Theory Society Paper Award.
In his (sadly limited) spare time, Venkat enjoys traveling, ethnic vegetarian food, racquet
sports, hiking/running within his humble limits, and listening to Carnatic music.
Y UAN Z HOU is a Ph. D. student in the Computer Science Department at Carnegie Mellon
University. His advisors are Ryan O’Donnell and Venkatesan Guruswami. Yuan was
an undergraduate student in the Microsoft Special Pilot CS Class supervised by Prof.
Andrew Yao at Tsinghua University, and received his Bachelor’s degree in 2009. His
main research interests are in approximation algorithms, hardness of approximation,
and analysis of Boolean functions. He is also interested in algorithmic mechanism
design, algebraic dichotomy theory, coding theory, and their relations to the theory of
approximation algorithms.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 239–267 267