On the Approximability of Presidential Type Predicates
share
Given a predicate P: {-1, 1}^k →{-1, 1}, let CSP(P) be the set of constraint satisfaction problems whose constraints are of the form P. We say that P is approximable if given a nearly satisfiable instance of CSP(P), there exists a probabilistic polynomial time algorithm that does better than a random assignment. Otherwise, we say that P is approximation resistant. In this paper, we analyze presidential type predicates, which are balanced linear threshold functions where all of the variables except the first variable (the president) have the same weight. We show that almost all presidential-type predicates P are approximable. More precisely, we prove the following result: for any δ_0 > 0, there exists a k_0 such that if k ≥ k_0, δ∈ (δ_0,1 - 2/k], and δk + k - 1 is an odd integer then the presidential-type predicate P(x) = sign(δkx_1 + ∑_i=2^kx_i) is approximable.
READ FULL TEXT