Name
Abstract | ||
|---|---|---|
We study the APRXCOLORING(q, Q) problem: Given a graph G, decide whether chi(G) <= q or chi(G) >= Q. We present hardness results for this problem for any constants 3 <= q < Q. For q >= 4, our result is based on Khot's 2-to-1 label cover, which is conjectured to be NP-hard [S. Khot, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767-775]. For q = 3, we base our hardness result on a certain "x-shaped" variant of his conjecture. Previously no hardness result was known for q = 3 and Q >= 6. At the heart of our proof are tight bounds on generalized noise-stability quantities, which extend the recent work of Mossel, O'Donnell, and Oleszkiewicz ["Noise stability of functions with low influences: Invariance and optimality," Ann. of Math. (2), to appear] and should have wider applicability. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/07068062X | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
hardness of approximation,unique games,graph coloring | Journal | 39 |
Issue | ISSN | Citations |
3 | 0097-5397 | 3 |
PageRank | References | Authors |
0.40 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Elchanan Mossel | 2 | 1725 | 145.16 |
| Oded Regev | 3 | 2322 | 133.33 |