ECCC-Report TR08-009https://eccc.weizmann.ac.il/report/2008/009Comments and Revisions published for TR08-009en-usTue, 19 Feb 2008 06:25:51 +0200
Paper TR08-009
| Approximation Resistant Predicates From Pairwise Independence |
Per Austrin,
Elchanan Mossel
https://eccc.weizmann.ac.il/report/2008/009We 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$.
Tue, 19 Feb 2008 06:25:51 +0200https://eccc.weizmann.ac.il/report/2008/009