TR05-039 Authors: Irit Dinur, Elchanan Mossel, Oded Regev

Publication: 13th April 2005 21:42

Downloads: 1078

Keywords:

We study the approximate-coloring(q,Q) problem: Given a graph G, decide

whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional

hardness for this problem for any constant 3\le q < Q. For q \ge

4, our result is based on Khot's 2-to-1 conjecture [Khot'02].

For q=3, we base our hardness result on a certain `alpha-

shaped' variant of his conjecture.

We also prove that the problem almost-approximate-3-coloring(eps) is hard for any constant eps>0, assuming Khot's

Unique Games conjecture. This is the problem of

deciding for a given graph, between the case where

one can 3-color all but an \eps fraction of the vertices without

monochromatic edges, and the case where the graph contains no

independent set of relative size at least \eps.

Our result is based on bounding various generalized noise-stability

quantities using the invariance principle of Mossel et al [MOO'05].