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.