Sai Sandeep

# $$d$$-to-1 hardness of coloring 3-colorable graphs with $$O(1)$$ colors.

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 $$\varepsilon > 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.

Joint work with Venkatesan Guruswami.