Conditional Hardness for Approximate Coloring
| dc.creator | Dinur, Irit | |
| dc.creator | Mossel, Elchanan | |
| dc.creator | Regev, Oded | |
| dc.date | 2005-04-14 | |
| dc.date.accessioned | 2026-07-07T03:22:52Z | |
| dc.date.available | 2026-07-07T03:22:52Z | |
| dc.description | We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$ or $c(G) \ge Q$, where c(G) is the chromatic number of G. 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 `fish shaped' variant of his conjecture. We also prove that the problem almost coloring 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 a $\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]. | |
| dc.identifier | https://arxiv.org/abs/cs/0504062 | |
| dc.identifier | http://arxiv.org/abs/cs/0504062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32719 | |
| dc.subject | Computational Complexity | |
| dc.subject | Probability | |
| dc.title | Conditional Hardness for Approximate Coloring | |
| dc.type | text |