ECCC-Report TR13-148https://eccc.weizmann.ac.il/report/2013/148Comments and Revisions published for TR13-148en-usSat, 26 Oct 2013 12:37:11 +0300
Paper TR13-148
| On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors |
Irit Dinur,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2013/148For $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.
Sat, 26 Oct 2013 12:37:11 +0300https://eccc.weizmann.ac.il/report/2013/148