TR08-009 Authors: Per Austrin, Elchanan Mossel

Publication: 19th February 2008 06:25

Downloads: 3414

Keywords:

We study the approximability of predicates on $k$ variables from a

domain $[q]$, and give a new sufficient condition for such predicates

to be approximation resistant under the Unique Games Conjecture.

Specifically, we show that a predicate $P$ is approximation resistant

if there exists a balanced pairwise independent distribution over

$[q]^k$ whose support is contained in the set of satisfying assignments

to $P$.

Using constructions of pairwise indepenent distributions this result

implies that:

For general $k \ge 3$ and $q \ge 2$, the Max $k$-CSP$_q$ problem is

UG-hard to approximate within $q^{\lceil \log_2 k +1 \rceil - k} +

\epsilon$.

For $k \geq 3$ and $q$ prime power, the hardness ratio is improved to

$kq(q-1)/q^k + \epsilon$.

For the special case of $q = 2$, i.e., boolean variables, we can

sharpen this bound to $(k + O(k^{0.525}))/2^k + \epsilon$, improving

upon the best previous bound of $2k/{2^k} + \epsilon$ (Samorodnitsky

and Trevisan, STOC'06) by essentially a factor $2$.

Finally, for $q=2$, assuming that the famous Hadamard Conjecture is

true, this can be improved even further, and the $O(k^{0.525})$ term

can be replaced by the constant $4$.