ECCC-Report TR19-116https://eccc.weizmann.ac.il/report/2019/116Comments and Revisions published for TR19-116en-usTue, 05 May 2020 02:49:30 +0300
Revision 1
| $d$-to-$1$ Hardness of Coloring $3$-colorable Graphs with $O(1)$ colors |
Venkatesan Guruswami,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2019/116#revision1 The $d$-to-$1$ conjecture of Khot asserts that it is NP-hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $3$-colorable graph with $C$ colors for arbitrarily large integers $C$.
Earlier, the hardness of $O(1)$-coloring a $4$-colorable graphs was known under the $2$-to-$1$ conjecture, which is the strongest in the family of $d$-to-$1$ conjectures, and the hardness for $3$-colorable graphs was known under a certain ``fish-shaped'' variant of the $2$-to-$1$ conjecture.Tue, 05 May 2020 02:49:30 +0300https://eccc.weizmann.ac.il/report/2019/116#revision1
Paper TR19-116
| $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors |
Venkatesan Guruswami,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2019/116The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ colors for arbitrarily large integers $C$. Earlier, this implication was only known under the $2$-to-$1$ conjecture, which is the strongest in the family of $d$-to-$1$ conjectures.Mon, 09 Sep 2019 23:29:16 +0300https://eccc.weizmann.ac.il/report/2019/116