Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-148 | 26th October 2013 11:45

On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

RSS-Feed




TR13-148
Authors: Irit Dinur, Igor Shinkar
Publication: 26th October 2013 12:37
Downloads: 4377
Keywords: 


Abstract:

For 3 \leq q < Q we consider the \text{ApproxColoring}(q,Q) problem of deciding for a given graph G whether \chi(G) \leq q or \chi(G) \geq Q. It was show in [DMR06] that the problem \text{ApproxColoring}(q,Q) is NP-hard for q=3,4 and arbitrary large constant Q under variants of the Unique Games Conjecture.

In this paper we give a tighter analysis of the reduction of [DMR06] from Unique Games to the \text{ApproxColoring} problem. We find that (under appropriate conjecture) a careful calculation of the parameters in [DMR06] implies hardness of coloring a 4-colorable graph with \log^c(\log(n)) colors for some positive constant c. By improving the analysis of the reduction we show hardness of coloring a 4-colorable graph with \log^c(n) colors for some positive constant c.

The main technical contribution of the paper is a variant of the Majority is Stablest Theorem, which says that among all balanced functions in which every coordinate has o(1) influence, the Majority function has the largest noise stability. We adapt the theorem for our applications to get a better dependency between the parameters required for the reduction.



ISSN 1433-8092 | Imprint