Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-039 | 13th April 2005 00:00

Conditional Hardness for Approximate Coloring


Authors: Irit Dinur, Elchanan Mossel, Oded Regev
Publication: 13th April 2005 21:42
Downloads: 3022


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

ISSN 1433-8092 | Imprint