Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-116 | 5th May 2020 02:49

$d$-to-$1$ Hardness of Coloring $3$-colorable Graphs with $O(1)$ colors

RSS-Feed




Revision #1
Authors: Venkatesan Guruswami, Sai Sandeep
Accepted on: 5th May 2020 02:49
Downloads: 30
Keywords: 


Abstract:

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.



Changes to previous version:

The hardness is extended to $3$-colorable graphs by applying a subsequently discovered repeated arc digraph construction to reduce the chromatic number to 3. This version is the ICALP 2020 camera ready paper.


Paper:

TR19-116 | 9th September 2019 23:28

$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors





TR19-116
Authors: Venkatesan Guruswami, Sai Sandeep
Publication: 9th September 2019 23:29
Downloads: 267
Keywords: 


Abstract:

The $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.



ISSN 1433-8092 | Imprint