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 -