Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-009 | 7th December 2007 00:00

Approximation Resistant Predicates From Pairwise Independence


Authors: Per Austrin, Elchanan Mossel
Publication: 19th February 2008 06:25
Downloads: 1429


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} +

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$.

ISSN 1433-8092 | Imprint