TY - GEN

T1 - Conditional hardness for approximate coloring

AU - Dinur, Irit

AU - Mossel, Elchanan

AU - Regev, Oded

PY - 2006

Y1 - 2006

N2 - We study the APPROXCOLORING(q, Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q. We derive conditional hardness for this problem for any constant 3 ≤ q < Q. For q ≥ 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 '⋉ shaped' variant of his conjecture. We also prove that the problem ALMOST-3-COLORINGε is hard for any constant ε > 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 a ε fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least ε. Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

AB - We study the APPROXCOLORING(q, Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q. We derive conditional hardness for this problem for any constant 3 ≤ q < Q. For q ≥ 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 '⋉ shaped' variant of his conjecture. We also prove that the problem ALMOST-3-COLORINGε is hard for any constant ε > 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 a ε fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least ε. Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

KW - Graph Coloring

KW - Hardness of Approximation

KW - Unique Games Conjecture

UR - http://www.scopus.com/inward/record.url?scp=33748106639&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748106639&partnerID=8YFLogxK

U2 - 10.1145/1132516.1132567

DO - 10.1145/1132516.1132567

M3 - Conference contribution

AN - SCOPUS:33748106639

SN - 1595931341

SN - 9781595931344

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 344

EP - 353

BT - STOC'06

PB - Association for Computing Machinery

T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06

Y2 - 21 May 2006 through 23 May 2006

ER -